A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma (Q926374)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5279115
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma |
scientific article; zbMATH DE number 5279115 |
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
0 references
0 references
0 references
0.8313046097755432
0 references
0.8105851411819458
0 references
0.8016539216041565
0 references
0.7933666110038757
0 references
0.77860027551651
0 references