Main Page

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 (inactive)
(600-699) A reading seminar on density Hales-Jewett (inactive)
(700-799) Bounds for the first few density Hales-Jewett numbers, and related quantities (inactive)
(800-849) Brief review of polymath1 (inactive)
(850-899) DHJ(3): 851-899 (active)
(900-999) DHJ(3): 900-999 (Density Hales-Jewett type numbers) (active)

Here is a further list of blog posts related to the Polymath1 project. Here is wordpress's list. Here is a timeline of progress so far.

A spreadsheet containing the latest upper and lower bounds for [math]\displaystyle{ c_n }[/math] can be found here. Here are the proofs of our upper and lower bounds for these constants.

We are also collecting bounds for Fujimura's problem, motivated by a hyper-optimistic conjecture.

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.

Proof strategies

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

Related theorems

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

Complete proofs or detailed sketches of potentially useful results

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

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.

Coloring Hales-Jewett theorem

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

Roth's theorem

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

Behrend-type constructions

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

Kruskal-Katona theorem

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

Main Page

Contents

Useful background materials

Threads and further problems

Proof strategies

Related theorems

Important concepts related to possible proofs

Complete proofs or detailed sketches of potentially useful results

Attempts at proofs of DHJ(3)

Bibliography

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools