Hypergraph regularity and the multidimensional Szemerédi theorem. (English) Zbl 1159.05052

In recent years there is huge activity on how to generalize Szemerédi’s Regularity and Removal lemmas for hypergraphs. There are different approaches, different results, even different definitions. (See for example [V. Rödl and J. Skokan, Random Struct. Algorithms 25, No. 1, 1–42 (2004; Zbl 1046.05042), B. Nagle, V. Rödl, and M. Schacht, ibid. 28, 113–179 (2006; Zbl 1093.05045); T. Tao, J. Comb. Theory, Ser. A 113, 1257–1280 (2006; Zbl 1105.05052 ); G. Elek and B. Szegedy, Limits of hypergraphs, regularity and removal lemmas. A non-standard approach. http://arxiv1.library.cornell.edu/abs/0705.2179v1]). The paper under review develops its own versions of the Regularity and Removal lemmas for hypergraphs, and as application it gives the first combinatorial proofs for the multidimensional Szemerédi theorem (and also providing an explicit bound).


05D10 Ramsey theory
05C65 Hypergraphs
05C30 Enumeration in graph theory
05C35 Extremal problems in graph theory
05C55 Generalized Ramsey theory
05C80 Random graphs (graph-theoretic aspects)
28D15 General groups of measure-preserving transformations
Full Text: DOI arXiv Link