Expander mixing lemma

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

Statement

Let $G = (V, E)$ be a d-regular graph on n vertices with $\lambda\in(0,1)$ the second-largest eigenvalue (in absolute value) of the normalized adjacency matrix. For any two subsets $S, T \subseteq V$, let $E(S, T) = |\{(x,y) \in S \times T : xy \in E(G)\}|$ be the number of edges between S and T (counting edges contained in the intersection of S and T twice). Then

$\left|E(S, T) - \frac{d |S| |T|}{n}\right| \leq d \lambda \sqrt{|S| |T|}\,.$

Proof

Let $A$ be the adjacency matrix for $G$. For a vertex subset $U \subseteq V$, let $|U\rangle = \sum_{v \in U} |v\rangle \in \mathbf{R}^n$. Here $|v\rangle$ is the standard basis element of $\mathbf{R}^n$ with a one in the $v^{th}$ position. Thus in particular $A |V\rangle = d |V\rangle$, and the number of edges between $S$ and $T$ is given by $E(S, T) = \langle S | A | T \rangle$.

Expand each of $|S\rangle$ and $|T\rangle$ into a component in the direction of the largest-eigenvalue eigenvector $|V\rangle$ and an orthogonal component:

$|S\rangle = \frac{|S|}{n} |V\rangle + |S'\rangle$

$|T\rangle = \frac{|T|}{n} |V\rangle + |T'\rangle$,

where $\langle S' | V \rangle = \langle T' | V \rangle = 0$. Then

$\langle S | A | T \rangle = \frac{|S| |T|}{n^2} \langle V | A | V \rangle + \langle S' | A | T' \rangle$.

The conclusion follows, since $\langle V | A | V \rangle = d \| |V\rangle \|^2 = d n$, and $| \langle S' | A | T' \rangle | \leq d \lambda | | S' \rangle . | T' \rangle | \leq d \lambda \| | S' \rangle \| \| | T' \rangle \| \leq d \lambda \| | S \rangle \| \| | T \rangle \| = d \lambda \sqrt{|S| |T|}$.

Converse

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| |T|}{n}| \leq d \lambda \sqrt{|S| |T|}$

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

References

• Expander mixing lemma converse.