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$.

Statement

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.
• Expander mixing lemma converse.