A Characterization for Sparse $\varepsilon$-Regular Pairs

Abstract

We are interested in $(\varepsilon)$-regular bipartite graphs which are the central objects in the regularity lemma of Szemerédi for sparse graphs. A bipartite graph $G=(A\uplus B,E)$ with density $p={|E|}/({|A||B|})$ is $(\varepsilon)$-regular if for all sets $A'\subseteq A$ and $B'\subseteq B$ of size $|A'|\geq \varepsilon|A|$ and $|B'|\geq \varepsilon |B|$, it holds that $\left| {e_G(A',B')}/{(|A'||B'|)}- p\right| \leq \varepsilon p$. In this paper we prove a characterization for $(\varepsilon)$-regularity. That is, we give a set of properties that hold for each $(\varepsilon)$-regular graph, and conversely if the properties of this set hold for a bipartite graph, then the graph is $f(\varepsilon)$-regular for some appropriate function $f$ with $f(\varepsilon)\rightarrow 0$ as $\varepsilon\rightarrow 0$. The properties of this set concern degrees of vertices and common degrees of vertices with sets of size $\Theta(1/p)$ where $p$ is the density of the graph in question.