A new proof of the density Hales-Jewett theorem

Abstract

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 Erdős and Turán in 1936, proved by Szemerédi in 1975, and given a different proof by Furstenberg in 1977. The Hales-Jewett theorem has a density version as well, proved by Furstenberg and Katznelson in 1991 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.

• [AS74] 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.
@article {AS74, MRKEY = {0369299},   AUTHOR = {Ajtai, M. and Szemer{é}di, E.},   TITLE = {Sets of lattice points that form no squares},   JOURNAL = {Stud. Sci. Math. Hungar.},   FJOURNAL = {Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences},   VOLUME = {9},   YEAR = {1974},   PAGES = {9--11 (1975)},   ISSN = {0081-6906},   MRCLASS = {10J25 (10E05)},   MRNUMBER = {0369299},   MRREVIEWER = {A. C. Woods},   ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},   ZBLNUMBER = {0303.10046},   }
• [Aus09] T. Austin, "Deducing the Density Hales–Jewett theorem from an infinitary removal lemma," J. Theoret. Probab., vol. 24, iss. 3, pp. 615-633, 2011.
@article{Aus09,   author={Austin, T.},   TITLE = {Deducing the Density {H}ales--{J}ewett theorem from an infinitary removal lemma},   JOURNAL = {J. Theoret. Probab.},   FJOURNAL = {Journal of Theoretical Probability},   VOLUME = {24},   YEAR = {2011},   NUMBER = {3},   PAGES = {615--633},   ISSN = {0894-9840},   CODEN = {JTPREO},   MRCLASS = {60G09 (05D05 37A50)},   MRNUMBER = {2822475},   ZBLNUMBER = {05948572},   DOI = {10.1007/s10959-011-0373-4},   }
• [Beh46] 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.
@article {Beh46, MRKEY = {0018694},   AUTHOR = {Behrend, F. A.},   TITLE = {On sets of integers which contain no three terms in arithmetical progression},   JOURNAL = {Proc. Nat. Acad. Sci. U. S. A.},   FJOURNAL = {Proceedings of the National Academy of Sciences of the United States of America},   VOLUME = {32},   YEAR = {1946},   PAGES = {331--332},   ISSN = {0027-8424},   MRCLASS = {10.0X},   MRNUMBER = {0018694},   MRREVIEWER = {P. Erd{ö}s},   ZBLNUMBER = {0060.10302},   }
• [BL96] 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.
@article {BL96, MRKEY = {1325795},   AUTHOR = {Bergelson, V. and Leibman, A.},   TITLE = {Polynomial extensions of van der {W}aerden's and {S}zemerédi's theorems},   JOURNAL = {J. Amer. Math. Soc.},   FJOURNAL = {Journal of the American Mathematical Society},   VOLUME = {9},   YEAR = {1996},   NUMBER = {3},   PAGES = {725--753},   ISSN = {0894-0347},   MRCLASS = {11B25 (05D10 28D05 54H20)},   MRNUMBER = {1325795},   MRREVIEWER = {Pierre Michel},   DOI = {10.1090/S0894-0347-96-00194-4},   ZBLNUMBER = {0870.11015},   }
• [Fur77] 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.
@article {Fur77, MRKEY = {0498471},   AUTHOR = {Furstenberg, H.},   TITLE = {Ergodic behavior of diagonal measures and a theorem of {S}zemerédi on arithmetic progressions},   JOURNAL = {J. Analyse Math.},   FJOURNAL = {Journal d'Analyse Mathématique},   VOLUME = {31},   YEAR = {1977},   PAGES = {204--256},   ISSN = {0021-7670},   MRCLASS = {10L10 (10K10 28A65)},   MRNUMBER = {0498471},   MRREVIEWER = {Francois Aribaud},   ZBLNUMBER = {0347.28016},   DOI = {10.1007/BF02813304},  }
• [FK78] H. Furstenberg and Y. Katznelson, "An ergodic Szemerédi theorem for commuting transformations," J. Analyse Math., vol. 34, pp. 275-291 (1979), 1978.
@article {FK78, MRKEY = {0531279},   AUTHOR = {Furstenberg, H. and Katznelson, Y.},   TITLE = {An ergodic {S}zemerédi theorem for commuting transformations},   JOURNAL = {J. Analyse Math.},   FJOURNAL = {Journal d'Analyse Mathématique},   VOLUME = {34},   YEAR = {1978},   PAGES = {275--291 (1979)},   ISSN = {0021-7670},   CODEN = {JOAMAV},   MRCLASS = {28D05 (10K50 10L02 10L20)},   MRNUMBER = {0531279},   MRREVIEWER = {J. H. B. Kemperman},   DOI = {10.1007/BF02790016},   ZBLNUMBER = {0426.28014},   }
• [FK85] 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.
@article {FK85, MRKEY = {0833409},   AUTHOR = {Furstenberg, H. and Katznelson, Y.},   TITLE = {An ergodic {S}zemerédi theorem for {IP}-systems and combinatorial theory},   JOURNAL = {J. Analyse Math.},   FJOURNAL = {Journal d'Analyse Mathématique},   VOLUME = {45},   YEAR = {1985},   PAGES = {117--168},   ISSN = {0021-7670},   CODEN = {JOAMAV},   MRCLASS = {28D05 (11B05 20M20)},   MRNUMBER = {0833409},   MRREVIEWER = {B. Volkmann},   DOI = {10.1007/BF02792547},   ZBLNUMBER = {0605.28012},   }
• [FK89] 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.
@article {FK89, MRKEY = {1001397},   AUTHOR = {Furstenberg, H. and Katznelson, Y.},   TITLE = {A density version of the {H}ales-{J}ewett theorem for {$k=3$}},   JOURNAL = {Discrete Math.},   FJOURNAL = {Discrete Mathematics},   VOLUME = {75},   YEAR = {1989},   NUMBER = {1-3},   PAGES = {227--241},   ISSN = {0012-365X},   CODEN = {DSMHA4},   MRCLASS = {05A05 (11B83 11K99 28D05)},   MRNUMBER = {1001397},   MRREVIEWER = {R. L. Graham},   DOI = {10.1016/0012-365X(89)90089-7},   ZBLNUMBER = {0697.05006},   }
• [FK89a] H. Furstenberg and Y. Katznelson, "Idempotents in compact semigroups and Ramsey theory," Israel J. Math., vol. 68, iss. 3, pp. 257-270, 1989.
@article {FK89a, MRKEY = {1039473},   AUTHOR = {Furstenberg, H. and Katznelson, Y.},   TITLE = {Idempotents in compact semigroups and {R}amsey theory},   JOURNAL = {Israel J. Math.},   FJOURNAL = {Israel Journal of Mathematics},   VOLUME = {68},   YEAR = {1989},   NUMBER = {3},   PAGES = {257--270},   ISSN = {0021-2172},   CODEN = {ISJMAP},   MRCLASS = {05D10 (22A15 54H15)},   MRNUMBER = {1039473},   MRREVIEWER = {N. Hindman},   DOI = {10.1007/BF02764984},   ZBLNUMBER = {0714.05059},   }
• [FK91] H. Furstenberg and Y. Katznelson, "A density version of the Hales-Jewett theorem," J. Anal. Math., vol. 57, pp. 64-119, 1991.
@article {FK91, MRKEY = {1191743},   AUTHOR = {Furstenberg, H. and Katznelson, Y.},   TITLE = {A density version of the {H}ales-{J}ewett theorem},   JOURNAL = {J. Anal. Math.},   FJOURNAL = {Journal d'Analyse Mathématique},   VOLUME = {57},   YEAR = {1991},   PAGES = {64--119},   ISSN = {0021-7670},   CODEN = {JOAMAV},   MRCLASS = {28D05 (11B25)},   MRNUMBER = {1191743},   MRREVIEWER = {B. Volkmann},   ZBLNUMBER = {0770.05097},   }
• [FKO82] 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.
@article {FKO82, MRKEY = {0670131},   AUTHOR = {Furstenberg, H. and Katznelson, Y. and Ornstein, D.},   TITLE = {The ergodic theoretical proof of {S}zemerédi's theorem},   JOURNAL = {Bull. Amer. Math. Soc.},   FJOURNAL = {American Mathematical Society. Bulletin. New Series},   VOLUME = {7},   YEAR = {1982},   NUMBER = {3},   PAGES = {527--552},   ISSN = {0273-0979},   CODEN = {BAMOAD},   MRCLASS = {28D05 (10L20)},   MRNUMBER = {0670131},   MRREVIEWER = {V. Drobot},   DOI = {10.1090/S0273-0979-1982-15052-2},   ZBLNUMBER = {0523.28017},   }
• [Gow01] W. T. Gowers, "A new proof of Szemerédi’s theorem," Geom. Funct. Anal., vol. 11, iss. 3, pp. 465-588, 2001.
@article {Gow01, MRKEY = {1844079},   AUTHOR = {Gowers, W. T.},   TITLE = {A new proof of {S}zemerédi's theorem},   JOURNAL = {Geom. Funct. Anal.},   FJOURNAL = {Geometric and Functional Analysis},   VOLUME = {11},   YEAR = {2001},   NUMBER = {3},   PAGES = {465--588},   ISSN = {1016-443X},   CODEN = {GFANFB},   MRCLASS = {11B25 (11K38 11K45)},   MRNUMBER = {1844079},   MRREVIEWER = {Hillel Furstenberg},   DOI = {10.1007/s00039-001-0332-9},   ZBLNUMBER = {1028.11005},   }
• [Gow06] W. T. Gowers, "Quasirandomness, counting and regularity for 3-uniform hypergraphs," Combin. Probab. Comput., vol. 15, iss. 1-2, pp. 143-184, 2006.
@article {Gow06, MRKEY = {2195580},   AUTHOR = {Gowers, W. T.},   TITLE = {Quasirandomness, counting and regularity for 3-uniform hypergraphs},   JOURNAL = {Combin. Probab. Comput.},   FJOURNAL = {Combinatorics, Probability and Computing},   VOLUME = {15},   YEAR = {2006},   NUMBER = {1-2},   PAGES = {143--184},   ISSN = {0963-5483},   MRCLASS = {05D05 (05C35 05C65)},   MRNUMBER = {2195580},   MRREVIEWER = {J{ó}zsef Solymosi},   DOI = {10.1017/S0963548305007236},   ZBLNUMBER = {1082.05081},   }
• [Gow07] W. T. Gowers, "Hypergraph regularity and the multidimensional Szemerédi theorem," Ann. of Math., vol. 166, iss. 3, pp. 897-946, 2007.
@article {Gow07, MRKEY = {2373376},   AUTHOR = {Gowers, W. T.},   TITLE = {Hypergraph regularity and the multidimensional {S}zemerédi theorem},   JOURNAL = {Ann. of Math.},   FJOURNAL = {Annals of Mathematics. Second Series},   VOLUME = {166},   YEAR = {2007},   NUMBER = {3},   PAGES = {897--946},   ISSN = {0003-486X},   CODEN = {ANMAAH},   MRCLASS = {05D10 (05C30 05C35 05C55 05C80 28D15)},   MRNUMBER = {2373376},   MRREVIEWER = {G{á}bor N. S{á}rk{ö}zy},   DOI = {10.4007/annals.2007.166.897},   ZBLNUMBER = {1159.05052},   }
• [Gow10] 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.
@incollection{Gow10,   author = {Gowers, W. T.},   TITLE = {Polymath and the density {H}ales-{J}ewettt theorem},   BOOKTITLE={An Irregular Mind: {S}zemerédi is 70},   PUBLISHER={Springer-Verlag},   ADDRESS={New York},   YEAR={2010},   PAGES={659--687},   ZBLNUMBER = {1223.05305},   DOI = {10.1007/978-3-642-14444-8},  }
• [GRS99] 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.
@article {GRS99, MRKEY = {1723801},   AUTHOR = {Gunderson, David S. and R{ö}dl, Vojt{ě}ch and Sidorenko, Alexander},   TITLE = {Extremal problems for sets forming {B}oolean algebras and complete partite hypergraphs},   JOURNAL = {J. Combin. Theory Ser. A},   FJOURNAL = {Journal of Combinatorial Theory. Series A},   VOLUME = {88},   YEAR = {1999},   NUMBER = {2},   PAGES = {342--367},   ISSN = {0097-3165},   CODEN = {JCBTA7},   MRCLASS = {05C65 (05D05)},   MRNUMBER = {1723801},   MRREVIEWER = {Andr{á}s Gy{á}rf{á}s},   DOI = {10.1006/jcta.1999.2973},   ZBLNUMBER = {0939.05079},   }
• [HJ63] A. W. Hales and R. I. Jewett, "Regularity and positional games," Trans. Amer. Math. Soc., vol. 106, pp. 222-229, 1963.
@article {HJ63, MRKEY = {0143712},   AUTHOR = {Hales, A. W. and Jewett, R. I.},   TITLE = {Regularity and positional games},   JOURNAL = {Trans. Amer. Math. Soc.},   FJOURNAL = {Transactions of the American Mathematical Society},   VOLUME = {106},   YEAR = {1963},   PAGES = {222--229},   ISSN = {0002-9947},   MRCLASS = {05.55},   MRNUMBER = {0143712},   MRREVIEWER = {J. W. Moon},   ZBLNUMBER = {0113.14802},   }
• [LM08] M. T. Lacey and W. McClain, Three Dimensional Corners: A Box Norm Proof, 2008.
@misc{LM08,   author={Lacey, M. T. and McClain, W.},   TITLE={Three Dimensional Corners: A {B}ox {N}orm Proof},   URL={http://arxiv.org/abs/0804.3019},   YEAR={2008},  }
• [lub66] D. Lubell, "A short proof of Sperner’s lemma," J. Combinatorial Theory, vol. 1, p. 299, 1966.
@article {lub66, MRKEY = {0194348},   AUTHOR = {Lubell, D.},   TITLE = {A short proof of {S}perner's lemma},   JOURNAL = {J. Combinatorial Theory},   VOLUME = {1},   YEAR = {1966},   PAGES = {299},   MRCLASS = {05.04},   MRNUMBER = {0194348},   MRREVIEWER = {A. A. Armend{á}riz},   ZBLNUMBER = {0151.01503},   DOI = {10.1016/S0021-9800(66)80035-2},  }
• [NRS06] 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.
@article {NRS06, MRKEY = {2198495},   AUTHOR = {Nagle, Brendan and R{ö}dl, Vojt{ě}ch and Schacht, Mathias},   TITLE = {The counting lemma for regular {$k$}-uniform hypergraphs},   JOURNAL = {Random Structures Algorithms},   FJOURNAL = {Random Structures \& Algorithms},   VOLUME = {28},   YEAR = {2006},   NUMBER = {2},   PAGES = {113--179},   ISSN = {1042-9832},   MRCLASS = {05C35 (05C65)},   MRNUMBER = {2198495},   MRREVIEWER = {Jozef Skokan},   DOI = {10.1002/rsa.20117},   ZBLNUMBER = {1093.05045},   }
• [Pol09] 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.
@incollection{Pol09,   author={Polymath, D. H. J.},   TITLE={Density {H}ales-{J}ewett and {M}oser numbers},   BOOKTITLE={An Irregular Mind: {S}zemerédi is 70},   PUBLISHER={Springer-Verlag},   ADDRESS={New York},   YEAR={2010},   PAGES={689--753},   ZBLNUMBER = {05853080},   DOI = {10.1007/978-3-642-14444-8},  }
• [RS07a] V. Rödl and M. Schacht, "Regular partitions of hypergraphs: regularity lemmas," Combin. Probab. Comput., vol. 16, iss. 6, pp. 833-885, 2007.
@article {RS07a, MRKEY = {2351688},   AUTHOR = {R{ö}dl, Vojt{ě}ch and Schacht, Mathias},   TITLE = {Regular partitions of hypergraphs: regularity lemmas},   JOURNAL = {Combin. Probab. Comput.},   FJOURNAL = {Combinatorics, Probability and Computing},   VOLUME = {16},   YEAR = {2007},   NUMBER = {6},   PAGES = {833--885},   ISSN = {0963-5483},   MRCLASS = {05C65 (05C35 05C70 05D05 05D10)},   MRNUMBER = {2351688},   MRREVIEWER = {G{á}bor N. S{á}rk{ö}zy},   ZBLNUMBER = {1206.05071},   DOI = {10.1017/S0963548307008565},  }
• [RS07b] V. Rödl and M. Schacht, "Regular partitions of hypergraphs: counting lemmas," Combin. Probab. Comput., vol. 16, iss. 6, pp. 887-901, 2007.
@article {RS07b, MRKEY = {2351689},   AUTHOR = {R{ö}dl, Vojt{ě}ch and Schacht, Mathias},   TITLE = {Regular partitions of hypergraphs: counting lemmas},   JOURNAL = {Combin. Probab. Comput.},   FJOURNAL = {Combinatorics, Probability and Computing},   VOLUME = {16},   YEAR = {2007},   NUMBER = {6},   PAGES = {887--901},   ISSN = {0963-5483},   MRCLASS = {05C65 (05C30 05C70)},   MRNUMBER = {2351689},   MRREVIEWER = {Norihide Tokushige},   ZBLNUMBER = {1206.05072},   DOI = {10.1017/S0963548307008553},  }
• [RS04] V. Rödl and J. Skokan, "Regularity lemma for $k$-uniform hypergraphs," Random Structures Algorithms, vol. 25, iss. 1, pp. 1-42, 2004.
@article {RS04, MRKEY = {2069663},   AUTHOR = {R{ö}dl, Vojt{ě}ch and Skokan, Jozef},   TITLE = {Regularity lemma for {$k$}-uniform hypergraphs},   JOURNAL = {Random Structures Algorithms},   FJOURNAL = {Random Structures \& Algorithms},   VOLUME = {25},   YEAR = {2004},   NUMBER = {1},   PAGES = {1--42},   ISSN = {1042-9832},   MRCLASS = {05D05 (05C65 05C75 60C05)},   MRNUMBER = {2069663},   MRREVIEWER = {W. G. Brown},   DOI = {10.1002/rsa.20017},   ZBLNUMBER = {1046.05042},   }
• [RS06] 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.
@article {RS06, MRKEY = {2198496},   AUTHOR = {R{ö}dl, Vojt{ě}ch and Skokan, Jozef},   TITLE = {Applications of the regularity lemma for uniform hypergraphs},   JOURNAL = {Random Structures Algorithms},   FJOURNAL = {Random Structures \& Algorithms},   VOLUME = {28},   YEAR = {2006},   NUMBER = {2},   PAGES = {180--194},   ISSN = {1042-9832},   MRCLASS = {05C35 (05C65)},   MRNUMBER = {2198496},   MRREVIEWER = {Jen{ő} Lehel},   DOI = {10.1002/rsa.20108},   ZBLNUMBER = {1087.05031},   }
• [Rot53] K. F. Roth, "On certain sets of integers," J. London Math. Soc., vol. 28, pp. 104-109, 1953.
@article {Rot53, MRKEY = {0051853},   AUTHOR = {Roth, K. F.},   TITLE = {On certain sets of integers},   JOURNAL = {J. London Math. Soc.},   FJOURNAL = {Journal of the London Mathematical Society. Second Series},   VOLUME = {28},   YEAR = {1953},   PAGES = {104--109},   ISSN = {0024-6107},   MRCLASS = {10.0X},   MRNUMBER = {0051853},   MRREVIEWER = {P. Erd{ö}s},   ZBLNUMBER = {0050.04002},   DOI = {10.1112/jlms/s1-28.1.104},  }
• [Shk06b] I. D. Shkredov, "On a generalization of Szemerédi’s theorem," Proc. London Math. Soc., vol. 93, iss. 3, pp. 723-760, 2006.
@article {Shk06b, MRKEY = {2266965},   AUTHOR = {Shkredov, I. D.},   TITLE = {On a generalization of {S}zemerédi's theorem},   JOURNAL = {Proc. London Math. Soc.},   FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},   VOLUME = {93},   YEAR = {2006},   NUMBER = {3},   PAGES = {723--760},   ISSN = {0024-6115},   CODEN = {PLMTAL},   MRCLASS = {11B25 (37A45)},   MRNUMBER = {2266965},   MRREVIEWER = {Randall McCutcheon},   DOI = {10.1017/S0024611506015991},   ZBLNUMBER = {1194.11024},   }
• [Shk06a] I. D. Shkredov, "On a problem of Gowers," Izv. Ross. Akad. Nauk Ser. Mat., vol. 70, iss. 2, pp. 179-221, 2006.
@article {Shk06a, MRKEY = {2223244},   AUTHOR = {Shkredov, I. D.},   TITLE = {On a problem of {G}owers},   JOURNAL = {Izv. Ross. Akad. Nauk Ser. Mat.},   FJOURNAL = {Rossiĭskaya Akademiya Nauk. Izvestiya. Seriya Matematicheskaya},   VOLUME = {70},   YEAR = {2006},   NUMBER = {2},   PAGES = {179--221},   ISSN = {0373-2436},   MRCLASS = {11B75},   MRNUMBER = {2223244},   MRREVIEWER = {Serge{\u\i} V. Konyagin},   DOI = {10.1070/IM2006v070n02ABEH002316},   ZBLNUMBER = {1149.11006},   }
• [Spe28] E. Sperner, "Ein Satz über Untermengen einer endlichen Menge," Math. Z., vol. 27, iss. 1, pp. 544-548, 1928.
@article {Spe28, MRKEY = {1544925},   AUTHOR = {Sperner, Emanuel},   TITLE = {Ein {S}atz über {U}ntermengen einer endlichen {M}enge},   JOURNAL = {Math. Z.},   FJOURNAL = {Mathematische Zeitschrift},   VOLUME = {27},   YEAR = {1928},   NUMBER = {1},   PAGES = {544--548},   ISSN = {0025-5874},   CODEN = {MAZEAX},   MRCLASS = {Contributed Item},   MRNUMBER = {1544925},   DOI = {10.1007/BF01171114},   JFMNUMBER = {54.0090.06},  }
• [Sze75] E. Szemerédi, "On sets of integers containing no $k$ elements in arithmetic progression," Acta Arith., vol. 27, pp. 199-245, 1975.
@article {Sze75, MRKEY = {0369312},   AUTHOR = {Szemer{é}di, E.},   TITLE = {On sets of integers containing no {$k$} elements in arithmetic progression},   JOURNAL = {Acta Arith.},   FJOURNAL = {Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica},   VOLUME = {27},   YEAR = {1975},   PAGES = {199--245},   ISSN = {0065-1036},   MRCLASS = {10L10},   MRNUMBER = {0369312},   MRREVIEWER = {S. L. G. Choi},   ZBLNUMBER = {0303.10056},   }
• [Tao06] T. Tao, "A quantitative ergodic theory proof of Szemerédi’s theorem," Electron. J. Combin., vol. 13, iss. 1, p. 99, 2006.
@article {Tao06, MRKEY = {2274314},   AUTHOR = {Tao, Terence},   TITLE = {A quantitative ergodic theory proof of {S}zemerédi's theorem},   JOURNAL = {Electron. J. Combin.},   FJOURNAL = {Electronic Journal of Combinatorics},   VOLUME = {13},   YEAR = {2006},   NUMBER = {1},   PAGES = {Research Paper 99, 49 pp.},   ISSN = {1077-8926},   MRCLASS = {37A45 (11B25)},   MRNUMBER = {2274314},   MRREVIEWER = {Bryna Kra},   URL = {http://www.combinatorics.org/Volume_13/Abstracts/v13i1r99.html},   ZBLNUMBER = {1127.11011},  }
• [Tao07] 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.
@article {Tao07, MRKEY = {2373263},   AUTHOR = {Tao, Terence},   TITLE = {A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma},   JOURNAL = {J. Anal. Math.},   FJOURNAL = {Journal d'Analyse Mathématique},   VOLUME = {103},   YEAR = {2007},   PAGES = {1--45},   ISSN = {0021-7670},   CODEN = {JOAMAV},   MRCLASS = {60C05 (05C35 05C65 05C75 05C80 37A25)},   MRNUMBER = {2373263},   MRREVIEWER = {Michele Zito},   DOI = {10.1007/s11854-008-0001-0},   ZBLNUMBER = {1146.05038},   }
• [vdW27] B. L. van der Waerden, "Beweis einer Baudetschen Vermutung," Nieuw Archief voor Wiskunde, vol. 15, pp. 212-216, 1927.
@article{vdW27,   author={van~der Waerden, B. L.},   TITLE={Beweis einer {{B}audetschen} {V}ermutung},   JOURNAL={Nieuw Archief voor Wiskunde},   VOLUME={15},   YEAR={1927},   PAGES={212--216},   JFMNUMBER = {53.0073.12},  }

Authors

D. H. J. Polymath