A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma (Q926374)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma |
scientific article |
Statements
A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma (English)
0 references
27 May 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}, Random Struct. Algorithms 28, 113--179 (2006; Zbl 1093.05045), \textit{W.T. Gowers}, Ann. Math. (2) 166, 897--946 (2007; Zbl 1159.05052), and \textit{G. Elek} and \textit{B. Szegedy}, Limits of hypergraphs, removal and regularity lemmas. A nonstandard approach. \url{http://arxiv1.library.cornell.edu/abs/0705.2179v1}]) The paper under review developed an infinitary analogous to the Furstenberg Correspondence Principle, which gives a new proof of the Removal Lemma, and which requires no Regularity Lemma. Then the paper discusses several applications of the method.
0 references
regularity lemma
0 references
removal lemma
0 references
Szemerédi theorem
0 references
Furstenberg correspondence principle
0 references