The Expander Mixing Lemma: Eigenvalues Force Pseudorandom Edges

The precise statement

Let G = (V, E) be a d-regular graph on n = |V| vertices with adjacency matrix A. Because A is real symmetric, the spectral theorem gives real eigenvalues d = λ₁ ≥ λ₂ ≥ ⋯ ≥ λₙ ≥ −d, with the all-ones vector 𝟙 an eigenvector for λ₁ = d. Define the spectral gap parameter

λ := max(|λ₂|, |λₙ|),

the largest absolute eigenvalue other than d. For any two subsets S, T ⊆ V, write e(S, T) = |{(u, v) ∈ S × T : uv ∈ E}| for the number of ordered edges between them (edges inside S ∩ T counted twice). The Expander Mixing Lemma (Alon–Chung, 1988) asserts

| e(S, T) − (d/n)·|S|·|T| | ≤ λ·√(|S|·|T|).

A slightly sharper version replaces the right side by λ·√(|S||T|(1 − |S|/n)(1 − |T|/n)). The quantity (d/n)|S||T| is the expected edge count in the Erdős–Rényi / random-regular model, so the lemma bounds discrepancy from perfect randomness by a single spectral quantity.

The picture: one eigenvalue, all cuts at once

Think of the normalized adjacency operator A/d as a diffusion step: it averages a function over each vertex's neighbors. On the constant direction 𝟙 it acts as the identity (eigenvalue 1); on every direction orthogonal to 𝟙 it shrinks by a factor at most λ/d. So after one step, any 'signal' orthogonal to the uniform distribution decays by λ/d. Edges between S and T are exactly a bilinear form ⟨𝟙_S, A 𝟙_T⟩ evaluated on indicator vectors.

Decompose each indicator into its uniform part (which lives along 𝟙) plus a mean-zero fluctuation. The uniform parts interact through the top eigenvalue d and produce precisely the 'expected' term (d/n)|S||T|. The fluctuations interact through the operator restricted to 𝟙⊥, where its norm is at most λ. The entire deviation from randomness is therefore squeezed into λ times a product of fluctuation norms — and those norms are just √(|S|) and √(|T|) sized quantities. One eigenvalue governs every subset pair simultaneously.

Key idea of the proof: project, then Cauchy–Schwarz

Write the indicator 𝟙_S = (|S|/n)𝟙 + f, where f = 𝟙_S − (|S|/n)𝟙 is orthogonal to 𝟙 (it has mean zero), and similarly 𝟙_T = (|T|/n)𝟙 + g. Then

e(S, T) = 𝟙_S^⊤ A 𝟙_T = (|S||T|/n²)·(𝟙^⊤ A 𝟙) + f^⊤ A g,

since the cross terms vanish: A𝟙 = d𝟙 is along 𝟙, and f, g ⟂ 𝟙. As 𝟙^⊤A𝟙 = d·n, the first term is exactly (d/n)|S||T|. It remains to bound the error f^⊤ A g. Because f, g lie in the invariant subspace 𝟙⊥, the operator norm of A there is λ = max(|λ₂|,|λₙ|), so |f^⊤ A g| ≤ λ‖f‖‖g‖ by the spectral bound plus Cauchy–Schwarz. Finally ‖f‖² = |S|(1 − |S|/n) ≤ |S| and ‖g‖² ≤ |T|, giving |f^⊤A g| ≤ λ√(|S||T|). Keeping the (1 − |S|/n) factors yields the sharp form. The whole argument is orthogonal projection followed by one inequality.

Worked example: the Petersen graph

The Petersen graph is 3-regular on n = 10 vertices with adjacency spectrum 3, 1, 1, 1, 1, 1, −2, −2, −2, −2. Thus λ₂ = 1, λ₁₀ = −2, so λ = max(1, 2) = 2. Take S = T a 5-vertex independent set (Petersen has independence number 4, so let S be a 4-vertex independent set instead, |S| = 4, and e(S, S) = 0). The lemma predicts

|0 − (3/10)·4·4| ≤ 2·√(16), i.e. 4.8 ≤ 8. ✓

Now the sharp form: λ·√(|S||T|(1−|S|/n)(1−|T|/n)) = 2·√(4·4·0.6·0.6) = 2·√(16·0.36) = 2·√5.76 = 2·2.4 = 4.8, so the sharp bound gives exactly 4.8 ≥ 4.8 — tight to the discrepancy. This tightness is characteristic: subsets aligned with the extreme eigenvectors (here the −2 eigenspace) saturate the inequality, which is why √(d−1)-type gaps are extremal for sparse regular graphs.

Why the hypotheses matter — and what breaks

Regularity is essential. The clean split into a uniform part plus 𝟙⊥ needs 𝟙 to be an eigenvector, which requires every row of A to sum to d. Drop it and (d/n)|S||T| is no longer the expectation; the irregular generalization (Chung; Bollobás–Nikiforov) replaces d/n by the ratio 2|E|/n² with an extra additive error, or works with the normalized Laplacian eigenvalues.

The two-sided gap matters. Using λ = max(|λ₂|,|λₙ|), not just |λ₂|, is crucial: a bipartite d-regular graph has λₙ = −d, so λ = d and the bound is vacuous — correctly, since e(A, B) between the two sides is wildly non-random. A large negative eigenvalue signals near-bipartiteness, a genuine obstruction to mixing.

Disconnection. Two disjoint copies of K_{d+1} have λ₂ = d, again λ = d: the lemma correctly refuses to certify mixing across the components. The lemma is a converse-friendly quantitative statement — Bilu–Linial (2006) proved a near-converse: small discrepancy forces λ = O(α·log(d/α)).

Why it matters: what the lemma unlocks

The Expander Mixing Lemma is the workhorse that turns a spectral gap into combinatorial pseudorandomness, and it underlies much of theoretical computer science. It gives instant proofs that expanders are excellent samplers and randomness extractors: a short random walk hits every large set with near-correct frequency, powering probability amplification and derandomization. It yields the expander-based error-correcting codes of Sipser–Spielman and Tanner, whose distance is bounded via edge discrepancy. In extremal combinatorics it proves that expanders contain the 'right' count of small subgraphs, connecting to the Chung–Graham–Wilson theory of quasirandom graphs, where seven equivalent pseudorandomness conditions include this discrepancy bound. It quantifies Markov chain mixing times through λ/d. Combined with the Alon–Boppana lower bound λ ≥ 2√(d−1) − o(1), it certifies that Ramanujan graphs (Lubotzky–Phillips–Sarnak, 1988) are optimally pseudorandom — a bridge from number theory and automorphic forms to concrete network design.

How the spectral gap parameter λ controls edge pseudorandomness for a d-regular graph on n vertices. Smaller λ (relative to d) means edges are distributed more like a random graph.

Graph type	λ = max(|λ₂|,|λₙ|)	Discrepancy bound λ√(|S||T|)	Interpretation
Complete graph Kₙ (d = n−1)	λ = 1	√(|S||T|)	Perfectly mixed; smallest possible λ
Ramanujan graph	λ ≤ 2√(d−1)	2√(d−1)·√(|S||T|)	Optimal sparse expander (Alon–Boppana tight)
Random d-regular graph	λ ≈ 2√(d−1)	≈ 2√(d−1)·√(|S||T|)	Almost Ramanujan with high probability
Disjoint union of two K_{d+1}	λ = d	d·√(|S||T|)	Bound vacuous; not an expander
Bipartite d-regular graph	λₙ = −d, so λ = d	d·√(|S||T|)	Two-sided gap fails; use |λ₂| variant