This wiki is intended to be a useful resource for anybody who wants to think about the density Hales-Jewett theorem. There are no rules about what can be added to it, but amongst other things it will contain articles that digest parts of the discussion that is taking place as part of the so-called Polymath project and present them in a concise way. This should save people from having to wade through hundreds of comments. If you add an article, it would be good to have it linked from this main page, so that it is easy to find. (However, there is also a list of all pages on this wiki.)
During the course of the discussion so far, several variants of the problem have been proposed.
The basic problem to be considered by the Polymath project is to explore a particular combinatorial approach to the density Hales-Jewett theorem for k=3 (DHJ(3)), suggested by Tim Gowers. The original proof of DHJ(3) used arguments from ergodic theory.
Useful background materials
Here is some background to the project. There is also a general discussion on massively collaborative "polymath" projects. This is a cheatsheet for editing the wiki. Finally, here is the general Wiki user's guide.
Threads and further problems
- (1-199) A combinatorial approach to density Hales-Jewett (inactive)
- (200-299) Upper and lower bounds for the density Hales-Jewett problem (inactive)
- (300-399) The triangle-removal approach (inactive)
- (400-499) Quasirandomness and obstructions to uniformity (inactive)
- (500-599) Possible proof strategies (active)
- (600-699) A reading seminar on density Hales-Jewett (active)
- (700-799) Bounds for the first few density Hales-Jewett numbers, and related quantities (active)
There is also a chance that we will be able to improve the known bounds on Moser's cube problem.
Here are some unsolved problems arising from the above threads.
Here is a tidy problem page.
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.
- 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.
- Complexity of a set
- Concentration of measure
- Influence of variables
- Obstructions to uniformity
Possibly useful lemmas that are definitely in the bag
- The multidimensional Sperner theorem
- Line-free sets correlate locally with complexity-1 sets (Article not finished, so lemma not yet "in the bag".)
- 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.
- H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem“, J. Anal. Math. 57 (1991), 64–119.
- R. McCutcheon, “The conclusion of the proof of the density Hales-Jewett theorem for k=3“, unpublished.
- A. Hales, R. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 1963 222--229. MR143712
- N. Hindman, E. Tressler, "The first non-trivial Hales-Jewett number is four", preprint.
- P. Matet, "Shelah's proof of the Hales-Jewett theorem revisited", European J. Combin. 28 (2007), no. 6, 1742--1745. MR2339499
- S. Shelah, "Primitive recursive bounds for van der Waerden numbers", J. Amer. Math. Soc. 1 (1988), no. 3, 683--697. MR 929498
- E. Croot, "Szemeredi's theorem on three-term progressions, at a glance, preprint.
- M. Elkin, "An Improved Construction of Progression-Free Sets ", preprint.
- B. Green, J. Wolf, "A note on Elkin's improvement of Behrend's construction", preprint.
- K. O'Bryant, "Sets of integers that do not contain long arithmetic progressions", preprint.
Triangles and corners
- M. Ajtai, E. Szemerédi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar. 9 (1974), 9--11 (1975). MR369299
- 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
- J. Solymosi, A note on a question of Erdős and Graham, Combin. Probab. Comput. 13 (2004), no. 2, 263--267. MR 2047239
- P. Keevash, "Shadows and intersections: stability and new proofs", preprint.