×
Polymath, D. H. J.

A new proof of the density Hales-Jewett theorem. (English) Zbl 1267.11010

Ann. Math. (2) 175, No. 3, 1283-1327 (2012).
Summary: The Hales-Jewett theorem asserts that for every \(r\) and every \(k\) there exists \(n\) such that every \(r\)-colouring of the \(n\)-dimensional grid \(\{1, \dots, k\}^n\) contains a monochromatic combinatorial line. This result is a generalization of van der Waerden’s theorem, and it is one of the fundamental results of Ramsey theory. The theorem of van der Waerden has a famous density version, conjectured by P. Erdős and P. Turán in 1936, proved by E. Szemerédi [Acta Arith. 27, 199–245 (1975; Zbl 0303.10056)], and given a different proof by H. Furstenberg in [J. Anal. Math. 31, 204–256 (1977; Zbl 0347.28016 )].
The Hales-Jewett theorem has a density version as well, proved by H. Furstenberg and Y. Katznelson in [J. Anal. Math. 57, 64–119 (1991; Zbl 0770.05097)] by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemerédi’s theorem. In this paper, we give the first elementary proof of the theorem of Furstenberg and Katznelson and the first to provide a quantitative bound on how large \(n\) needs to be.
In particular, we show that a subset of \(\{1,2,3\}^n\) of density \(\delta\) contains a combinatorial line if \(n\) is at least as big as a tower of 2s of height \(O(1/\delta^2)\). Our proof is surprisingly simple: indeed, it gives arguably the simplest known proof of Szemerédi’s theorem.
Note: D.H.J. Polymath is the assumed collective pseudonym for the authors of a number of papers which have arisen as a result of the polymath project initated by Gowers.

Cited in 1 Review
Cited in 29 Documents

MSC:

11B25 Arithmetic progressions
05D10 Ramsey theory

Keywords:

Szemerédi’s theorem; van der Waerden’s theorem

Citations:

Zbl 0303.10056; Zbl 0347.28016; Zbl 0770.05097
PDF BibTeX XML Cite
\textit{D. H. J. Polymath}, Ann. Math. (2) 175, No. 3, 1283--1327 (2012; Zbl 1267.11010)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] M. Ajtai and E. Szemerédi, ”Sets of lattice points that form no squares,” Stud. Sci. Math. Hungar., vol. 9, pp. 9-11 (1975), 1974. · Zbl 0303.10046
[2] T. Austin, ”Deducing the Density Hales-Jewett theorem from an infinitary removal lemma,” J. Theoret. Probab., vol. 24, iss. 3, pp. 615-633, 2011. · Zbl 1235.60031
[3] F. A. Behrend, ”On sets of integers which contain no three terms in arithmetical progression,” Proc. Nat. Acad. Sci. U. S. A., vol. 32, pp. 331-332, 1946. · Zbl 0060.10302
[4] V. Bergelson and A. Leibman, ”Polynomial extensions of van der Waerden’s and Szemerédi’s theorems,” J. Amer. Math. Soc., vol. 9, iss. 3, pp. 725-753, 1996. · Zbl 0870.11015
[5] H. Furstenberg, ”Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions,” J. Analyse Math., vol. 31, pp. 204-256, 1977. · Zbl 0347.28016
[6] H. Furstenberg and Y. Katznelson, ”An ergodic Szemerédi theorem for commuting transformations,” J. Analyse Math., vol. 34, pp. 275-291 (1979), 1978. · Zbl 0426.28014
[7] H. Furstenberg and Y. Katznelson, ”An ergodic Szemerédi theorem for IP-systems and combinatorial theory,” J. Analyse Math., vol. 45, pp. 117-168, 1985. · Zbl 0605.28012
[8] H. Furstenberg and Y. Katznelson, ”A density version of the Hales-Jewett theorem for \(k=3\),” Discrete Math., vol. 75, iss. 1-3, pp. 227-241, 1989. · Zbl 0697.05006
[9] H. Furstenberg and Y. Katznelson, ”Idempotents in compact semigroups and Ramsey theory,” Israel J. Math., vol. 68, iss. 3, pp. 257-270, 1989. · Zbl 0714.05059
[10] H. Furstenberg and Y. Katznelson, ”A density version of the Hales-Jewett theorem,” J. Anal. Math., vol. 57, pp. 64-119, 1991. · Zbl 0770.05097
[11] H. Furstenberg, Y. Katznelson, and D. Ornstein, ”The ergodic theoretical proof of Szemerédi’s theorem,” Bull. Amer. Math. Soc., vol. 7, iss. 3, pp. 527-552, 1982. · Zbl 0523.28017
[12] W. T. Gowers, ”A new proof of Szemerédi’s theorem,” Geom. Funct. Anal., vol. 11, iss. 3, pp. 465-588, 2001. · Zbl 1028.11005
[13] W. T. Gowers, ”Quasirandomness, counting and regularity for 3-uniform hypergraphs,” Combin. Probab. Comput., vol. 15, iss. 1-2, pp. 143-184, 2006. · Zbl 1082.05081
[14] W. T. Gowers, ”Hypergraph regularity and the multidimensional Szemerédi theorem,” Ann. of Math., vol. 166, iss. 3, pp. 897-946, 2007. · Zbl 1159.05052
[15] W. T. Gowers, ”Polymath and the density Hales-Jewettt theorem,” in An Irregular Mind: Szemerédi is 70, New York: Springer-Verlag, 2010, pp. 659-687. · Zbl 1223.05305
[16] D. S. Gunderson, V. Rödl, and A. Sidorenko, ”Extremal problems for sets forming Boolean algebras and complete partite hypergraphs,” J. Combin. Theory Ser. A, vol. 88, iss. 2, pp. 342-367, 1999. · Zbl 0939.05079
[17] A. W. Hales and R. I. Jewett, ”Regularity and positional games,” Trans. Amer. Math. Soc., vol. 106, pp. 222-229, 1963. · Zbl 0113.14802
[18] M. T. Lacey and W. McClain, Three Dimensional Corners: A Box Norm Proof, 2008.
[19] D. Lubell, ”A short proof of Sperner’s lemma,” J. Combinatorial Theory, vol. 1, p. 299, 1966. · Zbl 0151.01503
[20] B. Nagle, V. Rödl, and M. Schacht, ”The counting lemma for regular \(k\)-uniform hypergraphs,” Random Structures Algorithms, vol. 28, iss. 2, pp. 113-179, 2006. · Zbl 1093.05045
[21] D. H. J. Polymath, ”Density Hales-Jewett and Moser numbers,” in An Irregular Mind: Szemerédi is 70, New York: Springer-Verlag, 2010, pp. 689-753. · Zbl 1239.05189
[22] V. Rödl and M. Schacht, ”Regular partitions of hypergraphs: regularity lemmas,” Combin. Probab. Comput., vol. 16, iss. 6, pp. 833-885, 2007. · Zbl 1206.05071
[23] V. Rödl and M. Schacht, ”Regular partitions of hypergraphs: counting lemmas,” Combin. Probab. Comput., vol. 16, iss. 6, pp. 887-901, 2007. · Zbl 1206.05072
[24] V. Rödl and J. Skokan, ”Regularity lemma for \(k\)-uniform hypergraphs,” Random Structures Algorithms, vol. 25, iss. 1, pp. 1-42, 2004. · Zbl 1046.05042
[25] V. Rödl and J. Skokan, ”Applications of the regularity lemma for uniform hypergraphs,” Random Structures Algorithms, vol. 28, iss. 2, pp. 180-194, 2006. · Zbl 1087.05031
[26] K. F. Roth, ”On certain sets of integers,” J. London Math. Soc., vol. 28, pp. 104-109, 1953. · Zbl 0050.04002
[27] I. D. Shkredov, ”On a generalization of Szemerédi’s theorem,” Proc. London Math. Soc., vol. 93, iss. 3, pp. 723-760, 2006. · Zbl 1194.11024
[28] I. D. Shkredov, ”On a problem of Gowers,” Izv. Ross. Akad. Nauk Ser. Mat., vol. 70, iss. 2, pp. 179-221, 2006. · Zbl 1149.11006
[29] E. Sperner, ”Ein Satz über Untermengen einer endlichen Menge,” Math. Z., vol. 27, iss. 1, pp. 544-548, 1928. · JFM 54.0090.06
[30] E. Szemerédi, ”On sets of integers containing no \(k\) elements in arithmetic progression,” Acta Arith., vol. 27, pp. 199-245, 1975. · Zbl 0303.10056
[31] T. Tao, ”A quantitative ergodic theory proof of Szemerédi’s theorem,” Electron. J. Combin., vol. 13, iss. 1, p. 99, 2006. · Zbl 1127.11011
[32] T. Tao, ”A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma,” J. Anal. Math., vol. 103, pp. 1-45, 2007. · Zbl 1146.05038
[33] B. L. van der Waerden, ”Beweis einer Baudetschen Vermutung,” Nieuw Archief voor Wiskunde, vol. 15, pp. 212-216, 1927. · JFM 53.0073.12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.