The Upper Cheeger Bound from a Cut

From a Cut to a Spectral Test Function

A set of vertices with a small edge boundary is a bottleneck: a random walk starting inside the set has relatively few opportunities to leave. The upper Cheeger bound makes one precise connection between that bottleneck and a small spectral gap. Its proof uses a simple test function: the indicator of the set, centered by subtracting its stationary mean. The centering matters because the spectral gap is tested on functions orthogonal to constants.

Throughout, let $G=(V,E)$ be a finite, connected, simple, undirected graph with at least two vertices. Write $\deg(v)$ for the degree of $v$, $\operatorname{vol}(S)=\sum_{v\in S}\deg(v)$ for the volume of $S\subseteq V$, and $\partial S$ for the set of edges with exactly one endpoint in $S$. Thus $|\partial S|$ counts edges crossing the cut $(S,V\setminus S)$. Set $m=|E|$, so $\operatorname{vol}(V)=2m$.

Definition: The conductance of $G$ is $$ \phi(G)=\min_{\substack{\varnothing\ne S\subseteq V\\ \operatorname{vol}(S)\le \operatorname{vol}(V)/2}} \frac{|\partial S|}{\operatorname{vol}(S)}. $$ The lazy random walk stays at its current vertex with probability $1/2$, and moves to each neighbor with probability $1/(2\deg(v))$. Its transition matrix is $P_{\mathrm{lazy}}$. Its stationary distribution is $\pi(v)=\deg(v)/(2m)$, and its spectral gap is $\gamma=1-\lambda_2(P_{\mathrm{lazy}})$, with eigenvalues ordered from largest to smallest.

Connectivity and the assumption of at least two vertices ensure that every degree is positive, so $\pi$ is defined at every vertex. The set over which conductance is minimized is nonempty: a vertex of minimum degree has volume at most $2m/|V|\le m$. There are finitely many eligible sets, so a minimum is attained.

For functions $f,g:V\to\mathbb R$, use the stationary inner product $\langle f,g\rangle_\pi=\sum_{v\in V}\pi(v)f(v)g(v)$. The variance is $\operatorname{Var}_\pi(f)=\sum_v\pi(v)(f(v)-\sum_u\pi(u)f(u))^2$. The Dirichlet form of the walk is $\mathcal E(f,f)=\langle f,(I-P_{\mathrm{lazy}})f\rangle_\pi$.

The Rayleigh Principle and the Cut Calculation

Lemma (Rayleigh principle for the spectral gap): For this reversible random walk, $$ \gamma=\min_{\substack{f:V\to\mathbb R\\ \operatorname{Var}_\pi(f)>0}} \frac{\mathcal E(f,f)}{\operatorname{Var}_\pi(f)}. $$

Proof. Reversibility means $\pi(u)P_{\mathrm{lazy}}(u,v)=\pi(v)P_{\mathrm{lazy}}(v,u)$, so $P_{\mathrm{lazy}}$ is self-adjoint in the stationary inner product. Constants are eigenfunctions with eigenvalue $1$. By the spectral theorem, there is an orthonormal eigenbasis with the constant functions first and remaining eigenvalues $\lambda_2,\ldots,\lambda_{|V|}$. Subtracting the stationary mean from $f$ does not change its Dirichlet form and makes it orthogonal to constants. Write this centered function as $f=\sum_{i=2}^{|V|}a_i e_i$, where $e_i$ has eigenvalue $\lambda_i$. Then \[ \mathcal E(f,f)=\sum_{i=2}^{|V|}(1-\lambda_i)a_i^2,\qquad \operatorname{Var}_\pi(f)=\sum_{i=2}^{|V|}a_i^2. \] For a nonconstant $f$, the denominator is positive. Since $\lambda_i\le\lambda_2$, the quotient is at least $1-\lambda_2$; equality holds when $f=e_2$. This proves the formula. $\square$

Now fix a nonempty set $S$ with $\operatorname{vol}(S)\le m$, and let $a=\pi(S)=\operatorname{vol}(S)/(2m)$. Its centered indicator is \[ f(v)=\mathbf 1_S(v)-a, \] where $\mathbf 1_S(v)=1$ for $v\in S$ and $0$ otherwise. This function has stationary mean zero. Its variance is $a(1-a)$: on $S$ its value is $1-a$, and off $S$ its value is $-a$, giving $a(1-a)^2+(1-a)a^2=a(1-a)$.

Cut calculation: For the centered indicator of $S$, $$ \mathcal E(f,f)=\frac{|\partial S|}{4m}, \qquad \frac{\mathcal E(f,f)}{\operatorname{Var}_\pi(f)} =\frac{|\partial S|}{2\,\operatorname{vol}(S)(1-a)}. $$

Proof. The Dirichlet form can be written as $\frac12\sum_{u,v}\pi(u)P_{\mathrm{lazy}}(u,v)(f(u)-f(v))^2$. Terms with $u=v$ vanish, and terms for nonedges vanish. For each undirected edge $uv$, each directed stationary transition weight is $\pi(u)P_{\mathrm{lazy}}(u,v)=1/(4m)$. The two directed terms, together with the factor $1/2$, therefore contribute $(f(u)-f(v))^2/(4m)$. This difference squared is $1$ on a boundary edge and $0$ on any other edge. Summing gives $\mathcal E(f,f)=|\partial S|/(4m)$. Dividing by the variance $a(1-a)$, and substituting $a=\operatorname{vol}(S)/(2m)$, gives the stated quotient. $\square$

Theorem (upper Cheeger bound from a cut): For a finite connected graph with at least two vertices and the lazy random walk defined above, $$ \gamma\le 2\phi(G). $$

Proof. Choose a nonempty $S$ attaining $\phi(G)$, with $\operatorname{vol}(S)\le m$. Then $0<a\le 1/2$, so the centered indicator has positive variance and is an admissible function in the Rayleigh principle. Its quotient is \[ \frac{\mathcal E(f,f)}{\operatorname{Var}_\pi(f)} =\frac{\phi(G)}{2(1-a)}\le \phi(G)\le 2\phi(G), \] because $1-a\ge 1/2$. The Rayleigh principle says $\gamma$ is no greater than the quotient of any admissible function. Hence $\gamma\le 2\phi(G)$. $\square$

With the conventions in this tutorial, the calculation actually gives the stronger estimate $\gamma\le\phi(G)$. The stated upper Cheeger bound follows at once. Keeping the exact quotient visible is useful: it shows where the lazy transition probability $1/2$ enters and prevents confusion with formulas for a non-lazy walk or with a differently normalized conductance.

Worked Examples

Worked Example: A Cut in the Four-Cycle

Let $G$ have $V=\{1,2,3,4\}$ and $E=\{12,23,34,41\}$. Every vertex has degree $2$, so $2m=8$. Consider $S=\{1,2\}$. Its volume is $2+2=4$, its boundary is $\{23,41\}$, and $a=\operatorname{vol}(S)/(2m)=4/8=1/2$. Thus its conductance ratio is $2/4=1/2$, and its centered-indicator quotient is \[ \frac{|\partial S|}{2\operatorname{vol}(S)(1-a)} =\frac{2}{2\cdot4\cdot(1/2)}=\frac12. \]

In fact $\phi(G)=1/2$. An eligible set has volume $2$ or $4$. A single vertex has boundary size $2$ and ratio $2/2=1$. A pair of adjacent vertices has boundary size $2$ and ratio $2/4=1/2$; a pair of opposite vertices has boundary size $4$ and ratio $4/4=1$. These exhaust eligible sets up to complements.

Check: The lazy transition matrix has eigenvalues $1,1/2,1/2,0$, so $\gamma=1-1/2=1/2$. The cut quotient equals the gap, while $2\phi(G)=1$. The theorem’s inequality holds.

Worked Example: An Endpoint Cut in a Three-Vertex Path

Let $G$ have $V=\{1,2,3\}$ and $E=\{12,23\}$. The degrees are $1,2,1$, and $2m=4$. Take $S=\{1\}$. Then $\operatorname{vol}(S)=1$, $|\partial S|=1$, and $a=1/4$. The cut quotient is \[ \frac{1}{2\cdot1\cdot(1-1/4)}=\frac{1}{3/2}=\frac23. \]

For the conductance minimum, the eligible sets have volume at most $2$. The set $\{1\}$ has ratio $1/1=1$; $\{3\}$ also has ratio $1/1=1$. The set $\{2\}$ has volume $2$, boundary size $2$, and ratio $2/2=1$. The set $\{1,3\}$ has volume $2$, boundary size $2$, and ratio $2/2=1$. Therefore $\phi(G)=1$.

Check: In vertex order $1,2,3$, the lazy transition matrix is \[ \begin{pmatrix} 1/2&1/2&0\\ 1/4&1/2&1/4\\ 0&1/2&1/2 \end{pmatrix}. \] Its eigenvalues are $1,1/2,0$, so $\gamma=1/2$. Hence $1/2\le2/3\le2\phi(G)=2$, as required.

Worked Example: A Single Leaf of a Three-Leaf Star

Let $G$ have $V=\{c,a,b,d\}$ and $E=\{ca,cb,cd\}$. The center $c$ has degree $3$, each leaf has degree $1$, and $2m=6$. For $S=\{a\}$, the volume is $1$, the boundary size is $1$, and $a=\pi(S)=1/6$. Its quotient is \[ \frac{1}{2\cdot1\cdot(1-1/6)} =\frac{1}{2\cdot5/6}=\frac35. \]

To compute conductance, any nonempty eligible set consists either of $k$ leaves, where $k=1,2,3$, or of the center alone. A set of $k$ leaves has volume $k$, boundary size $k$, and ratio $k/k=1$. The center alone has volume $3$, boundary size $3$, and ratio $3/3=1$. Thus $\phi(G)=1$.

Check: The star’s non-lazy walk has eigenvalues $1,0,0,-1$; adding laziness transforms each eigenvalue $\lambda$ to $(1+\lambda)/2$. The lazy eigenvalues are therefore $1,1/2,1/2,0$, and $\gamma=1/2$. We have $1/2\le3/5\le2\phi(G)=2$.

Common Pitfall: Losing the Lazy Factor

A frequent error is to assign each directed transition across an edge stationary weight $1/(2m)$. That is the weight for the non-lazy walk, not the lazy walk. In the lazy walk the probability of moving to a particular neighbor is $1/(2\deg(u))$, so \[ \pi(u)P_{\mathrm{lazy}}(u,v) =\frac{\deg(u)}{2m}\cdot\frac{1}{2\deg(u)} =\frac{1}{4m}. \] For an undirected boundary edge, the two directed terms in the Dirichlet sum combine, including its prefactor $1/2$, to $1/(4m)$, not $1/(2m)$. For example, in the four-cycle cut above, the correct Dirichlet form is $2/(4\cdot4)=1/8$, and the variance is $(1/2)(1/2)=1/4$, giving quotient $(1/8)/(1/4)=1/2$. Using the non-lazy edge weight would double the Dirichlet form and incorrectly give quotient $1$.

The reason the cut is useful is not that its indicator is generally an eigenfunction. Rather, the Rayleigh principle allows any nonconstant test function: a minimizing-conductance set supplies one whose energy is determined exactly by the boundary, while its variance is determined by the stationary mass on either side. This argument proves an upper bound by constructing a test function. The reverse direction requires a different method and is not established by this cut calculation.

Check Your Understanding

Use the lazy-walk and conductance conventions stated above.

For a set $S$ with $\operatorname{vol}(S)=m/3$, express $a=\pi(S)$ and the centered-indicator quotient in terms of $|\partial S|$ and $m$.
Explain why the uncentered indicator $\mathbf 1_S$ is not the appropriate mean-zero Rayleigh test function, and state its centered version.
For a minimum-conductance set, identify the inequality involving $a$ that yields $\gamma\le\phi(G)$ under these conventions.
In the path example, verify directly that the stationary probabilities are $1/4,1/2,1/4$.
Explain which transition probability changes when the walk is made lazy, and how that changes the boundary contribution to the Dirichlet form.

The Upper Cheeger Bound from a Cut

What You'll Learn