<p>Below is a long-winded answer, but <strong>tl;dr</strong> in the general case there is no hope for such a formulation, but for many of the particular classes of sparse graphs that have regularity lemmas this formulation exists.</p>

<p>For background, there are two popular versions of the SRL.  They are: for any fixed <span class="math-container">$\varepsilon &gt; 0$</span> and any <span class="math-container">$n$</span>-node graph <span class="math-container">$G = (V, E)$</span>, one can partition <span class="math-container">$V = V_0 \cup V_1 \cup \dots \cup V_p$</span> into <span class="math-container">$p = O_{\varepsilon}(1)$</span> parts so that ...</p>

<blockquote>
  <ul>
  <li><p><strong>(Combinatorial Phrasing)</strong> (1) <span class="math-container">$|V_0| \le \varepsilon n$</span> and the sizes of any <span class="math-container">$V_1, \dots, V_p$</span> differ by at most <span class="math-container">$1$</span> (<span class="math-container">$V_0$</span> is called the "exceptional set"), and (2) all but <span class="math-container">$\varepsilon p^2$</span> pairs of the remaining parts <span class="math-container">$(V_i, V_j)$</span> satisfy
  <span class="math-container">$$\left|d(S, T) - d(V_i, V_j)\right| &lt; \varepsilon \text{ for all } S \subseteq V_i, T \subseteq V_j$$</span>
  (here <span class="math-container">$d(\cdot, \cdot)$</span> gives the density between the parts, i.e. the fraction of edges that are present).</p></li>
  <li><p><strong>(Analytic Phrasing)</strong> Letting
  <span class="math-container">$$\mathop{disc}(V_i, V_j) := \max \limits_{S \subseteq  V_i, T \subseteq V_j} |V_i||V_j|\left|d(V_i, V_j) - d(S, T)\right|,$$</span>
  we have
  <span class="math-container">$$\sum \limits_{i, j =0}^p \mathop{disc}(V_i, V_j) &lt; \varepsilon n^2.$$</span></p></li>
  </ul>
</blockquote>

<p>The "combinatorial phrasing" (I just made these names up, they are not standard) is the original and probably more famous one, whereas the "analytic phrasing" is more modern and related to graph limits, etc (I think it was popularized <a href="http://web.cs.elte.hu/~lovasz/analyst.pdf" rel="nofollow noreferrer">here</a>).  To my eye the analytic one is the right formalization of "graph approximated by union of bipartite expanders," since it gives a control on the total "error" of such an approximation, and there is not an exceptional set in which to hide mass.  But at this point this is just cosmetic, because it's an easy but important lemma that these two phrasings are equivalent.  To get from Combinatorial to Analytic, just union bound the contribution to discrepancy of the irregular parts and exceptional set.  To get from Analytic to Combinatorial, just move any part that contributes too much discrepancy to the exceptional set and apply Markov's Inequality to control its mass.</p>

<p>Now to sparse regularity.  The goal of sparse regularity is to replace the <span class="math-container">$\varepsilon$</span> in the respective inequalities with <span class="math-container">$\varepsilon d(G)$</span>, where <span class="math-container">$d(G)$</span> is the fraction of all possible edges present in <span class="math-container">$G$</span>.  Critically, with this change, <strong>the two phrasings are no longer equivalent.</strong>  Rather, the Analytic phrasing is stronger: it still implies Combinatorial exactly as before, but Combinatorial does not generally imply Analytic, because (as anticipated in the OP) one can potentially hide a lot of density in the exceptional set or between the non-regular pairs of parts.  Indeed, this separation is formal: the lower bound graphs for the dense SRL (say, <a href="https://arxiv.org/abs/1403.1768" rel="nofollow noreferrer">this one</a>) imply that the Analytic Phrasing doesn't extend in general to sparse graphs, but the paper by Scott linked in the OP shows that the Combinatorial Phrasing actually does extend to all sparse graphs with no conditions.</p>

<p>The survey linked in the OP mostly talks about an SRL for "upper-regular" sparse graphs, which roughly means that the graph has no cuts that are denser than average by more than a constant factor.  For these particular graphs, the Combinatorial and Analytic phrasings are equivalent, because there can't be too much extra mass hidden in the exceptional parts so their contribution to discrepancy can be union bounded like in the dense case.  So these graphs have an "approximated by union of bipartite expanders" interpretation.</p>

<p>Finally, I should mention that there are many other hypotheses in the literature that also imply equivalence between these phrasings.  For example, <span class="math-container">$L_p$</span> Upper Regularity (defined <a href="https://arxiv.org/pdf/1401.2906.pdf" rel="nofollow noreferrer">here</a>) is more general than Upper Regularity and is still enough to imply equivalence.  However, for this graph class and others, I am only aware of associated <em>weak</em> regularity lemmas.</p>

CC BY-SA 4.0
2019-10-01T18:54:05.637Z
Also, apologies for the thread necromancy -- this just happened to align with my current lit review, and I thought I would share what I found.
GMB
CC BY-SA 4.0
2019-10-01T18:53:12.953Z
2019-10-01T18:53:12.953Z
GMB
<p>Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets such that most pairs of sets form bipartite expanders (the number of sets in the partition and the expansion parameter depend on the approximation parameter):</p>

<p><a href="http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma">http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma</a></p>

<p>There are versions of this lemma for "well-behaving" sparse graphs, see, e.g.:</p>

<p><a href="http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf">http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf</a></p>

<p><a href="http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf">http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf</a></p>

<p>What surprises me about these formulations is that they only guarantee that most <em>pairs of sets</em> in the partition form bipartite expanders, and these bipartite expanders may be empty. So, in general sparse graphs, it's quite possible that all edges between different parts in the partition of the vertices don't belong to an expander.</p>

<p>I wonder whether there are formulations that give that most edges between parts are from an expander, or whether there's no hope for such a formulation.</p>

CC BY-SA 3.0
2012-12-24T19:45:57.660Z
but doesnt it seem intuitive that the thm, which is for dense graphs, breaks down in some ways on sparse ones? note the wikipedia ref linked to actually says nothing about expander graphs which suggests it might actually be a later interpretation/formulation...
vzn
CC BY-SA 3.0
2012-12-25T01:11:00.437Z
(1) The usual term for the good behaving pairs of sets are "regular pairs" (In Wikipedia "pseudo-random" pair). I replaced it by "bipartite expanders" because I find this terminology more natural for me. In any case, the intention is that if you pick large enough subsets from both sides of the pair, the number of edges between the subsets is proportional to the number of edges in the pair. (2) Of course what's true for dense graphs may cease to be true for sparse graphs. My question is exactly about the extent to which the properties from the dense case continue to hold in the sparse case.
Dana Moshkovitz
<graph-theory><co.combinatorics><expanders>
Regularity Lemma for Sparse Graphs
Dana Moshkovitz
# Regularity Lemma for Sparse Graphs

(Asked by: username_0 on 2012-12-22)

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets such that most pairs of sets form bipartite expanders (the number of sets in the partition and the expansion parameter depend on the approximation parameter):

<http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma>

There are versions of this lemma for "well-behaving" sparse graphs, see, e.g.:

<http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf>

<http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf>

What surprises me about these formulations is that they only guarantee that most *pairs of sets* in the partition form bipartite expanders, and these bipartite expanders may be empty. So, in general sparse graphs, it's quite possible that all edges between different parts in the partition of the vertices don't belong to an expander.

I wonder whether there are formulations that give that most edges between parts are from an expander, or whether there's no hope for such a formulation.

**Tags:** graph-theory, co.combinatorics, expanders
> **Comments:**
> **username_1**: but doesnt it seem intuitive that the thm, which is for dense graphs, breaks down in some ways on sparse ones? note the wikipedia ref linked to actually says nothing about expander graphs which suggests it might actually be a later interpretation/formulation...  
> **username_0**: (1) The usual term for the good behaving pairs of sets are "regular pairs" (In Wikipedia "pseudo-random" pair). I replaced it by "bipartite expanders" because I find this terminology more natural for me. In any case, the intention is that if you pick large enough subsets from both sides of the pair, the number of edges between the subsets is proportional to the number of edges in the pair. (2) Of course what's true for dense graphs may cease to be true for sparse graphs. My question is exactly about the extent to which the properties from the dense case continue to hold in the sparse case.  

---

## 1 answers

### Answer by username_2 on 2019-10-01. Score: 4

Below is a long-winded answer, but **tl;dr** in the general case there is no hope for such a formulation, but for many of the particular classes of sparse graphs that have regularity lemmas this formulation exists.

For background, there are two popular versions of the SRL. They are: for any fixed $\varepsilon > 0$ and any $n$-node graph $G = (V, E)$, one can partition $V = V\_0 \cup V\_1 \cup \dots \cup V\_p$ into $p = O\_{\varepsilon}(1)$ parts so that ...

> * **(Combinatorial Phrasing)** (1) $|V\_0| \le \varepsilon n$ and the sizes of any $V\_1, \dots, V\_p$ differ by at most $1$ ($V\_0$ is called the "exceptional set"), and (2) all but $\varepsilon p^2$ pairs of the remaining parts $(V\_i, V\_j)$ satisfy
>   $$\left|d(S, T) - d(V\_i, V\_j)\right| < \varepsilon \text{ for all } S \subseteq V\_i, T \subseteq V\_j$$
>   (here $d(\cdot, \cdot)$ gives the density between the parts, i.e. the fraction of edges that are present).
> * **(Analytic Phrasing)** Letting
>   $$\mathop{disc}(V\_i, V\_j) := \max \limits\_{S \subseteq V\_i, T \subseteq V\_j} |V\_i||V\_j|\left|d(V\_i, V\_j) - d(S, T)\right|,$$
>   we have
>   $$\sum \limits\_{i, j =0}^p \mathop{disc}(V\_i, V\_j) < \varepsilon n^2.$$

The "combinatorial phrasing" (I just made these names up, they are not standard) is the original and probably more famous one, whereas the "analytic phrasing" is more modern and related to graph limits, etc (I think it was popularized [here](http://web.cs.elte.hu/~lovasz/analyst.pdf)). To my eye the analytic one is the right formalization of "graph approximated by union of bipartite expanders," since it gives a control on the total "error" of such an approximation, and there is not an exceptional set in which to hide mass. But at this point this is just cosmetic, because it's an easy but important lemma that these two phrasings are equivalent. To get from Combinatorial to Analytic, just union bound the contribution to discrepancy of the irregular parts and exceptional set. To get from Analytic to Combinatorial, just move any part that contributes too much discrepancy to the exceptional set and apply Markov's Inequality to control its mass.

Now to sparse regularity. The goal of sparse regularity is to replace the $\varepsilon$ in the respective inequalities with $\varepsilon d(G)$, where $d(G)$ is the fraction of all possible edges present in $G$. Critically, with this change, **the two phrasings are no longer equivalent.** Rather, the Analytic phrasing is stronger: it still implies Combinatorial exactly as before, but Combinatorial does not generally imply Analytic, because (as anticipated in the OP) one can potentially hide a lot of density in the exceptional set or between the non-regular pairs of parts. Indeed, this separation is formal: the lower bound graphs for the dense SRL (say, [this one](https://arxiv.org/abs/1403.1768)) imply that the Analytic Phrasing doesn't extend in general to sparse graphs, but the paper by Scott linked in the OP shows that the Combinatorial Phrasing actually does extend to all sparse graphs with no conditions.

The survey linked in the OP mostly talks about an SRL for "upper-regular" sparse graphs, which roughly means that the graph has no cuts that are denser than average by more than a constant factor. For these particular graphs, the Combinatorial and Analytic phrasings are equivalent, because there can't be too much extra mass hidden in the exceptional parts so their contribution to discrepancy can be union bounded like in the dense case. So these graphs have an "approximated by union of bipartite expanders" interpretation.

Finally, I should mention that there are many other hypotheses in the literature that also imply equivalence between these phrasings. For example, $L\_p$ Upper Regularity (defined [here](https://arxiv.org/pdf/1401.2906.pdf)) is more general than Upper Regularity and is still enough to imply equivalence. However, for this graph class and others, I am only aware of associated *weak* regularity lemmas.

> **Comments:**
> **username_2**: Also, apologies for the thread necromancy -- this just happened to align with my current lit review, and I thought I would share what I found.  

---

