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
    0 references
    0 references
    0 references
    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 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references