Graph Laplacians, Isoperimetry, and Diameter Bounds

A graph has a discrete analogue of Dirichlet energy: sum the squared differences of a function across edges. The unnormalized Laplacian represents this quadratic form. We also use its degree-normalized version, whose Rayleigh quotient compares this energy with a degree-weighted norm.

We relate the spectral gap to two geometric quantities. The Cheeger constant measures the size of a boundary relative to the set it encloses, while the diameter measures the longest shortest path. Trial functions give one direction of the comparison; level sets of eigenfunctions give the other.

Let \(G=(V,E)\) be a finite simple undirected graph, with \(n=|V|\) and vertex degrees \(d_v\). The matrix definitions below allow isolated vertices, including graphs with no edges. The subsequent variational and diameter bounds will be stated for connected graphs with at least two vertices. Define

\[\begin{aligned} L(u,v) = \begin{cases} d_v & \text{ if } u = v ~, \\ -1 & \text{ if } u,v \text{ are adjacent} ~, \\ 0 & \text{ otherwise} ~. \end{cases} \end{aligned}\]

Define \(T = \operatorname{diag}(d_1, \cdots, d_n)\), where \(|V| = n\) is assumed in this definition. The Laplacian of the graph \(G\) is the matrix

\[\begin{aligned} \mathcal L (u,v) = \begin{cases} 1 & \text{ if } u = v \text{ and } d_v \neq 0 ~, \\ \displaystyle -\frac{1}{\sqrt{d_u d_v}} & \text{ if } u, v \text{ are adjacent} ~, \\ 0 & \text{ otherwise} ~. \end{cases} \end{aligned}\]

Note that the Laplacian is equivalently written as \(\mathcal L = T^{-\frac12} L T^{-\frac12}\). The convention is \(T^{-1} (v,v) = 0\) if \(d_v = 0\). As such, \(\mathcal L\) can also be viewed as an operator on the space of functions \(g : V \to \mathbb R\), and this satisfies

\[\begin{aligned} \mathcal L g(u) = \frac{1}{\sqrt{d_u}} \sum_{v : u \sim v} \left( \frac{g(u)}{\sqrt{d_u}} - \frac{g(v)}{\sqrt{d_v}} \right) ~. \end{aligned}\]

Letting \(A\) be the adjacency matrix associated with \(G\), we then have that, in general,

\[\begin{aligned} \mathcal L = P - T^{-\frac12} A T^{-\frac12} ~. \end{aligned}\]

Here \(P=\operatorname{diag}(\mathbf1_{\{d_v>0\}})\), and every diagonal entry of \(T^{-1/2}\) at an isolated vertex is defined to be zero. Indeed, \(T^{-1/2}TT^{-1/2}=P\). If no vertex is isolated, \(P=I\). At an isolated vertex the operator value is zero, so the preceding coordinate formula is read with this convention.

Alternatively, we can define \(S\) be the matrix

whose rows are indexed by the vertices,
whose columns are indexed by the edges of \(G\),

such that each column corresponding to an edge \(e = (u,v)\) has entry \(\frac{1}{\sqrt{d_u}}\) in the row corresponding to \(u\), and \(-\frac{1}{\sqrt{d_v}}\) in the row corresponding to \(v\), and \(0\) otherwise. Then, by this definition,

\[\begin{aligned} \mathcal L = S S^* ~, \end{aligned}\]

where \(S^*\) denotes the transpose of \(S\). Seen this way, \(S\) can be viewed as a “boundary operator” that maps \(1\)-chains defined on the edges of a graph (denoted by \(C_1\)) to \(0\)-chains defined on vertices (denoted by \(C_0\)). \(S^*\) is correspondingly the “coboundary operator”.

The matrix \(\mathcal L\) is real symmetric, so the spectral theorem gives real eigenvalues and an orthonormal eigenbasis. Its factorization gives the additional sign information: \(z^T\mathcal Lz=|S^Tz|^2\ge0\) for every \(z\), so every eigenvalue is nonnegative. From this point onward assume that \(G\) is connected and \(n\ge2\); then all degrees are positive. For a nonzero real function \(g\) on the vertices, its Rayleigh quotient is

\[\begin{aligned} \frac{\langle g, \mathcal L g \rangle}{\langle g, g \rangle} &= \frac{\langle g, T^{-\frac12} L T^{-\frac12} g \rangle}{\langle g, g \rangle} = \frac{\langle f, L f \rangle}{\langle T^{\frac12} f, T^{\frac12} f \rangle} = \frac{\sum_{u \sim v} (f(u) - f(v))^2}{\sum_v f(v)^2 d_v} ~, \end{aligned}\]

where \(g = T^{\frac12} f\), and \(u \sim v\) denotes the collection of all unordered vertex pairs such that \(u\) and \(v\) are adjacent.

There are \(n\) real eigenvalues counted with multiplicity, which we order as \(0=\lambda_0\le\lambda_1\le\cdots\le\lambda_{n-1}\). Since \(L\mathbf1=0\), the vector \(T^{1/2}\mathbf1\) is a zero eigenvector of \(\mathcal L\). The energy vanishes only when the function is constant on each connected component; connectedness therefore makes the zero eigenvalue simple. The least positive eigenvalue has the variational characterization

\[\begin{aligned} \lambda_G \triangleq \lambda_1 = \inf_{\substack{f\ne0\\f\perp T\mathbf1}} \frac{\sum_{u \sim v} (f(u) - f(v))^2}{\sum_v f(v)^2 d_v} ~. \end{aligned}\tag{1}\]

We call any function \(f\) attaining the infimum in (1) the harmonic eigenfunction of \(\mathcal L\). Note that (1) is equivalent to

\[\begin{aligned} \lambda_1 &= \inf_{f\ \mathrm{nonconstant}} \sup_t \frac{\sum_{u \sim v} (f(u) - f(v))^2}{\sum_v (f(v) - t)^2 d_v} ~, \\ \lambda_1 &= \inf_{f\ \mathrm{nonconstant}} \frac{\sum_{u \sim v} (f(u) - f(v))^2}{\sum_v (f(v) - \overline f)^2 d_v} ~,~ \text{where } \overline f \triangleq \frac{\sum_v f(v) d_v}{\operatorname{Vol} (G)} \end{aligned}\]

and \(\operatorname{Vol} (G) \triangleq \sum_v d_v\).

The spectral properties of a graph are intimately tied to a number of “geometric” properties of it. Define the diameter of a graph as the maximum distance between any two vertices of \(G\).

Lemma 1. Let \(G\) be a connected graph, and \(D\) be the diameter of \(G\). Then,

\[\begin{aligned} \lambda_1 \geq \frac{1}{D \operatorname{Vol} (G)} ~. \end{aligned}\]

Proof. Let \(f\) be a harmonic eigenfunction attaining the infimum in (1). Let \(v_0\) be a vertex such that \(|f(v_0)| = \max_v |f(v)|\). Since \(\sum_v d_v f(v) = 0\), it must be true that there exists a vertex \(u_0\) such that \(f(u_0) f(v_0) < 0\). Suppose \(P\) is the shortest path in \(G\) joining the vertices \(u_0\) and \(v_0\). Then,

\[\begin{aligned} \lambda_1 &= \frac{\sum_{u \sim v} (f(u) - f(v))^2}{\sum_u f(u)^2 d_u} \geq \frac{\sum_{(u,v) \in P} (f(u) - f(v))^2}{f(v_0)^2 \operatorname{Vol} (G)} \\ &\geq \frac{(f(u_0) - f(v_0))^2}{D f(v_0)^2 \operatorname{Vol} (G)} \geq \frac{1}{D \operatorname{Vol} (G)} ~, \end{aligned}\]

where the penultimate inequality follows from an application of the Cauchy-Schwarz inequality. ◻

To recover the eigenvalue equation at a vertex, perturb the minimizing function there and differentiate its Rayleigh quotient.

Lemma 2. Let \(f\) be a harmonic eigenfunction attaining (1). Then, for any vertex \(v \in V\), we have

\[\begin{aligned} \frac{1}{d_v} \sum_{y: y \sim v} (f(v) - f(y)) = \lambda_G f(v) ~. \end{aligned}\]

Proof. Write \(E(f)=\sum_{\{u,v\}\in E}(f(u)-f(v))^2\) and \(B(f)=\sum_vd_vf(v)^2\). For every perturbation \(h\) satisfying \(\sum_vd_vh(v)=0\), \(f+\varepsilon h\) remains admissible in (1). Differentiating \(E(f+\varepsilon h)/B(f+\varepsilon h)\) at its minimum gives

\[\sum_{\{u,v\}\in E}(f(u)-f(v))(h(u)-h(v))=\lambda_1\sum_vd_vf(v)h(v).\]

The left side equals \(\sum_vh(v)\sum_{y\sim v}(f(v)-f(y))\): each unordered edge contributes its two endpoint terms. Therefore \(Lf-\lambda_1Tf\) is orthogonal to the hyperplane \(\{h:\langle h,T\mathbf1\rangle=0\}\), and so equals \(cT\mathbf1\) for some scalar \(c\). Summing its coordinates gives zero, because \(\mathbf1^\top Lf=0\) and \(\sum_vd_vf(v)=0\). Since \(\operatorname{Vol}(G)>0\), \(c=0\). Thus \(Lf=\lambda_1Tf\), which is the asserted vertex equation. ◻

Remark 3 (a trace bound). Put \(B=I-\mathcal L=T^{-1/2}AT^{-1/2}\) and \(\overline\lambda=\max_{i\ge1}|1-\lambda_i|\). Since the eigenvalues of \(B\) are \(1-\lambda_i\),

\[\operatorname{tr}(B^2)=1+\sum_{i=1}^{n-1}(1-\lambda_i)^2\le1+(n-1)\overline\lambda^2.\]

Directly from its entries,

\[\operatorname{tr}(B^2)=2\sum_{\{u,v\}\in E}\frac1{d_ud_v}=\sum_v\frac1{d_v}-\sum_{\{u,v\}\in E}\left(\frac1{d_u}-\frac1{d_v}\right)^2.\]

All edge sums here are unordered. The last identity follows by expanding the square: the sum of its two reciprocal-square terms is \(\sum_vd_v/d_v^2\). Thus

\[\overline\lambda^2\ge\frac{\operatorname{tr}(B^2)-1}{n-1}.\]

For a \(k\)-regular graph, \(\operatorname{tr}(B^2)=n/k\), and consequently \(\overline\lambda\ge\sqrt{(n-k)/((n-1)k)}\). The square root is essential when passing from the trace to \(\overline\lambda\).

1. On Isoperimetric Problems

We next compare the spectral gap with the size of cuts. An isoperimetric problem asks how small a boundary can be when the enclosed set has prescribed size. On a graph, the boundary can be counted in edges or in vertices.

A useful tool to study isoperimetric problems for graphs is the Cheeger constant of a graph \(G\). Let \(S\) denote a subset of the vertices of graph \(G\). Then, the volume of \(S\) is the sum of all degrees of the vertices in \(S\), written as

\[\begin{aligned} \operatorname{Vol} (S) = \sum_{s \in S} d_s ~. \end{aligned}\]

The edge boundary of \(S\) is the collection of all edges with exactly one endpoint in \(S\), written as

\[\begin{aligned} \partial S \triangleq \{ (u,v) \in E = E(G) : u \in S ~,~ v \notin S \} ~. \end{aligned}\]

The vertex boundary of \(S\) is the collection of all vertices \(v\) not in \(S\), but adjacent to some vertex in \(S\), written as

\[\begin{aligned} \delta S \triangleq \{ v \notin S : (u,v) \in E = E(G) ~,~ u \in S \} ~. \end{aligned}\]

These definitions give two versions of the isoperimetric problem:

for a fixed number \(m\), find a subset \(S\) of vertices, with \(m \leq \operatorname{Vol} (S) \leq \operatorname{Vol} (\overline S)\) such that \(\partial S\) contains as few edges as possible;
for a fixed number \(m\), find a subset \(S\) of vertices, with \(m \leq \operatorname{Vol} (S) \leq \operatorname{Vol} (\overline S)\) such that \(\delta S\) contains as few vertices as possible.

We can then begin to understand how to tackle these problems, through defining the Cheeger constant. We first define

\[\begin{aligned} h_G (S) \triangleq \frac{|E(S,\overline S)|}{\min (\operatorname{Vol} (S), \operatorname{Vol} (\overline S))} ~, \end{aligned}\]

where \(\overline S = V \setminus S\) and \(E(A,B)\) denotes the set of edges with one endpoint in \(A \subset V\) and another endpoint in \(B \subset V\). The Cheeger constant is defined as

\[\begin{aligned} h_G = \min_{\varnothing\ne S\subsetneq V} ~ h_G (S) ~. \end{aligned}\]

For every nonempty proper \(S\), \(|\partial S|\ge h_G\min(\operatorname{Vol}(S),\operatorname{Vol}(\overline S))\). In particular, \(|\partial S|\ge h_G\operatorname{Vol}(S)\) when \(\operatorname{Vol}(S)\le\operatorname{Vol}(G)/2\). Connectedness gives \(h_G>0\), and \(|\partial S|\le\min(\operatorname{Vol}(S),\operatorname{Vol}(\overline S))\) gives \(h_G\le1\). These are edge-expansion bounds.

There is an analogous definition for vertex expansions of a graph \(G\), i.e.

\[\begin{aligned} g_G (S) = \frac{\operatorname{Vol} (\delta S)}{\min ( \operatorname{Vol}(S), \operatorname{Vol}(\overline S) )} ~, \end{aligned}\]

and analogously define

\[\begin{aligned} g_G = \min_{\varnothing\ne S\subsetneq V} ~ g_G (S) ~. \end{aligned}\]

Lemma 4. \(\lambda_1 \leq 2 h_G\).

Proof. Choose a nonempty proper set \(A\) attaining \(h_G\), and put \(B=V\setminus A\), \(a=\operatorname{Vol}(A)\), \(b=\operatorname{Vol}(B)\). Define \(f=1/a\) on \(A\) and \(f=-1/b\) on \(B\). Its degree-weighted mean is zero. Only crossing edges contribute to its energy, so its Rayleigh quotient is

\[\frac{|E(A,B)|(1/a+1/b)^2}{a/a^2+b/b^2}=|E(A,B)|(1/a+1/b)\le\frac{2|E(A,B)|}{\min(a,b)}=2h_G.\]

The variational characterization proves the result. ◻

Lemma 5 (Cheeger lower bound). For a connected graph, \(\lambda_1\ge h_G^2/2\).

Proof. Let \(f\) satisfy the eigenfunction equation of Lemma 2. Its weighted mean is zero and it is not zero, so it takes both positive and negative values. Replacing \(f\) by \(-f\) if necessary ensures that \(X=\{f>0\}\) has volume at most half the total volume. Put \(g=f_+\), and write

\[B=\sum_vd_vg(v)^2>0,\qquad E_g=\sum_{\{u,v\}\in E}(g(u)-g(v))^2.\]

Multiply \(Lf=\lambda_1Tf\) by \(g\) and sum. The monotone one-Lipschitz map \(x\mapsto x_+\) satisfies \((a-b)(a_+-b_+)\ge(a_+-b_+)^2\), hence

\[\lambda_1B=\sum_{\{u,v\}\in E}(f(u)-f(v))(g(u)-g(v))\ge E_g.\]

For \(t\ge0\), let \(S_t=\{v:g(v)^2>t\}\). Each nonempty \(S_t\) lies in \(X\) and therefore has volume at most half. Finite-sum layer cake gives the discrete coarea identities

\[\sum_{\{u,v\}\in E}|g(u)^2-g(v)^2|=\int_0^\infty|\partial S_t|dt\ge h_G\int_0^\infty\operatorname{Vol}(S_t)dt=h_GB.\]

On the other hand, Cauchy–Schwarz gives

\[\left(\sum_{\{u,v\}\in E}|g(u)^2-g(v)^2|\right)^2\le E_g\sum_{\{u,v\}\in E}(g(u)+g(v))^2\le2E_gB.\]

Combining the inequalities yields \(E_g/B\ge h_G^2/2\), and \(\lambda_1\ge E_g/B\) completes the proof. This spells out the threshold argument without an undefined final vertex \(v_{n+1}\), or a cut with zero denominator. ◻

Theorem 6 (sharper Cheeger bound). Every connected graph satisfies

\[\lambda_1\ge1-\sqrt{1-h_G^2}.\]

Proof. Retain \(g,B,E_g\) from Lemma 5 and set \(W=E_g/B\). Expanding the two edge sums gives the exact identity

\[\sum_{\{u,v\}\in E}(g(u)+g(v))^2=2B-E_g=(2-W)B.\]

Because \(g\ge0\), \(E_g=B-2\sum_{\{u,v\}\in E}g(u)g(v)\le B\); hence \(0<W\le1\). Use the coarea lower bound and Cauchy–Schwarz again to obtain \(h_G^2B^2\le E_g(2B-E_g)\), or

\[(W-1)^2\le1-h_G^2.\]

Thus \(\lambda_1\ge W\ge1-\sqrt{1-h_G^2}\). This is an interval inequality for \(W\), not an equality with a root of the quadratic. Strictness is unavailable in general: the three-vertex path has \(h_G=1\) and normalized spectral gap \(\lambda_1=1\). ◻

Remark 7. Every nontrivial cut of a connected graph contains at least one edge, and its smaller side has volume at most \(\operatorname{Vol}(G)/2\). Thus \(h_G\ge2/\operatorname{Vol}(G)\). Since a simple graph has \(\operatorname{Vol}(G)\le n(n-1)\), Lemma 5 gives

\[\lambda_1\ge\frac2{\operatorname{Vol}(G)^2}\ge\frac2{n^2(n-1)^2}\ge\frac2{n^4}.\]

For each set \(S\), every crossing edge is incident to \(\delta S\), so \(|\partial S|\le\operatorname{Vol}(\delta S)\). If \(d=\max_vd_v\), also \(\operatorname{Vol}(\delta S)\le d|\partial S|\). Taking minima gives \(h_G\le g_G\le dh_G\), and hence \(\lambda_1\le2g_G\). A flow construction gives a lower bound with only one factor of \(d\), as follows.

Theorem 8 (a vertex-expansion bound). Let \(d=\max_vd_v\). For the vertex-expansion constant defined above,

\[\lambda_1\ge\frac{g_G^2}{2d(2+g_G)}.\]

The constant here is the one established by the flow estimate below.

Proof. Take \(g=f_+\) and \(X=\{f>0\}\) as in Lemma 5, so \(\operatorname{Vol}(X)\le\operatorname{Vol}(G)/2\) and \(\lambda_1\ge E_g/B\). Put \(\gamma=g_G\). Make disjoint copies \(X_L\) of \(X\) and \(V_R\) of \(V\), with source \(s\) and sink \(t\). Give \(s\to u_L\) capacity \((1+\gamma)d_u\), give \(v_R\to t\) capacity \(d_v\), and give \(u_L\to v_R\) capacity \(H>(1+\gamma)\operatorname{Vol}(X)\) whenever \(u=v\) or \(\{u,v\}\in E\).

For completeness, the finite directed max-flow/min-cut theorem follows as follows. Feasible flows form a compact set, so a maximum exists. Its residual network has no source-to-sink path with positive residual capacities, since augmenting along that path would increase the flow. Let the source side of the cut consist of the vertices reachable from the source in the residual network. Every original arc leaving this set is saturated and every original arc entering it has zero flow. Conservation at interior vertices therefore identifies the flow value with this cut capacity. Every feasible flow is bounded by every cut capacity, proving equality.¹ There is a cut of capacity \((1+\gamma)\operatorname{Vol}(X)\), namely the arcs leaving \(s\), so a minimum cut uses no capacity-\(H\) arc. If \(U\subset X\) is the set of left vertices on the source side, all right copies in \(U\cup\delta U\) must also be on that side. The cut therefore has capacity at least²

\[(1+\gamma)\operatorname{Vol}(X\setminus U)+\operatorname{Vol}(U\cup\delta U)\ge(1+\gamma)\operatorname{Vol}(X).\]

For \(U\ne\varnothing\), the last step uses \(\operatorname{Vol}(U)\le\operatorname{Vol}(G)/2\) and \(\operatorname{Vol}(\delta U)\ge\gamma\operatorname{Vol}(U)\); for \(U=\varnothing\) it is immediate. Thus all source arcs can be saturated. The resulting transport numbers \(F_{uv}\ge0\), extended by zero for \(u\notin X\), satisfy

\[\sum_vF_{uv}=(1+\gamma)d_u\quad(u\in X),\qquad\sum_uF_{uv}\le d_v\quad(v\in V).\]

Discard self-transfers and cancel opposing transfers on each original edge. Give the remaining net transfer \(q_e=|F_{uv}-F_{vu}|\) its positive orientation \(u\to v\). This preserves divergence. In particular, the weighted divergence identity gives

\[\sum_{e:u\to v}q_e(g(u)^2-g(v)^2)=\sum_vg(v)^2\left(\sum_wF_{vw}-\sum_wF_{wv}\right)\ge\gamma B.\]

Vertices outside \(X\) contribute zero because \(g=0\). Since \(F_{uv}\le d_v\le d\), each \(q_e\le d\). Cancellation can only reduce incident transfer, so

\[\sum_{e\ni v}q_e\le\sum_wF_{vw}+\sum_wF_{wv}\le(2+\gamma)d_v.\]

Consequently,

\[\begin{aligned}\sum_{e=\{u,v\}}q_e^2(g(u)+g(v))^2&\le2\sum_vg(v)^2\sum_{e\ni v}q_e^2\\&\le2d(2+\gamma)\sum_vd_vg(v)^2=2d(2+\gamma)B.\end{aligned}\]

Apply Cauchy–Schwarz to the divergence sum, with one factor \(g(u)-g(v)\) and the other \(q_e(g(u)+g(v))\). There is at most one net orientation per unordered edge; the first sum of squares is therefore at most \(E_g\). We obtain \(\gamma^2B^2\le2d(2+\gamma)BE_g\), proving the theorem. ◻

Remark 9 (counting vertices rather than degree-weighted volume). Define

\[\widetilde h_G=\min_{\varnothing\ne S\subsetneq V}\frac{|\partial S|}{\min(|S|,|V\setminus S|)}.\]

Writing \(d_{\min}=\min_vd_v\) and \(d_{\max}=\max_vd_v\), comparison of the denominators gives \(d_{\min}h_G\le\widetilde h_G\le d_{\max}h_G\). If \(0=\widetilde\lambda_0\le\cdots\le\widetilde\lambda_{n-1}\) are the eigenvalues of \(L\), then

\[\widetilde\lambda_1=\min_{f\ne0,\,\sum_vf(v)=0}\frac{E(f)}{\sum_vf(v)^2}=\inf_{f\text{ nonconstant}}\frac{E(f)}{\min_t\sum_v(f(v)-t)^2}.\]

The min–max principle and \(d_{\min}\sum f^2\le\sum d_vf^2\le d_{\max}\sum f^2\) give \(d_{\min}\lambda_i\le\widetilde\lambda_i\le d_{\max}\lambda_i\) for every \(i\): apply the quotient comparison on each subspace before taking the min–max over subspaces.

There is also the unnormalized Cheeger inequality

\[\frac{\widetilde h_G^2}{2d_{\max}}\le\widetilde\lambda_1\le2\widetilde h_G.\]

For the upper bound, use the cut trial function of Lemma 4 with \(|A|,|B|\) replacing volumes. For the lower bound, use an eigenfunction of \(L\) with ordinary mean zero, choosing its sign so that \(\{f>0\}\) has at most \(n/2\) vertices. The proof of Lemma 5 then gives \(\widetilde\lambda_1\sum g^2\ge E_g\) and \(\sum_E|g(u)^2-g(v)^2|\ge\widetilde h_G\sum g^2\), while \(\sum_E(g(u)+g(v))^2\le2d_{\max}\sum g^2\). Combining these proves the lower bound, with the squared isoperimetric constant \(\widetilde h_G^2\) in the numerator.

2. Graph Diameters and Eigenvalue Bounds

If a matrix \(M\) has zero off-diagonal entries away from graph edges, then \((M^j)_{uv}=0\) whenever \(d(u,v)>j\). Indeed, every term in the matrix product follows a sequence of at most \(j\) edges, with diagonal factors permitting stays at a vertex. Thus a polynomial of degree \(t\) in \(M\) has zero \((u,v)\) entry when \(d(u,v)>t\). We apply this to a polynomial in \(\mathcal L\).

For a connected noncomplete graph put

\[q=\frac{\lambda_{n-1}-\lambda_1}{\lambda_{n-1}+\lambda_1}\in(0,1),\qquad p_t(z)=\left(1-\frac{2z}{\lambda_1+\lambda_{n-1}}\right)^t.\]

Then \(p_t(0)=1\) and \(|p_t(\lambda_i)|\le q^t\) for \(i\ge1\). If all positive eigenvalues were equal to \(a\), then \(\mathcal L=a(I-\phi_0\phi_0^\top)\), where \(\phi_0=T^{1/2}\mathbf1/\sqrt{\operatorname{Vol}(G)}\); all its off-diagonal entries would be nonzero, forcing the graph to be complete. This proves the strict positivity of the numerator defining \(q\) here. Complete graphs have diameter one and can be handled separately.

For nonempty sets define \(d(X,Y)=\min_{x\in X,y\in Y}d(x,y)\). The following estimate also gives the regular-graph diameter bound

\[D\le\left\lfloor\frac{\log(n-1)}{\log(1/q)}\right\rfloor+1.\]

The integer must be strictly larger than the displayed logarithmic ratio; using a ceiling alone does not ensure the needed strict inequality at integer endpoints.

Proposition 10 (distance between vertex sets). In a connected noncomplete graph, for nonempty disjoint \(X,Y\subset V\),

\[d(X,Y)\le\left\lfloor\frac{\log\sqrt{\operatorname{Vol}(\overline X)\operatorname{Vol}(\overline Y)/(\operatorname{Vol}(X)\operatorname{Vol}(Y))}}{\log(1/q)}\right\rfloor+1.\]

If \(X\cap Y\ne\varnothing\), their distance is zero.

Proof. Take an orthonormal eigenbasis \(\phi_0,\ldots,\phi_{n-1}\), with \(\phi_0=T^{1/2}\mathbf1/\sqrt V\), where \(V=\operatorname{Vol}(G)\) in this proof. Set \(x=\operatorname{Vol}(X)\), \(y=\operatorname{Vol}(Y)\), \(u_X=T^{1/2}1_X\), and \(u_Y=T^{1/2}1_Y\). If \(u_X=\sum_i a_i\phi_i\), then

\[a_0=x/\sqrt V,\qquad\sum_{i\ge1}a_i^2=\|u_X\|^2-a_0^2=x(V-x)/V.\]

Similarly \(b_0=y/\sqrt V\) and \(\sum_{i\ge1}b_i^2=y(V-y)/V\). The spectral expansion and Cauchy–Schwarz therefore give

\[\left|\langle u_Y,p_t(\mathcal L)u_X\rangle-\frac{xy}{V}\right|\le\frac{q^t}{V}\sqrt{x(V-x)y(V-y)}.\tag{2}\]

The inner product is positive whenever \(q^t\sqrt{(V-x)(V-y)/(xy)}<1\). Since \(X,Y\) are disjoint, \(x+y\le V\), so the square-root ratio is at least one. The integer in the statement is strictly larger than its logarithm divided by \(\log(1/q)\); it therefore makes the inner product positive. If \(d(X,Y)>t\), every matrix entry contributing to the inner product would be zero by the polynomial-support observation, a contradiction.

For singleton sets in a regular graph the square-root ratio is \(n-1\), which proves the diameter bound above. More generally it is at most \(V/d_{\min}-1\), giving \(D\le\lfloor\log(V/d_{\min}-1)/\log(1/q)\rfloor+1\). ◻

For an integer \(s\ge1\), define the exterior \(s\)-boundary \(\delta_sX=\{v\notin X:d(v,X)\le s\}\). The set outside the closed neighborhood is \(Y=V\setminus(X\cup\delta_sX)\). If \(Y\ne\varnothing\), then \(d(X,Y)>s\), so \(\langle u_Y,p_s(\mathcal L)u_X\rangle=0\). Formula (2) implies

\[\operatorname{Vol}(X)\operatorname{Vol}(Y)\le q^{2s}\operatorname{Vol}(\overline X)\operatorname{Vol}(\overline Y).\]

The same non-strict inequality is automatic if \(Y\) is empty. The shifted polynomial \(p_s\), rather than \((I-\mathcal L)^s\), is what supplies the spectral contraction factor \(q^s\).

Proposition 11 (spectral boundary expansion). For every nonempty proper \(X\subset V\),

\[\frac{\operatorname{Vol}(\delta X)}{\operatorname{Vol}(X)}\ge\frac{1-q^2}{q^2+\operatorname{Vol}(X)/\operatorname{Vol}(\overline X)}.\]

This also holds for a complete graph with \(q=0\).

Proof. Put \(x=\operatorname{Vol}(X)\), \(b=\operatorname{Vol}(\delta X)\), and \(V=\operatorname{Vol}(G)\). For \(Y=V\setminus(X\cup\delta X)\), the preceding inequality gives

\[x(V-x-b)\le q^2(V-x)(x+b).\]

Move the terms not containing \(b\) to one side:

\[x(V-x)(1-q^2)\le b[x+q^2(V-x)].\]

Divide by the positive quantity \(x(V-x)[q^2+x/(V-x)]\). This gives the claim, including the case of an empty \(Y\). In a complete graph \(\delta X=\overline X\), so the \(q=0\) formula is an equality. ◻

Remark 12. If \(\operatorname{Vol}(X)\le\operatorname{Vol}(\overline X)\), Proposition 11 implies

\[\frac{\operatorname{Vol}(\delta X)}{\operatorname{Vol}(X)}\ge\frac{1-q^2}{1+q^2}\ge1-q=\frac{2\lambda_1}{\lambda_1+\lambda_{n-1}}.\]

For the last inequality, subtract \(1-q\): the difference is \(q(1-q)^2/(1+q^2)\ge0\). The half-volume condition is necessary for this denominator comparison; the preceding proposition remains the appropriate bound for larger sets.

Ford, L. R., and D. R. Fulkerson. 1956. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8: 399–404. https://doi.org/10.4153/CJM-1956-045-5.

Imagine a complex pipeline with a common source and common sink. You start to pump the water up, but you can’t exceed some maximum flow. Why is that? Because there is some kind of bottleneck, i.e. a subset of pipes that transfer the fluid at their maximum capacity—you can’t push more through. This bottleneck will be precisely the minimum cut, i.e. the set of edges that block the flow. Please note, that there may be more than one minimum cut. If you find one, then you know the maximum flow; knowing the maximum flow, then you know the capacity of the cut.↩︎
A minimum cut may include right-vertex-to-sink arcs. The large capacities exclude only the middle arcs. This is why the cut calculation contains \(\operatorname{Vol}(U\cup\delta U)\).↩︎

Reading: Carmo (1992), Riemannian geometry.