Matrix-free proof of a regularity characterization

MaRDI QIDQ1422124zbMATH OpenFDO

Authors Andrzej Czygrinow, B. Nagle

Publication date 5 February 2004

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/123236, http://www.emis.de/journals/EJC/Volume_10/Abstracts/v10i1r39.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

regularity lemma

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Review text

Summary: The central concept in Szemerédi's powerful regularity lemma is the so-called \(\varepsilon\)-regular pair. A useful statement of \textit{N. Alon} et al. [J. Algorithms 16, 80-109 (1994; Zbl 0794.05119)] essentially equates the notion of an \(\varepsilon\)-regular pair with degree uniformity of vertices and pairs of vertices. The known proof of this characterization uses a clever matrix argument. This paper gives a simple proof of the characterization without appealing to the matrix argument of Alon et al. We show the \(\varepsilon\)-regular characterization follows from an application of Szemerédi's regularity lemma itself.

Recommendations

• A characterization for sparse -regular pairs
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Regularity lemmas for hypergraphs and quasi-randomness
• scientific article; zbMATH DE number 2086426
• A short proof of Gowers' lower bound for the regularity lemma

Cited in

(3)

• Short paths in \(\varepsilon \)-regular pairs and small diameter decompositions of dense graphs
• Hairer's reconstruction theorem without regularity structures
• A characterization for sparse -regular pairs

This page was built for publication: Matrix-free proof of a regularity characterization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422124)