Matrix-Free Proof of a Regularity Characterization

Abstract

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