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]