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 \| = 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