Expansion as a Uniform Property
A single graph can have a large boundary relative to its smaller vertex sets, but the central question for an expander family is whether this remains true as the graphs grow. A family is an expander family when its degrees stay bounded and its conductance has a positive lower bound independent of the graph. Cheeger’s inequalities make this combinatorial condition equivalent to a uniform spectral gap for lazy random walks.
Throughout, graphs are finite, undirected and simple. For a graph \(G=(V,E)\), the volume of a vertex set \(S\subseteq V\) is \(\operatorname{vol}(S)=\sum_{v\in S}\deg(v)\). Its edge boundary \(\partial S\) is the set of edges with exactly one endpoint in \(S\). We consider connected graphs with at least two vertices, so every degree is positive and \(\operatorname{vol}(V)>0\).
The constants \(D\) and \(c\) must work uniformly across the whole family. The definition rules out a sequence that expands well at each individual index but has conductance tending to zero. It also excludes families whose degrees grow without bound, even if their conductance stays high.
For a connected graph, the simple random walk moves from \(v\) to each neighbor with probability \(1/\deg(v)\). The lazy random walk stays at its current vertex with probability \(1/2\) and otherwise makes one simple-random-walk move. Its transition matrix is \(P_{\mathrm{L}}=(I+P)/2\), where \(P\) is the transition matrix of the simple random walk. The stationary probability of \(v\) is \(\deg(v)/\operatorname{vol}(V)\). The walk is reversible with respect to this distribution, and its eigenvalues are real. Write them in nonincreasing order as \(1=\lambda_1(P_{\mathrm{L}})>\lambda_2(P_{\mathrm{L}})\ge\cdots\). Connectedness ensures that the eigenvalue \(1\) is simple. The lazy-walk spectral gap is \(\gamma_{\mathrm{L}}(G)=1-\lambda_2(P_{\mathrm{L}})\).
The Cheeger Criterion for a Family
The inequalities are the upper and lower Cheeger bounds, with the constants adjusted for laziness. The upper bound follows from testing the spectral-gap Rayleigh quotient on a cut; the lower bound follows from the level-set argument for Cheeger’s inequality. These bounds are established in the earlier material on Cheeger bounds. Here the task is to apply both inequalities with their hypotheses and constants intact.
Proof. First suppose \(\Phi(G_i)\ge c>0\) for every \(i\). Apply the lower Cheeger inequality separately to each graph. It gives \(\gamma_{\mathrm{L}}(G_i)\ge \Phi(G_i)^2/4\ge c^2/4\). Thus the spectral gaps have a uniform positive lower bound.
Conversely, suppose \(\gamma_{\mathrm{L}}(G_i)\ge a>0\) for every \(i\). The upper Cheeger inequality gives \(\gamma_{\mathrm{L}}(G_i)\le\Phi(G_i)\), so \(\Phi(G_i)\ge a\) for every \(i\). Thus the conductances have a uniform positive lower bound. Both implications use constants independent of \(i\), and every graph satisfies the connectedness and size assumptions of the inequalities. \(\square\)
This equivalence is the spectral criterion for expansion: for a bounded-degree family whose orders tend to infinity, one may prove uniform expansion through conductance or through the lazy-walk gap. The degree bound is part of the definition of an expander family, but it is not needed in the Cheeger equivalence itself. The equivalence holds for any sequence of finite connected graphs satisfying the stated assumptions.
Worked Examples and the Constants
Worked Example: Conductance and Gap on a Path
Let \(G=P_3\) have \(V=\{1,2,3\}\) and \(E=\{12,23\}\). Its degrees are \(1,2,1\), so \(\operatorname{vol}(V)=1+2+1=4\). The nonempty sets allowed in the conductance minimum must have volume at most \(4/2=2\). For \(S=\{1\}\) or \(S=\{3\}\), the boundary has one edge and the volume is \(1\), giving ratio \(1/1=1\). For \(S=\{2\}\), the boundary has two edges and the volume is \(2\), giving \(2/2=1\). For \(S=\{1,3\}\), the boundary has two edges and the volume is \(1+1=2\), also giving \(2/2=1\). These are all eligible sets, so \(\Phi(G)=1\).
In the vertex order \(1,2,3\), the simple-walk transition matrix is $$ P=\begin{pmatrix} 0&1&0\\ 1/2&0&1/2\\ 0&1&0 \end{pmatrix}. $$ Its eigenvalues are \(1,0,-1\), so the lazy matrix \((I+P)/2\) has eigenvalues \(1,1/2,0\). Hence \(\gamma_{\mathrm{L}}(G)=1-1/2=1/2\). The Cheeger bounds give \(1^2/4=1/4\le1/2\le1=\Phi(G)\), as required.
Check: the direct cut computation gives \(\Phi(G)=1\), and the transition matrix gives gap \(1/2\). The gap satisfies both bounds; they need not be equal to the gap.
Worked Example: A Cycle Family Does Not Expand Uniformly
For each \(n\ge3\), let \(C_n\) have \(V=\{0,1,\ldots,n-1\}\) and edges joining consecutive residues modulo \(n\). Every vertex has degree \(2\), so the degrees are uniformly bounded by \(2\). For any eligible nonempty set \(S\), its volume is \(2|S|\), and eligibility means \(2|S|\le 2n/2=n\), or \(|S|\le\lfloor n/2\rfloor\). A nonempty proper subset of a cycle has at least two boundary edges: as one moves around the cycle, membership in \(S\) must change at least once from outside to inside and once from inside to outside. Therefore $$ \frac{|\partial S|}{\operatorname{vol}(S)} \ge \frac{2}{2|S|} \ge \frac{1}{\lfloor n/2\rfloor}. $$ A set of \(\lfloor n/2\rfloor\) consecutive vertices has exactly two boundary edges and volume \(2\lfloor n/2\rfloor\), so it attains this lower bound. Thus \(\Phi(C_n)=1/\lfloor n/2\rfloor\).
For \(C_6\), the set \(\{0,1,2\}\) is eligible: its volume is \(2\cdot3=6\), equal to half the total volume \(12/2=6\). Its boundary has two edges, so its ratio is \(2/6=1/3\), agreeing with \(1/\lfloor6/2\rfloor=1/3\).
The simple-walk eigenvalues on \(C_n\) are \(\cos(2\pi j/n)\), for \(j=0,\ldots,n-1\). Laziness changes these to \((1+\cos(2\pi j/n))/2\), so the largest eigenvalue below \(1\) is \((1+\cos(2\pi/n))/2\). It follows that $$ \gamma_{\mathrm{L}}(C_n) =1-\frac{1+\cos(2\pi/n)}{2} =\frac{1-\cos(2\pi/n)}{2} =\sin^2(\pi/n). $$ For \(C_6\), this is \(\sin^2(\pi/6)=(1/2)^2=1/4\). As \(n\) increases, \(\Phi(C_n)=1/\lfloor n/2\rfloor\) tends to zero. Also \(\sin x\le x\) for \(x\ge0\), so \(0\le\gamma_{\mathrm{L}}(C_n)=\sin^2(\pi/n)\le\pi^2/n^2\), which tends to zero. Thus the cycle sequence has bounded degree and growing order, but is not an expander family.
Check: for \(C_6\), the computed values are \(\Phi=1/3\) and \(\gamma_{\mathrm{L}}=1/4\). The bounds read \((1/3)^2/4=1/36\le1/4\le1/3\).
Worked Example: A Small Graph Where the Upper Bound Is Exact
Let \(G=K_4\), with \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\). Each vertex has degree \(3\), so \(\operatorname{vol}(V)=12\), and eligible sets have volume at most \(6\). A one-vertex set has boundary size \(3\) and volume \(3\), giving ratio \(1\). A two-vertex set has boundary size \(2\cdot2=4\) and volume \(6\), giving ratio \(4/6=2/3\). These are all possible set sizes under the constraint, so \(\Phi(K_4)=2/3\).
For the simple random walk on \(K_4\), each vertex moves to each of the other three with probability \(1/3\). The transition matrix is \((J-I)/3\), where \(J\) is the \(4\) by \(4\) all-ones matrix. The constant vector has eigenvalue \(1\); every vector whose coordinates sum to zero has eigenvalue \(-1/3\), since \(J\) sends such a vector to zero. Thus the lazy eigenvalues are \(1\) and \( (1-1/3)/2=1/3\) on the sum-zero vectors. The lazy gap is \(1-1/3=2/3\), so here \(\gamma_{\mathrm{L}}(K_4)=\Phi(K_4)\).
Check: the lower bound is \((2/3)^2/4=1/9\), and the upper bound is \(2/3\). The computed gap \(2/3\) lies between them and attains the upper bound.
Why the Degree Bound and Laziness Matter
Conductance measures boundary edges per unit of stationary volume, not per vertex. For a bounded-degree connected graph, it also controls the more elementary edge expansion ratio \(|\partial S|/|S|\). Indeed, every vertex has degree at least \(1\), so \(\operatorname{vol}(S)\ge |S|\), while the degree bound gives \(\operatorname{vol}(S)\le D|S|\). For every eligible \(S\), these inequalities imply $$ \frac{|\partial S|}{|S|} =\frac{|\partial S|}{\operatorname{vol}(S)} \frac{\operatorname{vol}(S)}{|S|} \ge \Phi(G), \qquad \frac{|\partial S|}{|S|} \le D\,\frac{|\partial S|}{\operatorname{vol}(S)}. $$ In particular, conductance at least \(c\) implies \(|\partial S|\ge c|S|\) for eligible \(S\). Conversely, if \(|\partial S|\ge h|S|\) for every eligible \(S\), then \(\Phi(G)\ge h/D\). The uniform degree bound is what makes this conversion uniform across a family.
Laziness matters because the simple random walk on a bipartite graph can have eigenvalue \(-1\), causing periodic oscillation. Replacing \(P\) by \((I+P)/2\) maps each eigenvalue \(\lambda\) of \(P\) to \((1+\lambda)/2\); in particular, \(-1\) becomes \(0\). The lazy spectral gap therefore measures the distance from the top eigenvalue to the next one without confusing slow convergence with periodicity.
Common mistake: using the non-lazy constants with the lazy gap. The usual Cheeger bounds for the simple random walk are \(\Phi^2/2\le 1-\lambda_2(P)\le2\Phi\). Since laziness halves the gap, the corresponding bounds are \(\Phi^2/4\le\gamma_{\mathrm{L}}\le\Phi\), not \(\Phi^2/2\le\gamma_{\mathrm{L}}\le2\Phi\). For the computed graph \(P_3\), \(\Phi=1\) and \(\gamma_{\mathrm{L}}=1/2\). Applying the non-lazy lower bound directly would incorrectly claim \(1/2\ge1\). The correction is to halve the non-lazy gap, and hence both Cheeger constants, when passing to the lazy walk.
Check Your Understanding
Use the definitions and bounds above. When applying the conductance minimum, include sets of exactly half the total volume.
- For \(P_3\), list all eligible sets and verify the conductance computation.
- Explain why a uniform lower bound on the lazy gaps forces a uniform lower bound on conductance.
- For \(C_8\), compute the conductance by considering a consecutive set of four vertices. Why is it eligible?
- State how the uniform degree bound converts a conductance lower bound into an edge expansion lower bound.
- What is the relationship between the simple-walk and lazy-walk spectral gaps, and how does that affect the Cheeger constants?