Graph Theory
Cheeger's Inequality: The Spectral Gap Bounds Graph Expansion
One eigenvalue tells you whether a graph is a bottleneck. Cheeger's inequality says that the second-smallest eigenvalue λ₂ of the normalized graph Laplacian sandwiches the graph's conductance h(G) — the cheapest bottleneck cut, measured by edges-crossing per unit volume — between two explicit bounds: λ₂/2 ≤ h(G) ≤ √(2λ₂).
Concretely, if λ₂ is bounded away from 0 the graph has no sparse cut and is therefore an expander (fast-mixing, robustly connected); if λ₂ is tiny the graph has an almost-disconnecting cut. The remarkable content is the upper bound h(G) ≤ √(2λ₂): a purely linear-algebraic quantity computable in polynomial time controls a combinatorial optimum (sparsest cut) that is NP-hard to compute exactly, and the proof is constructive — it hands you the good cut.
- FieldSpectral graph theory / combinatorics
- Discrete version provedDodziuk (1984); Alon–Milman, Alon (1985–86)
- Named afterJeff Cheeger (1970, Riemannian manifolds)
- Statementλ₂/2 ≤ h(G) ≤ √(2λ₂), λ₂ = 2nd eigenvalue of normalized Laplacian ℒ
- Proof techniqueRayleigh quotient + sweep (threshold) cut rounding
- Key hypothesisG connected, undirected, nonnegative weights; ℒ symmetric PSD
Interactive visualization
Press play, or step through manually. The visualization is yours to drive — try it before reading on.
Watch the 60-second explainer
A condensed visual walkthrough — narrated, captioned, under a minute.
Precise statement: what the inequality claims
Let G = (V, E) be a connected, undirected graph with nonnegative edge weights w and degrees d(v) = ∑ᵤ w(u,v). The normalized Laplacian is ℒ = I − D^(−1/2) A D^(−1/2), where A is the (weighted) adjacency matrix and D = diag(d(v)). ℒ is symmetric positive semidefinite with eigenvalues 0 = λ₁ ≤ λ₂ ≤ ⋯ ≤ λₙ ≤ 2; λ₁ = 0 with eigenvector D^(1/2)𝟙, and λ₂ > 0 iff G is connected.
For S ⊆ V define its volume vol(S) = ∑_{v∈S} d(v) and conductance φ(S) = w(S, S̄) / min(vol(S), vol(S̄)), where w(S, S̄) is the total weight of edges leaving S. The conductance (Cheeger constant) is h(G) = min_{S: 0 < vol(S) ≤ vol(V)/2} φ(S). Cheeger's inequality is
λ₂ / 2 ≤ h(G) ≤ √(2λ₂).
So λ₂ and h(G)² are equivalent up to a factor of 4: h(G) small ⇔ λ₂ small.
The intuition: a spring network that wants to vibrate
Think of the Laplacian as a network of springs. The eigenvector f for λ₂ is the lowest-energy way to displace the vertices so that they don't all move together (it must be orthogonal to the constant mode). Its Rayleigh quotient
λ₂ = min_{g ⊥ D𝟙} (∑_{(u,v)∈E} w(u,v)(g(u) − g(v))²) / (∑_v d(v) g(v)²)
measures how much the graph resists being pulled into two lumps. If there is a sparse cut — a set S with few edges to the outside but large volume — you can set g ≈ +1 on S and −1 outside, paying energy only on the few crossing edges while the denominator stays large. That makes the ratio small, so λ₂ is small. The deep direction reverses this: a small λ₂ forces the existence of such a cut. The eigenvector itself, a continuous relaxation of the ±1 cut indicator, secretly encodes where the bottleneck is — you just have to round it.
Key idea of the proof: the sweep cut
The easy bound is a one-line variational estimate: given the optimal cut (S, S̄), the vector g = 𝟙_S / vol(S) − 𝟙_{S̄} / vol(S̄) is orthogonal to D𝟙, and its Rayleigh quotient is at most 2h(G), so λ₂ ≤ 2h(G).
The hard bound h(G) ≤ √(2λ₂) is the beautiful part — a rounding argument. Take the λ₂-eigenvector; via g = D^(−1/2)f obtain a function on vertices with ∑_v d(v)g(v)(g(v)) small energy. WLOG center it so a median-type vertex sits at 0, and consider only its positive part. Sort the vertices by g-value and look at the n−1 threshold (sweep) cuts Sₜ = {v : g(v) > t}. The claim is that the best sweep cut already satisfies φ(Sₜ) ≤ √(2λ₂). The engine is a Cauchy–Schwarz estimate: writing the numerator ∑ w(u,v)|g(u)²−g(v)²| = ∑ w(u,v)|g(u)−g(v)|·|g(u)+g(v)|, one factors it into an 'energy' part (≤ √λ₂ up to normalization) and a 'volume' part, and a probabilistic/averaging argument shows some threshold t achieves the ratio. No cut can beat every threshold, so the minimum sweep cut is the certificate.
Worked example: cycle vs. complete graph vs. expander
Cycle Cₙ (n vertices, each degree 2). The Laplacian eigenvalues are 1 − cos(2πk/n), giving λ₂ = 1 − cos(2π/n) ≈ (2π/n)²/... ≈ 2π²/n² for large n. The sparsest cut splits the cycle into two arcs: it cuts 2 edges out of volume ≈ n, so h(Cₙ) ≈ 2/(n) · (1/… ) ≈ 2/n. Check: √(2λ₂) ≈ √(4π²/n²) = 2π/n, and indeed h ≈ 2/n ≤ 2π/n, with h ≈ √(λ₂)/√2 — the square-root loss is real and necessary.
Complete graph Kₙ. λ₂ = ⋯ = λₙ = n/(n−1) ≈ 1, and h(Kₙ) ≈ 1/2; both bounds are Θ(1), and Kₙ is a (trivial, dense) expander.
3-regular Ramanujan expander. λ₂ ≥ 1 − 2√2/3 ≈ 0.057 is bounded below by a constant independent of n, so h(G) ≥ λ₂/2 stays Θ(1): every cut is expensive. This constant-degree, constant-conductance family is exactly what 'expander' means.
Why the hypotheses matter, and what breaks
Connectedness / the choice of λ₂. If G is disconnected, λ₂ = 0 and h(G) = 0 — the inequality holds but is vacuous; the interesting regime is λ₂ > 0. You must use the second eigenvalue: λ₁ = 0 always (eigenvector D^(1/2)𝟙) carries no cut information.
Normalization is essential. The theorem as stated is for the normalized Laplacian ℒ and volume-weighted conductance. If you use the combinatorial Laplacian L = D − A and edge-boundary/|S| isoperimetry, you get a different (degree-dependent) Cheeger inequality; mixing the two normalizations produces false constants. On d-regular graphs they agree up to scaling by d.
The √ is not removable. Cₙ above shows h can be Θ(√λ₂), so no bound of the form h ≤ C·λ₂ holds. Higher-order Cheeger inequalities (Lee–Oveis Gharan–Trevisan, 2012) relate λ_k to k-way partitions, and the 'improved' Cheeger bound h ≲ λ₂/√(λ₃) (Kwok et al., 2013) shows the loss shrinks when λ₃ is large.
Why it matters: expanders, mixing, and clustering
Cheeger's inequality is the bridge between three worlds. (1) Random walks. The spectral gap λ₂ controls the mixing time of the lazy random walk: τ_mix = O(log(n) / λ₂). Via Cheeger this becomes a combinatorial guarantee — a graph with no sparse cut mixes fast — underlying Markov-chain Monte Carlo, card shuffling, and the analysis of algorithms like approximate counting.
(2) Expanders. Constant-degree families with λ₂ ≥ ε (equivalently h ≥ ε') are the workhorses of theoretical CS: pseudorandomness, error-correcting codes, derandomization (the zig-zag product), and robust networks. Cheeger certifies expansion from a single eigenvalue.
(3) Spectral clustering. The proof is an algorithm: compute the λ₂-eigenvector and sweep to get a cut within a √2 factor (in conductance) of optimal — a polynomial-time approximation to NP-hard sparsest cut, and the theoretical justification for the ubiquitous spectral partitioning of images, meshes, and networks. It descends from Cheeger's 1970 manifold isoperimetric inequality, discretized by Dodziuk, Alon, and Alon–Milman.
| Direction | Statement | Proof mechanism | Tightness (extremal example) |
|---|---|---|---|
| Easy bound | λ₂ ≤ 2·h(G) (i.e. λ₂/2 ≤ h(G)) | Plug the ±1 indicator of the optimal cut into the Rayleigh quotient; a linear (variational) estimate | Essentially tight for expanders; both sides Θ(1) |
| Hard bound | h(G) ≤ √(2λ₂) | Take the eigenvector, sort vertices by its value, and prove one of the n−1 threshold cuts is good (sweep cut) | Tight up to constant: the cycle Cₙ has λ₂ ≈ (2π/n)², h ≈ 2/n, so h ≈ √(λ₂)/√2 |
| Combined | λ₂/2 ≤ h(G) ≤ √(2λ₂) | Two independent arguments; the square-root loss in the hard bound is unavoidable | Cₙ shows the √ gap is real; expanders show it can be absent |
Frequently asked questions
Why is it the second eigenvalue λ₂ and not λ₁?
The smallest eigenvalue of the normalized Laplacian ℒ is always λ₁ = 0, with eigenvector D^(1/2)𝟙 (the constant/all-together mode). That mode carries no partitioning information — it can't distinguish any cut. The conductance is governed by the lowest nonzero mode, which is the smallest displacement orthogonal to the constant vector; that's λ₂, also called the spectral gap when λ₁ = 0.
Why does the upper bound have a square root, √(2λ₂), rather than being linear in λ₂?
Because the eigenvector is a real-valued relaxation of a ±1 cut indicator, and rounding it back to a set loses a square-root factor via the Cauchy–Schwarz step in the sweep argument. This loss is genuine, not an artifact: the cycle Cₙ has h ≈ 2/n but λ₂ ≈ (2π/n)², so h ≈ Θ(√λ₂). No inequality of the form h ≤ C·λ₂ can hold for all graphs.
Is the inequality tight? Which side is tight for which graphs?
Both sides are tight up to constants but on different families. For good expanders (and Kₙ) the easy bound λ₂/2 ≤ h is tight — both quantities are Θ(1). For the cycle and long 'path-like' graphs the hard bound h ≤ √(2λ₂) is tight up to the constant, since h ≈ √(λ₂)/√2. So neither bound dominates; each is essential in its regime.
How does this differ from Cheeger's original inequality for manifolds?
Jeff Cheeger (1970) proved that on a compact Riemannian manifold M, the first nonzero eigenvalue of the Laplace–Beltrami operator satisfies λ₁ ≥ h(M)²/4, where h(M) is the isoperimetric (Cheeger) constant inf |∂A|/min(vol A, vol Aᶜ). The graph version is the discrete analogue, with the sweep-cut proof mirroring the manifold coarea/level-set argument. Dodziuk (1984), Alon–Milman and Alon (1985–86) transferred it to graphs.
Can I use the combinatorial Laplacian L = D − A instead of the normalized ℒ?
Yes, but you get a different Cheeger inequality tied to edge-expansion h_edge(S) = |∂S|/min(|S|,|S̄|) rather than volume-conductance, and the eigenvalue is that of L, not ℒ. The bounds pick up degree-dependent factors. On d-regular graphs the two settings coincide up to dividing by d. Mixing normalizations — normalized eigenvalue with unnormalized isoperimetry — gives incorrect constants, a common pitfall.
How is Cheeger's inequality used algorithmically, and does it beat the LP/SDP relaxations for sparsest cut?
The proof is constructive: compute the λ₂-eigenvector (polynomial time), sort vertices by its value, and output the best of the n−1 threshold cuts. This gives a cut with conductance ≤ √(2λ₂) ≤ 2√(h(G)) — an O(1/√OPT)-type, i.e. √-approximation. It's simpler and faster than the O(√log n) Arora–Rao–Vazirani SDP rounding, though ARV gives a better worst-case approximation ratio. Spectral partitioning is the practical method of choice.