# Difference between revisions of "Main Page"

(→The Problem) |
(→Bibliography) |
||

Line 33: | Line 33: | ||

== Bibliography == | == Bibliography == | ||

− | + | Density Hales-Jewett | |

+ | |||

# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/hj43.pdf 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, “[http://math.stanford.edu/~katznel/hj43.pdf 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, “[http://math.stanford.edu/~katznel/dhj12.pdf A density version of the Hales-Jewett theorem]“, J. Anal. Math. 57 (1991), 64–119. | # H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/dhj12.pdf A density version of the Hales-Jewett theorem]“, J. Anal. Math. 57 (1991), 64–119. | ||

+ | # R. McCutcheon, “[http://www.msci.memphis.edu/~randall/preprints/HJk3.pdf The conclusion of the proof of the density Hales-Jewett theorem for k=3]“, unpublished. | ||

+ | |||

+ | Behrend-type constructions | ||

+ | |||

+ | # M. Elkin, "[http://arxiv.org/abs/0801.4310 An Improved Construction of Progression-Free Sets ]", preprint. | ||

# B. Green, J. Wolf, "[http://arxiv.org/abs/0810.0732 A note on Elkin's improvement of Behrend's construction]", preprint. | # B. Green, J. Wolf, "[http://arxiv.org/abs/0810.0732 A note on Elkin's improvement of Behrend's construction]", preprint. | ||

# K. O'Bryant, "[http://arxiv.org/abs/0811.3057 Sets of integers that do not contain long arithmetic progressions]", preprint. | # K. O'Bryant, "[http://arxiv.org/abs/0811.3057 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). [http://www.ams.org/mathscinet-getitem?mr=369299 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. [http://www.ams.org/mathscinet-getitem?mr=519318 MR519318] | ||

+ | # J. Solymosi, [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=206943 A note on a question of Erdős and Graham], Combin. Probab. Comput. 13 (2004), no. 2, 263--267. [http://www.ams.org/mathscinet-getitem?mr=2047239 MR 2047239] |

## Revision as of 16:37, 13 February 2009

## 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 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 (final call)
- (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 (arriving at station)

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.

Here are some unsolved problems arising from the above threads.

Here is a tidy problem page.

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