Abstract
We present alternative proofs of density versions of some combinatorial partition theorems originally obtained by E. Szemerédi, H. Furstenberg and Y. Katznelson. These proofs are based on an extremal hypergraph result which was recently obtained independently by W. T. Gowers and B. Nagle, V. Rödl, M. Schacht, J. Skokan by extending Szemerédi’s regularity lemma to hypergraphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Frankl and V. Rödl,Extremal problems on set systems, Random Structures & Algorithms20 (2002), 131–164.
H. Furstenberg,Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, Journal d’Analyse Mathématique31 (1977), 204–256.
H. Furstenberg and Y. Katznelson,An ergodic Szemerédi theorem for commuting transformations, Journal d’Analyse Mathématique34 (1978), 275–291.
H. Furstenberg and Y. Katznelson,An ergodic Szemerédi theorem for IP-systems and combinatorial theory, Journal d’Analyse Mathématique45 (1985), 117–168.
H. Furstenberg and Y. Katznelson,A density version of the Hales-Jewett theorem, Journal d’Analyse Mathématique57 (1991), 64–119.
W. T. Gowers,Hypergraph regularity and the multidimensional Szemerédi theorem, submitted.
W. T. Gowers,A new proof of Szemerédi’s theorem, Geometric and Functional Analysis11 (2001), 465–588.
A. W. Hales and R. I. Jewett,Regularity and positional games, Transactions of the American Mathematical Society106 (1963), 222–229.
B. Nagle, V. Rödl and M. Schacht,The counting lemma for regula k-uniform hypergraphs, Random Structures & Algorithms, to appear.
V. Rödl and J. Skokan,Applications of the regularity lemma for uniform hypergraphs, Random Structures & Algorithms, to appear.
V. Rödl and J. Skokan,Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms25 (2004), 1–42.
J. Solymosi,A− note on a question of Erdős and Graham, Combinatorics, Probability and Computing13 (2004), 263–267.
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.
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.
T. Tao,A quantitative ergodic theory proof of Szemerédi’s theorem, submitted.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research was partially supported by NSF Grant DMS 0300529.
Research was partially supported by the Deutsche Forschungsgemeinschaft within the European graduate program ‘Combinatorics, Geometry, and Computation’ (No. GRK 588/2) and by grant SCHA 1263/1-1.
Research was supported by a scholarship from CAPES, Brazil.
Research was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027.
Rights and permissions
About this article
Cite this article
Rödl, V., Tengan, E., Schacht, M. et al. Density theorems and extremal hypergraph problems. Isr. J. Math. 152, 371–380 (2006). https://doi.org/10.1007/BF02771992
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02771992