Hypergraph regularity and the multidimensional Szemerédi theorem (Q2482877)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Hypergraph regularity and the multidimensional Szemerédi theorem
scientific article

    Statements

    Hypergraph regularity and the multidimensional Szemerédi theorem (English)
    0 references
    25 April 2008
    0 references
    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 [\textit{V. Rödl} and \textit{J. Skokan}, Random Struct. Algorithms 25, No. 1, 1--42 (2004; Zbl 1046.05042), \textit{B. Nagle}, \textit{V. Rödl}, and \textit{M. Schacht}, ibid. 28, 113--179 (2006; Zbl 1093.05045); \textit{T. Tao}, J. Comb. Theory, Ser. A 113, 1257--1280 (2006; Zbl 1105.05052 ); \textit{G. Elek} and \textit{B. Szegedy}, Limits of hypergraphs, regularity and removal lemmas. A non-standard approach. \url{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).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    Regularity Lemma
    0 references
    Removal Lemma
    0 references
    multidimensional Szemerédi theorem
    0 references
    Furstenberg-Katznelson's theorem
    0 references
    0 references
    0 references
    0 references
    0 references