Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Dec 24 '12 at 19:45
    
(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 Dec 25 '12 at 1:11
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.