×

Density theorems and extremal hypergraph problems. (English) Zbl 1127.05055

The goal of this clearly written, nice paper is to give new, qualitative proofs for the density versions of some combinatorial partition theorems by Szemerédi, Furstenberg and Katznelson. The main tool of the investigation is the so-called removal lemma, proved by Gowers and, independently, by Nagle, Rödl, Schacht and Sokan.

MSC:

05C35 Extremal problems in graph theory
05C65 Hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Frankl and V. Rödl,Extremal problems on set systems, Random Structures & Algorithms20 (2002), 131–164. · Zbl 0995.05141 · doi:10.1002/rsa.10017
[2] H. Furstenberg,Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, Journal d’Analyse Mathématique31 (1977), 204–256. · Zbl 0347.28016 · doi:10.1007/BF02813304
[3] H. Furstenberg and Y. Katznelson,An ergodic Szemerédi theorem for commuting transformations, Journal d’Analyse Mathématique34 (1978), 275–291. · Zbl 0426.28014 · doi:10.1007/BF02790016
[4] H. Furstenberg and Y. Katznelson,An ergodic Szemerédi theorem for IP-systems and combinatorial theory, Journal d’Analyse Mathématique45 (1985), 117–168. · Zbl 0605.28012 · doi:10.1007/BF02792547
[5] H. Furstenberg and Y. Katznelson,A density version of the Hales-Jewett theorem, Journal d’Analyse Mathématique57 (1991), 64–119. · Zbl 0770.05097
[6] W. T. Gowers,Hypergraph regularity and the multidimensional Szemerédi theorem, submitted. · Zbl 1159.05052
[7] W. T. Gowers,A new proof of Szemerédi’s theorem, Geometric and Functional Analysis11 (2001), 465–588. · Zbl 1028.11005 · doi:10.1007/s00039-001-0332-9
[8] A. W. Hales and R. I. Jewett,Regularity and positional games, Transactions of the American Mathematical Society106 (1963), 222–229. · Zbl 0113.14802 · doi:10.1090/S0002-9947-1963-0143712-1
[9] B. Nagle, V. Rödl and M. Schacht,The counting lemma for regula k-uniform hypergraphs, Random Structures & Algorithms, to appear. · Zbl 1093.05045
[10] V. Rödl and J. Skokan,Applications of the regularity lemma for uniform hypergraphs, Random Structures & Algorithms, to appear.
[11] V. Rödl and J. Skokan,Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms25 (2004), 1–42. · Zbl 1046.05042 · doi:10.1002/rsa.20017
[12] J. Solymosi,Anote on a question of Erdos and Graham, Combinatorics, Probability and Computing13 (2004), 263–267. · Zbl 1049.05077 · doi:10.1017/S0963548303005959
[13] E. Szemerédi,On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica27 (1975), 199–245, Collection of articles in memory of Jurii Vladimirovič Linnik. · Zbl 0303.10056
[14] E. Szemerédi,Regular partitions of graphs, inProblèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399–401.
[15] T. Tao,A quantitative ergodic theory proof of Szemerédi’s theorem, submitted.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.