Expander mixing lemma

From Wikipedia, the free encyclopedia

The expander mixing lemma states that, for any two subsets S,T of a regular expander graph G, the number of edges between S and T is approximately what you would expect in a random d-regular graph, i.e. d |S| \cdot |T| / n.

[edit] Statement

Let G = (V,E) be a d-regular graph with (un-)normalized second-largest eigenvalue λ. Then for any two subsets S, T \subseteq V, let E(S,T) denote the number of edges between S and T. We have

|E(S, T) - \frac{d |S| \cdot |T|}{n}| \leq \lambda \sqrt{|S| \cdot |T|}

For a proof, see link in references.

[edit] Converse

Recently, Bilu and Linial showed that the converse holds as well: if a graph satisfies the conclusion of the expander mixing lemma, that is, for any two subsets S, T \subseteq V,

|E(S, T) - \frac{d |S| \cdot |T|}{n}| \leq \alpha \sqrt{|S| \cdot |T|}

then its second-largest eigenvalue is O(α(1 + log(d / α))).

[edit] References

  • Notes proving the expander mixing lemma. [1]
  • Expander mixing lemma converse. [2]
This article is uncategorized.

Please help improve this article by adding it to one or more categories, so it may be associated with related articles (how?). Please remove this tag after categorizing.
This page has been tagged since November 2006.
Retrieved from "http://en.wikipedia.org../../../e/x/p/Expander_mixing_lemma.html"