
doi: 10.37236/1732
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.
Extremal problems in graph theory, regularity lemma, Random graphs (graph-theoretic aspects)
Extremal problems in graph theory, regularity lemma, Random graphs (graph-theoretic aspects)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
