25
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – vzn Dec 24 '12 at 19:45
  • 1
    $\begingroup$ (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. $\endgroup$ – Dana Moshkovitz Dec 25 '12 at 1:11
4
$\begingroup$

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). 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) 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) 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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – GMB Oct 1 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.