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

1. 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.

2. Shelah's primitive recurive bounds on the VDW numbers [29]. VDWSHELAH.PDF.

3. Szemeredi's Density theorem [32]. SZDENSITY.PDF.

4. Polynomial Extensions of VDW's and Sz's thm, by by Bergelson and Leibman[1]. Has the original proof of Poly VDW thm. BergLeib.pdf, Ergodic Methods.

5. Combinatorial Proofs of the Poly VDW thm and the Poly HJ thm. by Mark Walters[34]. This is the easier proof of Poly VDW. walters.pdf, Purely Combinatorial.

6. A Partition Theorem by Shelah[28]. polyvdwshelah.pdf This has primitive recursive bounds on the poly vdw.

7. Set-Polynomials and Polynomial Extensions of the HJ thm. by Bergelson and Leibman[2]. First proof of Poly-HJ. Hard. polyHJ.pdf, Ergodic Theory.

8. Two Combinatorial Theorems on Arithmetic Progressions by Wolfgang Schmidt[27]. This gives some nice lower bounds on VDW numbers. schmidtlowervdw.pdf, Purely combinatorial.

9. Monochromatic Equilateral Right Triangles in the Integer Grid. By Graham and Solymosi[11]. Gets a better upper bounds on W(3,c) as a corollary. graham-solymosi.pdf, Purely combinatorial.

10. A New Method to Construct Lower Bounds for VDW Numbers. By Herwig, Heule, Lamblagen, an Maaren[14]. lower-bds.pdf, Purely Combinatorial.

11. The van der Waerden Number $W(2,6)$ is 1132. By Michal Kouril and Jerome Paul.[17]. 1132.pdf.

12. On Sets of Integers Which Contain No Three Terms in Arithmetic Progession. By Salem and Spencer[25]. 3ap-salem.pdf, Purely Combinatorial.

13. On Sets of Integers Not Containing Long Arithmetic Progressiosn. By Laba and Lacey[18]. k-free-sets.pdf, Purely Combinatorial.

14. A Restricted Version of HJ Thm. By Deuber, Promel, Rothschild[7]. restrictedHJ.pdf,

15. An Application of Lovasz Local Lemma-- A New Lower Bound for the van der Waerden Number [31]. by Soltan Szabo. SZABOLOWER.PDF,

16. A construction for partitions which avoid long arithmetic progressions [3] by E. Berlekamp. BERLEKAMPVDW.PDF,

17. Combinatorial Number Theory: Resuls of Hilbert, Schur, Folkman, and Hindman. By Yudi Setyawan, Masters Degree CNTSFH.PDF,

18. A lower bound for off diagonal van der Warden numbers by Li and Shu.

19. Integer sets containing no arithmetic progressions by Szemeredi [33] SZLOG.PDF.

20. Integer sets containing no arithmetic progressions by Heath-Brown [13] HEATHBROWN.PDF,

LOWEROFF.PDF,

Other Generalizations and Variants of VDW

1. Independent Arithmetic progressions in clique-free graphs on the natural numbers [12]. by Gunderson, Rodl, Sidorenko. ArithSeqInGraphs.pdf,

2. Ramsey's Theorem for $n$-parameter sets. by Graham and Rothschild [10]. A very general from which follows VDW and Ramsey. Graham-Rothschild.pdf, Hard.

3. Note on Combinatorial Analysis. by Richard Rado's This contains both Rado's thm and Gallai-Witt thm. There is both a German version [22] and an English version [23]. rado-gallai-german.pdf, or rado-gallai-english.pdf, Purely Combinatorial.

4. Ein Kombinatorischer Satz der Elementgeometric (German) By Von Ernst Witt[35]. Witt's article that contain Gallai-Witt thm. witt.pdf, Purely Combinatorial but in German.

5. An ergodic Szemeredi Theorem for commuting transformations. By Furstenberg and Katznelson [9]. ergodicsz.pdf, This has a density version of the Gallai-Witt theorem.

6. An elementary proof of the canonizing version of Gallai-Witt's theorem by Rödl and Prömel[21]. CanGallaiWittElementary.pdf My notes on this paper: vdwcanNOTES.pdf, Purely Combinatorial.

7. A Canonical Partition Theorem for Equivalence Relations on $Z^n$. Deuber, Graham, Promel, Voigt[6]. VDWcan.pdf, Ergodic theorey or other hard techniques.

8. Partition Theorems and Computability Theory by Joseph Mileti[20] canramseylogic.ps,

9. Restricted Ramsey Configurations. Spencer[30]. res-ram-config.pdf, Purely Combinatorial.

10. VDW's thm on Homothetic Copies of $\{1,1+s,1+s+t\}$. By Kim and Rho [15]. VDWH.pdf,

11. Monochromatic Homothetic Copies of $\{1,1+s,1+s+t\}$[5]. VDWHcopies.pdf,

12. APs in Sequences with Bounded Gaps, by Tom Brown and Donavan Hare[4]. VDWgaps.pdf.

13. The 2-color relative linear VDW numbers by Kim and Rho[16]. VDWlin.pdf.

14. An Infinitary Polynomial VDW Thm. By McCutcheon[19]. infinite-vdw.pdf,

15. Rainbow Arithmetic Progression and Anti-Ramsey Results. By Jungic, Licht, Mahdian, Nesteril, Radoicic. rainbow.pdf,

16. Difference sets without squares. by I.Z. Ruzsa[24]. sqdiff-ruzsa.pdf,

17. On differences of sets of sequences of integers I [26] by Sarkozy. SARKOZYONE.PDF,

18. Sets whose differences set is square-free by Julia Wolf [36] WOLFSQ.PDF,

19. On sets of natural numbers whose difference set contains on squares By Pintz, Steiger, Szemeredi PSS.PDF,

20. On differences os sequences of integers III by Sarkozy ONDIFFIII.PDF,

Sz's Theorem

1. Tau's exposition of Sz's thm by Tau. tauexpsz.pdf.

2. Notes on Sz's Reg Lemma by Ernie Croot. Good exposition! notesregularity.pdf,

3. A New Proof of Sz's Thm for AP's of Length 4. By Gowers. gowers-sz-4AP.pdf,

4. Roth's Thm on AP's. By Iosevich. notes-roth3ap.pdf,

5. Sz Reg Lemma and its applications in Graph Theory. By Komlos, Simonovitis. szreg-applications.pdf,

6. Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions [8] by Hillel Furstenberg. FURSTENBERGSZ.PDF,

7. The Ergodic Theoretic Proof of Sz Thm. By Furstenberg, Katznelson, Ornstein. sz-thm-ergodic-easier.pdf,

8. A New Proof of Sz Thm. By Gowers. sz-thm-gowers-proof.pdf,

9. An alternate proof of Szemeredi's cube lemma using extremal hypergraphs. By Gunderson and Rodl. szcubedensity.pdf,