Diagnosing Expansion in Standard Graph Families

Expansion in Four Standard Families

Conductance and spectral gap offer two related ways to assess how well a graph connects its vertices. Conductance asks how many edges cross every balanced cut, relative to the size of the smaller side and the degree. The normalized spectral gap measures how far the second-largest eigenvalue of the random-walk transition matrix lies below \(1\). These quantities let us compare families whose degrees and orders may both grow.

All graphs in this tutorial are finite, simple and undirected. We consider connected \(d\)-regular graphs with at least two vertices. For a vertex set \(S\), let \(\partial S\) be the set of edges with exactly one endpoint in \(S\). In a \(d\)-regular graph, the volume of \(S\) is \(d|S|\). Using the smaller side of each cut gives the following definition.

Because \(\lambda_2\) is the second-largest eigenvalue—not the eigenvalue of second-largest absolute value—a connected bipartite graph may have an eigenvalue \(-1\) without making this gap zero. A family of connected regular graphs has uniform edge expansion if there is a constant \(c>0\), independent of the graph in the family, such that \(\Phi(G)\ge c\) for every member. The degree \(d\) in the denominator matters: expansion is being measured relative to the possible number of edges incident to the smaller side.

Cycles: Both Quantities Vanish

For the cycle \(C_n\), every vertex has degree \(2\). A nonempty proper subset of the vertices has at least two boundary edges: as one goes around the cycle, membership must change at least once to enter the subset and once to leave it. A consecutive block of \(k\) vertices, where \(1\le k\le\lfloor n/2\rfloor\), has exactly two boundary edges. Thus the conductance is exactly \(1/\lfloor n/2\rfloor\). The spectral gap has a different rate of decay, quadratic rather than linear in \(1/n\).

Proof. If \(S\) is nonempty and \(|S|\le n/2\), then \(k=|S|\le\lfloor n/2\rfloor\), and \(|\partial S|\ge2\). Therefore \(\frac{|\partial S|}{2|S|}\ge\frac{2}{2k}\ge\frac{1}{\lfloor n/2\rfloor}\). A consecutive block of \(\lfloor n/2\rfloor\) vertices has two boundary edges and attains this value.

For the spectral calculation, label cycle vertices by residues \(0,\ldots,n-1\). For each \(j\in\{0,\ldots,n-1\}\), the vector with coordinate \(z_j(k)=\exp(2\pi i jk/n)\) at vertex \(k\) satisfies \((Pz_j)(k)=(z_j(k-1)+z_j(k+1))/2=\cos(2\pi j/n)z_j(k)\). These \(n\) vectors give the eigenvalues of \(P\). The largest eigenvalue is \(1\), at \(j=0\); among the others the largest is \(\cos(2\pi/n)\), since cosine decreases from \(0\) to \(\pi\) and the nonzero angles closest to \(0\) modulo \(2\pi\) are \(2\pi/n\) and \(2\pi-2\pi/n\). Hence the stated gap follows. \(\square\)

Complete Graphs: Uniform Expansion

In the complete graph \(K_n\), every vertex in \(S\) is adjacent to every vertex outside \(S\). A cut with \(|S|=k\) therefore has \(k(n-k)\) crossing edges. Dividing by the degree \(n-1\) and by \(k\) shows that the conductance stays bounded away from zero as \(n\) grows. The spectrum gives a normalized gap that also stays bounded away from zero.

Proof. For \(1\le k\le\lfloor n/2\rfloor\), the conductance ratio for a set of size \(k\) is \(\frac{k(n-k)}{(n-1)k}=\frac{n-k}{n-1}\). This decreases as \(k\) increases, so its minimum occurs at \(k=\lfloor n/2\rfloor\), giving \(\lceil n/2\rceil/(n-1)\).

For the spectrum, \(P\) sends a vector \(x\) to the vector whose \(i\)th coordinate is \((\sum_j x_j-x_i)/(n-1)\). The constant vector has eigenvalue \(1\). If \(\sum_jx_j=0\), then \(Px=-x/(n-1)\). The subspace of such vectors has dimension \(n-1\), so all other eigenvalues equal \(-1/(n-1)\). Thus \(\lambda_2=-1/(n-1)\) and \(\gamma=1+1/(n-1)=n/(n-1)\). \(\square\)

Complete Bipartite Graphs: A Uniform Lower Bound

In \(K_{n,n}\), each of the two parts has \(n\) vertices and every vertex has degree \(n\). A set \(S\) contains \(a\) vertices from one part and \(b\) from the other. Its boundary consists of the \(a(n-b)\) edges from those \(a\) vertices to the other part outside \(S\), and the \(b(n-a)\) edges from those \(b\) vertices to the first part outside \(S\). In particular, a balanced set of vertices from both parts does not have a small boundary relative to its volume.

Proof. Take a nonempty \(S\) with \(a+b\le n\), as required in the conductance minimum. Its boundary size is \(|\partial S|=a(n-b)+b(n-a)=n(a+b)-2ab\). Since \(4ab\le(a+b)^2\) and \(a+b\le n\), we have \(2ab\le (a+b)^2/2\le n(a+b)/2\). Consequently, \(\frac{|\partial S|}{n(a+b)}=1-\frac{2ab}{n(a+b)}\ge1/2\). This proves the lower bound.

For the spectrum, the vector that is \(1\) on one part and \(-1\) on the other has eigenvalue \(-1\). The constant vector has eigenvalue \(1\). A vector supported on one part whose coordinates sum to zero is sent to zero by \(P\); the same holds for such vectors on the other part. These subspaces account for all \(2n\) dimensions, so the remaining eigenvalues are zero. For \(n\ge2\), the second-largest eigenvalue is \(0\), and \(\gamma=1\). \(\square\)

Hypercubes: Degree-Growing but Expanding Slowly

The \(r\)-dimensional hypercube \(Q_r\) has the binary strings of length \(r\) as vertices; two strings are adjacent exactly when they differ in one coordinate. Every vertex has degree \(r\). Its spectral gap is \(2/r\). Its conductance can be found by combining this gap with the lower Cheeger bound from the earlier material on conductance and spectral gaps, and then exhibiting a cut that attains the resulting bound.

Proof. Index coordinates by \(1,\ldots,r\). For each subset \(A\) of these coordinates, define \(f_A(x)=(-1)^{\sum_{i\in A}x_i}\). Flipping a coordinate in \(A\) changes the sign of \(f_A\), and flipping a coordinate outside \(A\) leaves it unchanged. Thus the average over the \(r\) neighbors of \(x\) is \((Pf_A)(x)=\frac{r-2|A|}{r}f_A(x)\). The \(2^r\) functions \(f_A\) are linearly independent: their pairwise inner products, summed over all binary strings, are zero for distinct subsets and \(2^r\) for identical subsets. They therefore give the full spectrum. The constant function corresponds to \(A=\varnothing\); the largest eigenvalue among the remaining ones occurs when \(|A|=1\) and equals \(1-2/r\). This gives \(\gamma(Q_r)=2/r\).

The lower Cheeger bound in the normalized convention used here is \(\gamma(G)\le2\Phi(G)\). Applying it to \(Q_r\) gives \(\Phi(Q_r)\ge\gamma(Q_r)/2=1/r\). For the reverse inequality, take \(S\) to consist of the strings whose first coordinate is \(0\). Then \(|S|=2^{r-1}\), and each of its vertices has exactly one edge leaving \(S\), so \(|\partial S|=2^{r-1}\). Its conductance ratio is \(2^{r-1}/(r2^{r-1})=1/r\). The two bounds agree. \(\square\)

Which Families Have Uniform Edge Expansion?

The calculations distinguish the four families immediately. For \(C_n\), the conductance is \(1/\lfloor n/2\rfloor\), which tends to zero, and the spectral gap also tends to zero. For \(K_n\), conductance is at least \(1/2\): indeed \(\lceil n/2\rceil/(n-1)\ge1/2\), since \(2\lceil n/2\rceil\ge n-1\). The complete bipartite graphs \(K_{n,n}\) have conductance at least \(1/2\). These two families therefore have uniform edge expansion.

For \(Q_r\), conductance equals \(1/r\), so the family does not have uniform edge expansion as its dimension grows. Its spectral gap \(2/r\) also tends to zero. The complete graph and complete bipartite graph examples show that a growing order alone does not force expansion to vanish; the cycle and hypercube examples show that increasing order can coexist with vanishing conductance. Degree normalization is essential to making these comparisons meaningful.

Common Pitfall: Omitting the Degree

A common error is to calculate \(|\partial S|/|S|\) and call it conductance in a regular graph. That ratio omits the factor \(d\), so it is not the normalized conductance defined here. For example, in \(K_6\), the cut into two sets of three vertices has nine crossing edges. The incorrect ratio is \(9/3=3\); the conductance ratio is \(9/(5\cdot3)=3/5\). The former grows with the degree in complete graphs, while the latter is the appropriate normalized quantity.

Another potential confusion is to use the largest eigenvalue in absolute value after \(1\) when defining the gap. In \(K_{n,n}\), the eigenvalue \(-1\) records bipartiteness, but \(\lambda_2=0\) and the normalized gap is \(1\). For conductance and the spectral criterion used here, the ordering is by value, not absolute value.