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


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



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.

  • 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

Your Answer

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

Browse other questions tagged or ask your own question.