Main Page

The Problem

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

[math]\displaystyle{ k=3 }[/math] Density Hales-Jewett (DHJ(3)) theorem: [math]\displaystyle{ \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 consider by the Polymath project is to explore a particular combinatorial approach to DHJ, suggested by Tim Gowers. Some background to this project can be found here, and general discussion on massively collaborative "polymath" projects can be found here.

Threads

• (1-199) A combinatorial approach to density Hales-Jewett (inactive)
• (200-299) Upper and lower bounds for the density Hales-Jewett problem (active)
• (300-399) The triangle-removal approach (inactive)
• (400-499) Quasirandomness and obstructions to uniformity (final call)
• (500-599) TBA
• (600-699) A reading seminar on density Hales-Jewett (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]\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.

Here are some unsolved problems arising from the above threads.

Bibliography

1. M. Elkin, "An Improved Construction of Progression-Free Sets ", preprint.
2. 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.
3. H. Furstenberg, Y. Katznelson, “A density version of the Hales-Jewett theorem“, J. Anal. Math. 57 (1991), 64–119.
4. B. Green, J. Wolf, "A note on Elkin's improvement of Behrend's construction", preprint.
5. K. O'Bryant, "Sets of integers that do not contain long arithmetic progressions", preprint.
6. R. McCutcheon, “The conclusion of the proof of the density Hales-Jewett theorem for k=3“, unpublished.

Other resources

• Wiki user's guide