A characterization for sparse \(\varepsilon\)-regular pairs (Q870053)

Summary: We are interested in (\(\varepsilon\))-regular bipartite graphs which are the central objects in the regularity lemma of Szeméredi 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 \(|e_G(A',B')/(|A'||B'|)- p| \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)\to 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.