# 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]x[/math] in it, e.g., [math]112x1xx3\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 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 lower and upper bounds for [math]c_n[/math] can be found here.

Here are some unsolved problems arising from the above threads.

## Bibliography

- M. Elkin, "An Improved Construction of Progression-Free Sets ", preprint.
- 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.
- 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.
- R. McCutcheon, “The conclusion of the proof of the density Hales-Jewett theorem for k=3“, unpublished.