Main Page

2009-03-09T15:13:03Z

68.252.51.1:

== Threads and further problems==

* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* (200-299) [http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ Upper and lower bounds for the density Hales-Jewett problem] (inactive)
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (inactive)
* (500-599) [http://gowers.wordpress.com/2009/02/13/dhj-possible-proof-strategies/#more-441/ Possible proof strategies] (inactive)
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (inactive)
* (700-799) [http://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/ Bounds for the first few density Hales-Jewett numbers, and related quantities] (inactive)
* (800-849) [http://gowers.wordpress.com/2009/02/23/brief-review-of-polymath1/ Brief review of polymath1] (inactive)
* (850-899) [http://gowers.wordpress.com/2009/03/02/dhj3-851-899/ DHJ(3): 851-899] (active)
* (900-999) [http://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/ DHJ(3): 900-999 (Density Hales-Jewett type numbers)] (active)

[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list]. Here is a [[timeline]] of progress so far.

A spreadsheet containing the latest upper and lower bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg 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]].
* Use of [[equal-slices measure]].

== Related theorems ==

* [[Carlson's theorem]].
* The [[Carlson-Simpson theorem]].
* [[Folkman's theorem]].
* The [[Graham-Rothschild theorem]].
* The colouring [[Hales-Jewett theorem]].
* The [[Kruskal-Katona theorem]].
* [[Roth's theorem]].
* The [[IP-Szemerédi theorem]].
* [[Sperner's theorem]].
* [[Szemerédi's regularity lemma]].
* [[Szemerédi's theorem]].
* The [[triangle removal lemma]].

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

* [[Complexity of a set]]
* [[Concentration of measure]]
* [[Influence of variables]]
* [[Obstructions to uniformity]]
* [[Quasirandomness]]

==Complete proofs or detailed sketches of potentially useful results==

*[[Sperner's theorem|The multidimensional Sperner theorem]]
*[[Line-free sets correlate locally with complexity-1 sets]]
*[[Correlation with a 1-set implies correlation with a subspace]] (Not finished)
*[[Fourier-analytic_proof_of_Sperner|A Fourier-analytic proof of Sperner's theorem]]
*[[A second Fourier decomposition related to Sperner's theorem]]
*[[A Hilbert space lemma]]
*A [[Modification of the Ajtai-Szemerédi argument]]
*[[DHJ(k) implies multidimensional DHJ(k)]]

==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, “[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.
# 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.

[[Coloring Hales-Jewett theorem]]

# A. Hales, R. Jewett, [http://www.jstor.org/stable/1993764 Regularity and positional games], Trans. Amer. Math. Soc. 106 1963 222--229. [http://www.ams.org/mathscinet-getitem?mr=143712 MR143712]
# N. Hindman, E. Tressler, "[http://www.math.ucsd.edu/~etressle/hj32.pdf The first non-trivial Hales-Jewett number is four]", preprint.
# P. Matet, "[http://dx.doi.org/10.1016/j.ejc.2006.06.021 Shelah's proof of the Hales-Jewett theorem revisited]", European J. Combin. 28 (2007), no. 6, 1742--1745. [http://www.ams.org/mathscinet-getitem?mr=2339499 MR2339499]
# S. Shelah, "[http://www.jstor.org/stable/1990952 Primitive recursive bounds for van der Waerden numbers]", J. Amer. Math. Soc. 1 (1988), no. 3, 683--697. [http://www.ams.org/mathscinet-getitem?mr=929498 MR 929498]

[[Roth's theorem]]

# E. Croot, "[http://www.math.gatech.edu/~ecroot/szemeredi.pdf Szemeredi's theorem on three-term progressions, at a glance], preprint.

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

[[Kruskal-Katona theorem]]

# P. Keevash, "[http://arxiv.org/abs/0806.2023 Shadows and intersections: stability and new proofs]", preprint.

Polymath Wiki - User contributions [en]

Main Page