Expander mixing lemma

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.

tatement

Let $$G = (V, E) be a d-regular graph with (un-)normalized second-largest eigenvalue $$lambda. 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

For a proof, see link in references.

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

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

References

*Notes proving the expander mixing lemma. [http://algo.epfl.ch/handouts/en/algoM_lect24.pdf]
*Expander mixing lemma converse. [http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf]