Expander Mixing Lemma

|e(S, T) - d|S||T|/n| ≤ λ √|S||T| — spectral gap controls pseudorandomness.

The idea

Theorem (Expander mixing lemma).

Let $G$ be a $d$-regular graph on $n$ vertices with adjacency eigenvalues $d = \lambda_{1} \ge \lambda_{2} \ge \cdots \ge \lambda_{n}$, and put $\lambda = \max(|\lambda_{2}|, |\lambda_{n}|)$. Then for all vertex sets $S$ and $T$, $\left| e(S,T) - \frac{d\,|S|\,|T|}{n} \right| \le \lambda \sqrt{|S|\,|T|},$ where $e(S,T)$ is the number of edges with one end in $S$ and the other in $T$.

The subtracted term is the random benchmark. If the $dn/2$ edges were placed at random, each of the $d$ edges leaving a vertex of $S$ would land in $T$ with probability $|T|/n$, giving $d|S||T|/n$ crossing edges on average. The left-hand side therefore measures how far the graph departs from random behaviour on the pair $S$, $T$.

A single number bounds this departure for every pair of sets at once: $\lambda$, the largest adjacency eigenvalue apart from the trivial $\lambda_{1} = d$, taken in absolute value. The difference $d - \lambda$ is the spectral gap. When $\lambda$ is small compared with $d$, the error term is small compared with the main term, so every pair of reasonably large sets receives close to its random share of edges. A graph with small $\lambda$ is an expander, and the lemma says that this one eigenvalue certifies pseudorandom edge distribution.

Ways to work on it

• Walkthrough. What the mixing lemma says — and a numerical check on a small example.
• Practice. Compute the expected edge count between two vertex sets and the mixing-lemma error bound.
• Hardest. Graphs achieving the best possible spectral gap, and how sharp the mixing bound gets there.

Not sure where to start? Take the ten-question placement test.