Main Page

hDHOOf <a href="http://kyjmdzvhqcrz.com/">kyjmdzvhqcrz</a>, [url=http://tqwqpvtsifxg.com/]tqwqpvtsifxg[/url], [link=http://riqpijdmrbbl.com/]riqpijdmrbbl[/link], http://lckrghakqopc.com/

Proof strategies

It is natural to look for strategies based on one of the following:

• Szemerédi's original proof of Szemerédi's theorem.
• Szemerédi's combinatorial proof of Roth's theorem.
• Ajtai-Szemerédi's proof of the corners theorem.
• The density increment method.
• The triangle removal lemma.
• Ergodic-inspired methods.
• The Furstenberg-Katznelson argument.
• Use of equal-slices measure.

Related theorems

• Carlson's theorem.
• The Carlson-Simpson theorem.
• Folkman's theorem.
• The Graham-Rothschild theorem.
• The colouring Hales-Jewett theorem.
• The Kruskal-Katona theorem.
• Roth's theorem.
• The IP-Szemerédi theorem.
• Sperner's theorem.
• Szemerédi's regularity lemma.
• Szemerédi's theorem.
• The triangle removal lemma.

All these theorems are worth knowing. The most immediately relevant are Roth's theorem, Sperner's theorem, Szemerédi's regularity lemma and the triangle removal lemma, but some of the others could well come into play as well.

Important concepts related to possible proofs

• Complexity of a set
• Concentration of measure
• Influence of variables
• Obstructions to uniformity
• Quasirandomness

Complete proofs or detailed sketches of potentially useful results

• The multidimensional Sperner theorem
• Line-free sets correlate locally with complexity-1 sets
• Correlation with a 1-set implies correlation with a subspace (Not finished)
• A Fourier-analytic proof of Sperner's theorem
• A second Fourier decomposition related to Sperner's theorem
• A Hilbert space lemma
• A Modification of the Ajtai-Szemerédi argument
• DHJ(k) implies multidimensional DHJ(k)

Attempts at proofs of DHJ(3)

• An outline of a density-increment argument (ultimately didn't work)
• A second outline of a density-increment argument (seems to be OK but more checking needed)

Bibliography

Density Hales-Jewett

1. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem for k=3“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
2. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem“, J. Anal. Math. 57 (1991), 64–119.
3. R. McCutcheon, “The conclusion of the proof of the density Hales-Jewett theorem for k=3“, unpublished.

Coloring Hales-Jewett theorem

1. A. Hales, R. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 1963 222--229. MR143712
2. N. Hindman, E. Tressler, "The first non-trivial Hales-Jewett number is four", preprint.
3. P. Matet, "Shelah's proof of the Hales-Jewett theorem revisited", European J. Combin. 28 (2007), no. 6, 1742--1745. MR2339499
4. S. Shelah, "Primitive recursive bounds for van der Waerden numbers", J. Amer. Math. Soc. 1 (1988), no. 3, 683--697. MR 929498

Roth's theorem

1. E. Croot, "Szemeredi's theorem on three-term progressions, at a glance, preprint.

Behrend-type constructions

1. M. Elkin, "An Improved Construction of Progression-Free Sets ", preprint.
2. B. Green, J. Wolf, "A note on Elkin's improvement of Behrend's construction", preprint.
3. K. O'Bryant, "Sets of integers that do not contain long arithmetic progressions", preprint.

Triangles and corners

1. M. Ajtai, E. Szemerédi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar. 9 (1974), 9--11 (1975). MR369299
2. I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, pp. 939--945, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, 1978. MR519318
3. J. Solymosi, A note on a question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), no. 2, 263--267. MR 2047239

Kruskal-Katona theorem

1. P. Keevash, "Shadows and intersections: stability and new proofs", preprint.