# Main Page

## The Problem

Let [math][3]^n[/math] be the set of all length [math]n[/math] strings over the alphabet [math]1, 2, 3[/math]. A *combinatorial line* is a set of three points in [math][3]^n[/math], formed by taking a string with one or more wildcards [math]\ast[/math] in it, e.g., [math]112\!\ast\!\!1\!\ast\!\ast3\ldots[/math], and replacing those wildcards by [math]1, 2[/math] and [math]3[/math], respectively. In the example given, the resulting combinatorial line is: [math]\{ 11211113\ldots, 11221223\ldots, 11231333\ldots \}[/math]. A subset of [math][3]^n[/math] is said to be *line-free* if it contains no lines. Let [math]c_n[/math] be the size of the largest line-free subset of [math][3]^n[/math].

**[math]k=3[/math] Density Hales-Jewett (DHJ(3)) theorem:** [math]\lim_{n \rightarrow \infty} c_n/3^n = 0[/math]

The original proof of DHJ(3) used arguments from ergodic theory. The basic problem to be considered by the Polymath project is to explore a particular combinatorial approach to DHJ, suggested by Tim Gowers.

## 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

## Threads

- (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)

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

A spreadsheet containing the latest upper and lower bounds for [math]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:

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

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

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