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, suggested by Tim Gowers. The original proof of DHJ(3) used arguments from ergodic theory.
Useful background materials
Some background to the project can be found here. General discussion on massively collaborative "polymath" projects can be found here. A cheatsheet for editing the wiki may be found here. Finally, here is the general Wiki user's guide
- (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.
- 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.
- 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