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
Regularity Lemma
0 references
Removal Lemma
0 references
multidimensional Szemerédi theorem
0 references
Furstenberg-Katznelson's theorem
0 references