Abstract
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 language | English (US) |
---|---|
Journal | Electronic Journal of Combinatorics |
Volume | 10 |
Issue number | 1 R |
DOIs | |
State | Published - Oct 13 2003 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics