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**

- Draft of a book on VDW material by
Gasarch and Kruskal and Parrish
GKPbook.pdf
Van der waerden's theorem: Variants and "Applications"
This is a draft- we welcome comments and corrections.
- Shelah's primitive recurive bounds on the VDW numbers [31].
VDWSHELAH.PDF.
- Szemeredi's Density theorem [34].
SZDENSITY.PDF.
- Polynomial Extensions of VDW's and
Sz's thm, by
by Bergelson and Leibman[2].
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[36].
This is the easier proof of Poly VDW.
walters.pdf,
Purely Combinatorial.
- A Partition Theorem by Shelah[30].
polyvdwshelah.pdf
This has primitive recursive bounds on the poly vdw.
- Set-Polynomials and Polynomial Extensions
of the HJ thm.
by Bergelson and Leibman[3].
First proof of Poly-HJ. Hard.
polyHJ.pdf,
Ergodic Theory.
- Two Combinatorial Theorems on Arithmetic Progressions
by Wolfgang Schmidt[29].
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[12].
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[15].
lower-bds.pdf,
Purely Combinatorial.
- The van der Waerden Number is 1132.
By
Michal Kouril and
Jerome Paul.[18].
1132.pdf.
- Extremal binary matrices without constant 2-squares
by Roland Bacher and Shalom Eliahou.
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[27].
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[19].
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[8].
restrictedHJ.pdf,
- An Application of Lovasz Local Lemma-- A New Lower Bound
for the van der Waerden Number [33].
by Soltan Szabo.
SZABOLOWER.PDF,
- A construction for partitions which avoid
long arithmetic progressions [4]
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 [35]
SZLOG.PDF.
- Integer sets containing no arithmetic progressions
by Heath-Brown [14]
HEATHBROWN.PDF,
- Canonical Partition Theorems for parameter sets
by H.J. Promel and B.Voight [23]
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 [1].
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,
- Independent Arithmetic progressions in clique-free graphs on the
natural numbers [13].
by Gunderson, Rodl, Sidorenko.
ArithSeqInGraphs.pdf,
- Ramsey's Theorem for -parameter sets.
by Graham and Rothschild [11].
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 [24] and
an English version [25].
rado-gallai-german.pdf,
or
rado-gallai-english.pdf,
Purely Combinatorial.
- Ein Kombinatorischer Satz der Elementgeometric (German)
By Von Ernst Witt[37].
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 [10].
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[22].
CanGallaiWittElementary.pdf
My notes on this paper:
vdwcanNOTES.pdf,
Purely Combinatorial.
- A Canonical Partition Theorem for Equivalence Relations
on . Deuber, Graham, Promel, Voigt[7]
VDWcan.pdf,
Ergodic theorey or other hard techniques.
- Partition Theorems and Computability Theory
by Joseph Mileti[21]
canramseylogic.pdf,
- Restricted Ramsey Configurations.
Spencer[32].
res-ram-config.pdf,
Purely Combinatorial.
- VDW's thm on Homothetic Copies of
.
By Kim and Rho [16].
VDWH.pdf,
- Monochromatic Homothetic Copies of
[6].
VDWHcopies.pdf,
- APs in Sequences with Bounded Gaps,
by Tom Brown and Donavan Hare[5].
VDWgaps.pdf.
- The 2-color relative linear VDW numbers by Kim and Rho[17].
VDWlin.pdf.
- An Infinitary Polynomial VDW Thm.
By McCutcheon[20].
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[26].
sqdiff-ruzsa.pdf,
- On differences of sets of sequences of integers I [28]
by Sarkozy.
SARKOZYONE.PDF,
- Sets whose differences set is square-free by Julia Wolf [38]
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 [9]
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,