A WebPage on Van Der Waerden's Theorem

by William Gasarch

(For now this is just papers that I want to gather in one place)

**VDW, poly-VDW, HJ, poly-HJ**

- Masters Thesis by Karen Johannson
*Variations on a theorem by van der Waerden*. Could really be a book on VDW. See: othervdwbook.pdf or if that does not work then: othervdwbook.pdf - Masters Thesis by Sohail Farhangi
*On Refinements of Van der waerden's Theorem*Focus on the set of naturals the difference can come from. refinevdw.pdf or if that does not work then: refinedvdw.pdf - Draft of a book on VDW material by
Gasarch and Kruskal and Parrish
GKPbook.pdf
Van der waerden's theorem: Variants and "Applications"
- Shelah's primitive recurive bounds on the VDW numbers [#!VDWs!#].
VDWSHELAH.PDF.
- Szemeredi's Density theorem [#!density!#].
SZDENSITY.PDF.
- Polynomial Extensions of VDW's and
Sz's thm, by
by Bergelson and Leibman[#!pvdw!#].
Has the original proof of
Poly VDW thm.
BergLeib.pdf,
Ergodic Methods.
- Combinatorial Proofs of the
Poly VDW thm and the Poly HJ thm.
by Mark Walters[#!pvdww!#].
This is the easier proof of Poly VDW.
walters.pdf,
Purely Combinatorial.
- A Partition Theorem by Shelah[#!pvdwshelah!#].
polyvdwshelah.pdf
This has primitive recursive bounds on the poly vdw.
- Set-Polynomials and Polynomial Extensions
of the HJ thm.
by Bergelson and Leibman[#!setpoly!#].
First proof of Poly-HJ. Hard.
polyHJ.pdf,
Ergodic Theory.
- Two Combinatorial Theorems on Arithmetic Progressions
by Wolfgang Schmidt[#!twocomb!#].
This gives some nice lower bounds on VDW numbers.
schmidtlowervdw.pdf,
Purely combinatorial.
- Monochromatic Equilateral Right Triangles
in the Integer Grid.
By Graham and Solymosi[#!monotri!#].
Gets a better upper bounds on W(3,c) as a corollary.
graham-solymosi.pdf,
Purely combinatorial.
- Question about
QUESTION
- A New Method to Construct Lower Bounds for VDW Numbers.
By Herwig, Heule, Lamblagen, an Maaren[#!newlbvdw!#].
lower-bds.pdf,
Purely Combinatorial.
- The van der Waerden Number is 1132.
By
Michal Kouril and
Jerome Paul.[#!VDWexactkouril!#].
1132.pdf.
- Extremal binary matrices without constant 2-squares
by Roland Bacher and Shalom Eliahou.
Journal of Combinatorics, Volume 1, Number 1, pages 77-100,
2011.
2colsq.pdf.
This is the paper where they show that any 2-coloring
of has a mono square.
- Investigating Monte-Carlo Methods on the Weak Schur Problem
by Eliahou, Fonlupt, Fromentin, Marion-Poty,
Robilliard, Teytaud.
Finding Schure Numbers.
They find n such that any 6-coloring of [n] has a mono x,y,z
with x+y=z.
- On Sets of Integers Which Contain No Three Terms in
Arithmetic Progession.
By Salem and Spencer[#!SS!#].
3ap-salem.pdf,
Purely Combinatorial.
- Behrend had the largest 3-free sets, but his paper is not online.
Elkin improved it and now has the largets 3-free sets.
Elkin
An easier proof of Elkin's theorem, due to Green and Wolfe:
Green-Wolfe
- On Sets of Integers Not Containing Long Arithmetic Progressiosn.
By Laba and Lacey[#!genbehrend!#].
k-free-sets.pdf,
Purely Combinatorial.
- Large -free sets based on Elkin's improvement of Behrends:
Bryant
- A Restricted Version of HJ Thm.
By Deuber, Promel, Rothschild[#!RHJ!#].
restrictedHJ.pdf,
- An Application of Lovasz Local Lemma-- A New Lower Bound
for the van der Waerden Number [#!szabolower!#].
by Soltan Szabo.
SZABOLOWER.PDF,
- A construction for partitions which avoid
long arithmetic progressions [#!vdwprimes!#]
by E. Berlekamp.
BERLEKAMPVDW.PDF,
- Combinatorial Number Theory: Resuls of Hilbert, Schur,
Folkman, and Hindman.
By Yudi Setyawan, Masters Degree
CNTSFH.PDF,
- A lower bound for off diagonal van der Warden numbers
by Li and Shu.
- Integer sets containing no arithmetic progressions
by Szemeredi [#!szlog!#]
SZLOG.PDF.
- Integer sets containing no arithmetic progressions
by Heath-Brown [#!heathbrown!#]
HEATHBROWN.PDF,
- Canonical Partition Theorems for parameter sets
by H.J. Promel and B.Voight [#!canhj!#]
CANHJ
They prove a very general canonical theorems.
One of the corollaries is Can Hales-Jewitt.

**Other Generalizations and Variants of VDW**

- Extremal binary matrices without constant 2-squares
Roland Batcher and Shalom Eliahou
sq.pdf,
In this paper they show that every 2-coloring of the
15 by 15 grid has a mono square. There is a 2-coloring of
the 14 by 14 grid without a mono square.
Journal of Combinatorics, Volum 1, 77-100, 2010.
- On Monochromatic subsets of a rectangular grid [#!monosquare!#].
By Maria Axenovich and Jacob Manske.
Integers: Electronic Journal of combinatorial number theory.
Volume 8, 2008, A21.
They prove that any 2-coloring of VDW(8,2) by VDW(8,2) has a mono square.
monosquare.pdf,
- Searching for Monochromatic-Square-Free Ramsey Grid Colorings
via SAT Solvers.
By Paul Walton and Wing Ning Li.
International Conference on information science and application, 2013.
This paper also has a 2-coloring of without a mono square
and shows you can't do 15.
monosquareexact.pdf,
- Independent Arithmetic progressions in clique-free graphs on the
natural numbers [#!ArithSeqInGraphs!#].
by Gunderson, Rodl, Sidorenko.
ArithSeqInGraphs.pdf,
- Ramsey's Theorem for -parameter sets.
by Graham and Rothschild [#!nparam!#].
A very general from which follows VDW and Ramsey.
Graham-Rothschild.pdf,
Hard.
- Note on Combinatorial Analysis.
by Richard Rado's
This contains both Rado's thm and
Gallai-Witt thm.
There is both a German version [#!radogerman!#] and
an English version [#!radoenglish!#].
rado-gallai-german.pdf,
or
rado-gallai-english.pdf,
Purely Combinatorial.
- Ein Kombinatorischer Satz der Elementgeometric (German)
By Von Ernst Witt[#!witt!#].
Witt's article that contain Gallai-Witt thm.
witt.pdf,
Purely Combinatorial but in German.
- An ergodic Szemeredi Theorem for commuting transformations.
By Furstenberg and Katznelson [#!densityGW!#].
ergodicsz.pdf,
This has a density version of the Gallai-Witt theorem.
- An elementary proof of the canonizing version of Gallai-Witt's theorem
by Rödl and Prömel[#!VDWcan!#].
CanGallaiWittElementary.pdf
My notes on this paper:
vdwcanNOTES.pdf,
Purely Combinatorial.
- A Canonical Partition Theorem for Equivalence Relations
on . Deuber, Graham, Promel, Voigt[#!VDWcanhard!#]
VDWcan.pdf,
Ergodic theorey or other hard techniques.
- Partition Theorems and Computability Theory
by Joseph Mileti[#!canramseylogic!#]
canramseylogic.pdf,
- Restricted Ramsey Configurations.
Spencer[#!CanConf!#].
res-ram-config.pdf,
Purely Combinatorial.
- VDW's thm on Homothetic Copies of
.
By Kim and Rho [#!vdwh1!#].
VDWH.pdf,
- Monochromatic Homothetic Copies of
[#!vdwh2!#].
VDWHcopies.pdf,
- APs in Sequences with Bounded Gaps,
by Tom Brown and Donavan Hare[#!APgaps!#].
VDWgaps.pdf.
- The 2-color relative linear VDW numbers by Kim and Rho[#!lvdw!#].
VDWlin.pdf.
- An Infinitary Polynomial VDW Thm.
By McCutcheon[#!infvdw!#].
infinite-vdw.pdf,
- Rainbow Arithmetic Progression and Anti-Ramsey Results.
By Jungic, Licht, Mahdian, Nesteril, Radoicic.
rainbow.pdf,
- Difference sets without squares.
by I.Z. Ruzsa[#!Ruzsasq!#].
sqdiff-ruzsa.pdf,
- On differences of sets of sequences of integers I [#!sarkozyONE!#]
by Sarkozy.
SARKOZYONE.PDF,
- Sets whose differences set is square-free by Julia Wolf [#!wolfsq!#]
WOLFSQ.PDF,
- On sets of natural numbers whose difference set contains
on squares
By Pintz, Steiger, Szemeredi
PSS.PDF,
- On differences os sequences of integers III
by Sarkozy
ONDIFFIII.PDF,

**Sz's Theorem**

- Tau's exposition of Sz's thm
by Tau.
tauexpsz.pdf.
- Notes on Sz's Reg Lemma
by Ernie Croot. Good exposition!
notesregularity.pdf,
- A New Proof of Sz's Thm for AP's of Length 4.
By Gowers.
gowers-sz-4AP.pdf,
- Roth's Thm on AP's.
By Iosevich.
notes-roth3ap.pdf,
- Sz Reg Lemma and its applications in Graph Theory.
By Komlos, Simonovitis.
szreg-applications.pdf,
- Ergodic behaviour of diagonal measures and a theorem of Szemerédi on
arithmetic progressions [#!Furstenberg!#]
by
Hillel Furstenberg.
FURSTENBERGSZ.PDF,
- The Ergodic Theoretic Proof of Sz Thm.
By Furstenberg, Katznelson, Ornstein.
sz-thm-ergodic-easier.pdf,
- A New Proof of Sz Thm.
By Gowers.
sz-thm-gowers-proof.pdf,
- An alternate proof
of Szemeredi's
cube lemma
using extremal
hypergraphs.
By Gunderson and
Rodl.
szcubedensity.pdf,