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

Stefanie Gerke ; Angelika Steger

The electronic journal of combinatorics, Tome 14 (2007)

Résumé

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.

Détail

DOI : 10.37236/923

Classification : 05C75, 05C80
Mots-clés : regularity lemma