Matrix-free proof of a regularity characterization

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


The central concept in Szemerédi's powerful regularity lemma is the so-called ε-regular pair. A useful statement of Alon et al. essentially equates the notion of an ε-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 ε-regular characterization follows from an application of Szemerédi's regularity lemma itself.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Issue number1 R
StatePublished - Oct 13 2003

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Matrix-free proof of a regularity characterization'. Together they form a unique fingerprint.

Cite this