By the entrywise description of \(\mathcal{L}\),

Since \(\sum _{v\sim u} \frac{g(u)}{d_u} = g(u)\), we may write \(g(u) = \frac{1}{\sqrt{d_u}}\sum _{v\sim u}\frac{g(u)}{\sqrt{d_u}}\), and hence

Since \(L = T - A\), we have \(\mathcal{L}= T^{-1/2}(T-A)T^{-1/2} = T^{-1/2}T\, T^{-1/2} - T^{-1/2}AT^{-1/2} = I - T^{-1/2}AT^{-1/2}\), where \(T^{-1/2}TT^{-1/2}=I\) on the vertices of nonzero degree.

When every degree equals \(k\) we have \(T = kI\), so \(T^{-1/2}AT^{-1/2} = \frac1k A\), and \(\mathcal{L}= I - \frac1k A\) by Lemma 7.

Compute \((SS^{*})(u,u) = \sum _{e \ni u} \frac{1}{d_u} = \frac{d_u}{d_u} = 1\), and for \(u\ne v\), \((SS^{*})(u,v) = \sum _e S(u,e)S(v,e)\); only the edge \(\{ u,v\} \) (if present) contributes, giving \(\frac{1}{\sqrt{d_u}}\cdot \left(-\frac{1}{\sqrt{d_v}}\right) = -\frac{1}{\sqrt{d_u d_v}}\). Thus \(SS^{*} = \mathcal{L}\). For any \(g\), \(\langle g, \mathcal{L}g\rangle = \langle g, SS^{*}g\rangle = \| S^{*}g\| ^2 = \sum _{\{ u,v\} }\left(\frac{g(u)}{\sqrt{d_u}} - \frac{g(v)}{\sqrt{d_v}}\right)^2 \ge 0\), so \(\mathcal{L}\) is positive semidefinite. Being real and symmetric, \(\mathcal{L}\) has real nonnegative eigenvalues by the spectral theorem.

By Lemma 9, \(\langle g, \mathcal{L}g\rangle = \sum _{\{ u,v\} }\bigl(\frac{g(u)}{\sqrt{d_u}} - \frac{g(v)}{\sqrt{d_v}}\bigr)^2\). With \(g=T^{1/2}f\) we have \(g(u)/\sqrt{d_u} = f(u)\), so the numerator equals \(\sum _{u\sim v}(f(u)-f(v))^2\). Also \(\langle g,g\rangle = \sum _v g(v)^2 = \sum _v d_v f(v)^2\).

With \(g = T^{1/2}\mathbf{1}\) we have \(g(u)/\sqrt{d_u} = 1\) for every \(u\) of nonzero degree, so each edge term \(\frac{g(u)}{\sqrt{d_u}} - \frac{g(v)}{\sqrt{d_v}} = 0\), hence \(S^{*}g = 0\) and \(\mathcal{L}g = SS^{*}g = 0\). Thus \(0\) is an eigenvalue; by Lemma 9 all eigenvalues are \(\ge 0\), so \(0\) is the least.

By the Courant–Fischer (min–max) principle applied to the symmetric operator \(\mathcal{L}\), \(\lambda _1 = \min \{ \langle g,\mathcal{L}g\rangle /\langle g,g\rangle : g \ne 0,\ g \perp \phi _0\} \), with \(\phi _0\) proportional to \(T^{1/2}\mathbf{1}\) (Lemma 12). The constraint \(g \perp T^{1/2}\mathbf{1}\) reads \(\langle T^{1/2}f, T^{1/2}\mathbf{1}\rangle = \sum _v f(v)d_v = 0\), i.e. \(f\perp T\mathbf{1}\). Substituting the Rayleigh–Dirichlet identity (Lemma 10) for the quotient gives the stated formula.

The numerator \(\sum _{u\sim v}(f(u)-f(v))^2\) is unchanged if \(f\) is replaced by \(f-t\). For fixed \(f\), \(\sum _v (f(v)-t)^2 d_v\) is a quadratic in \(t\) minimized at the weighted mean \(t = \bar f\); hence \(\sup _t\) of the ratio is attained there, giving the second expression. Moreover \(f - \bar f \perp T\mathbf{1}\), and any \(f\perp T\mathbf{1}\) has \(\bar f = 0\), so the second expression equals the variational formula of Lemma 15. Finally, using the weighted identity \(\operatorname {vol}G\sum _v (f(v)-\bar f)^2 d_v = \sum _{\{ u,v\} }(f(u)-f(v))^2 d_u d_v\) (the weighted form of \(N\sum _i (a_i-a)^2 = \sum _{i{\lt}j}(a_i-a_j)^2\) with \(a=\bar f\)), substitute for the denominator to obtain the third expression.

By Courant–Fischer, \(\lambda _{n-1} = \max _{g\ne 0}\langle g,\mathcal{L}g\rangle /\langle g,g\rangle \); substituting the Rayleigh–Dirichlet identity (Lemma 10) via \(g = T^{1/2}f\) gives the claim.

This is Courant–Fischer for the \(k\)-th eigenvalue: \(\lambda _k\) is the minimum Rayleigh quotient of \(\mathcal{L}\) over the orthogonal complement of \(\mathrm{span}(\phi _0,\dots ,\phi _{k-1})\), and the orthogonality \(g' = T^{1/2}f \perp T^{1/2}P_{k-1}\) translates to \(f\perp T P_{k-1}\). Substituting the Rayleigh–Dirichlet identity gives both displayed forms.

\(K_n\) is \((n-1)\)-regular, so \(\mathcal{L}= I - \frac{1}{n-1}A\) by Lemma 8, with \(A = J - I\) (\(J\) the all-ones matrix). The eigenvalues of \(A\) are \(n-1\) (eigenvector \(\mathbf{1}\)) and \(-1\) (multiplicity \(n-1\), on \(\mathbf{1}^{\perp }\)). Hence \(\mathcal{L}\) has eigenvalues \(1 - \frac{n-1}{n-1}=0\) and \(1 - \frac{-1}{n-1} = \frac{n}{n-1}\) with multiplicity \(n-1\).

Order the vertices as the part \(X\) of size \(m\) (each of degree \(n\)) followed by the part \(Y\) of size \(n\) (each of degree \(m\)). Then \(A = \left(\begin{smallmatrix} 0 & J_{m,n} \\ J_{n,m} & 0 \end{smallmatrix}\right)\) and \(T = \mathrm{diag}(nI_m, mI_n)\), so \(B := T^{-1/2}AT^{-1/2} = \frac{1}{\sqrt{mn}}\left(\begin{smallmatrix} 0 & J_{m,n} \\ J_{n,m} & 0 \end{smallmatrix}\right)\). Since \(J_{m,n}J_{n,m} = nJ_m\) has eigenvalue \(mn\) once and \(0\) otherwise, the matrix \(\left(\begin{smallmatrix} 0 & J \\ J^{\top } & 0 \end{smallmatrix}\right)\) has nonzero eigenvalues \(\pm \sqrt{mn}\) (each once) and \(0\) with multiplicity \(m+n-2\). Hence \(B\) has eigenvalues \(\pm 1\) (each once) and \(0\) (\(m+n-2\) times), and \(\mathcal{L}= I - B\) has eigenvalues \(0\), \(2\), and \(1\) (multiplicity \(m+n-2\)) by Lemma 7.

This is the case \(m=1\), \(n\mapsto n-1\) of Lemma 20: the eigenvalues are \(0\), \(2\), and \(1\) with multiplicity \(1+(n-1)-2 = n-2\).

\(C_n\) is \(2\)-regular, so \(\mathcal{L}= I - \frac12 A\) (Lemma 8). The adjacency matrix of \(C_n\) is a circulant whose eigenvectors are \((\omega ^{jk})_{j}\) with \(\omega = e^{2\pi i/n}\), having eigenvalues \(\omega ^k + \omega ^{-k} = 2\cos \frac{2\pi k}{n}\). Hence \(\mathcal{L}\) has eigenvalues \(1 - \cos \frac{2\pi k}{n}\).

\(Q_n\) is \(n\)-regular, so \(\mathcal{L}= I - \frac1n A\) (Lemma 8). Indexing vertices by subsets \(S \subseteq \{ 1,\dots ,n\} \) (equivalently by \(\{ 0,1\} ^n\)), the characters \(\chi _S(x) = (-1)^{|S\cap x|}\) are eigenvectors of \(A\) with eigenvalues \(n - 2|S|\); there are \(\binom nk\) subsets with \(|S| = k\). Hence \(\mathcal{L}\) has eigenvalues \(1 - \frac{n-2k}{n} = \frac{2k}{n}\) with multiplicity \(\binom nk\).

\(\sum _i \lambda _i = \operatorname {tr}\mathcal{L}= \sum _u \mathcal{L}(u,u)\), and \(\mathcal{L}(u,u) = 1\) if \(d_u \ne 0\) and \(\mathcal{L}(u,u) = 0\) if \(d_u = 0\). Thus \(\operatorname {tr}\mathcal{L}\) equals the number of non-isolated vertices, which is \(\le n\), with equality exactly when no vertex is isolated.

Since \(\lambda _0 = 0\), Lemma 25 gives \(\sum _{i=1}^{n-1}\lambda _i \le n\). Averaging the \(n-1\) terms \(\lambda _1\le \cdots \le \lambda _{n-1}\),

The second gives \(\lambda _{n-1}\ge \frac{n}{n-1}\) when there are no isolated vertices (so \(\sum _{i\ge 1}\lambda _i = n\)). Equality in \(\lambda _1 \le \frac{n}{n-1}\) forces both \(\sum _{i\ge 1}\lambda _i = n\) (no isolated vertices) and \(\lambda _1 = \cdots = \lambda _{n-1} = \frac{n}{n-1}\); that is the spectrum of \(K_n\) (Lemma 19), and a graph is determined up to the value \(0\)-multiplicity here to be \(K_n\).

Since \(G\) is not complete, it has two nonadjacent vertices \(a\) and \(b\). Define

Then \(\sum _v f_1(v) d_v = d_b d_a - d_a d_b = 0\), so \(f_1 \perp T\mathbf{1}\). Because \(a\) and \(b\) are nonadjacent, every edge at \(a\) goes to a vertex with \(f_1 = 0\), contributing \(d_b^2\); there are \(d_a\) such edges. Likewise the edges at \(b\) contribute \(d_a^2\) each, \(d_b\) of them. Thus the Dirichlet sum is \(d_a d_b^2 + d_b d_a^2 = d_a d_b(d_a+d_b)\), while \(\sum _v f_1(v)^2 d_v = d_b^2 d_a + d_a^2 d_b = d_a d_b(d_a+d_b)\). By Lemma 15 the Rayleigh quotient of \(f_1\) is \(1\), so \(\lambda _1 \le 1\).

Ordering vertices by component makes \(\mathcal{L}\) block-diagonal, one block per connected component (each block being the Laplacian of that component). The spectrum of a block-diagonal matrix is the union of the spectra of the blocks.

An eigenfunction \(g\) with eigenvalue \(0\) has \(\langle g,\mathcal{L}g\rangle = 0\), so by the Rayleigh–Dirichlet identity (Lemma 10) with \(f=T^{-1/2}g\), \(\sum _{u\sim v}(f(u)-f(v))^2 = 0\); hence \(f\) is constant on each connected component. For a connected graph this forces \(f\) constant, so the \(0\)-eigenspace is one-dimensional and \(\lambda _1 {\gt} 0\). In general the \(0\)-eigenspace is spanned by the functions that are a (suitably normalized) constant on one component and \(0\) elsewhere, so its dimension equals the number of connected components; equivalently (Lemma 28) each component contributes exactly one \(0\) to the spectrum. Thus \(\lambda _0 = \cdots = \lambda _i = 0 {\lt} \lambda _{i+1}\) occurs iff there are exactly \(i+1\) components.

Using the elementary inequality \((f(x)-f(y))^2 \le 2(f(x)^2 + f(y)^2)\) and \(\sum _{x\sim y}(f(x)^2 + f(y)^2) = \sum _x f(x)^2 d_x\), formula (1.6) (Lemma 17) gives

Equality requires \((f(x)-f(y))^2 = 2(f(x)^2+f(y)^2)\) on every edge, i.e. \(f(x) = -f(y)\) for each edge \(\{ x,y\} \); a nonzero such \(f\) can exist only if some component is bipartite (two-color it by the sign of \(f\)) and nontrivial. Conversely, if a component is bipartite with parts \(X,Y\), taking \(f = +1\) on \(X\), \(-1\) on \(Y\), and \(0\) off the component achieves the Rayleigh quotient \(2\), so \(\lambda _{n-1} = 2\).

By Lemma 28 it suffices to treat a connected \(G\). Suppose \(G\) is bipartite with parts \(A\) and \(B\). For a harmonic eigenfunction \(f\) with eigenvalue \(\lambda \), set \(g(x) = f(x)\) for \(x\in A\) and \(g(x) = -f(x)\) for \(x\in B\). Using the harmonic eigenfunction identity (Lemma 33), \(\frac{1}{d_x}\sum _{y\sim x}(f(x)-f(y)) = \lambda f(x)\), and the fact that adjacency only connects \(A\) to \(B\), one checks that \(\frac{1}{d_x}\sum _{y\sim x}(g(x)-g(y)) = (2-\lambda )g(x)\); hence \(g\) is a harmonic eigenfunction with eigenvalue \(2-\lambda \). Thus \(\lambda \mapsto 2-\lambda \) maps the spectrum bijectively to itself, giving (iii); the multiplicity bookkeeping of the \(2\)’s against the \(0\)’s (via Lemma 29) gives (ii). Conversely, if \(2\) is an eigenvalue then \(\lambda _{n-1} = 2\), so by Lemma 30 a component is bipartite; symmetry of the whole spectrum forces every component bipartite, i.e. \(G\) bipartite.

Let \(f\) be a harmonic eigenfunction achieving \(\lambda _1\) in Lemma 15, and let \(v_0\) be a vertex with \(|f(v_0)| = \max _v |f(v)|\). Since \(\sum _v f(v) d_v = 0\), there is a vertex \(u_0\) with \(f(u_0)f(v_0) {\lt} 0\). Let \(P\) be a shortest path joining \(u_0\) and \(v_0\); it has at most \(D\) edges. Then, dropping all edges not on \(P\) from the numerator and bounding \(\sum _x f(x)^2 d_x \le f(v_0)^2 \operatorname {vol}G\),

By the Cauchy–Schwarz inequality, \(\sum _{\{ x,y\} \in P}(f(x)-f(y))^2 \ge \frac{1}{|P|}\bigl(\sum _{\{ x,y\} \in P}(f(x)-f(y))\bigr)^2 = \frac{1}{|P|}(f(v_0)-f(u_0))^2\), and \(|P| \le D\) while \((f(v_0)-f(u_0))^2 \ge f(v_0)^2\) because \(f(u_0)\) and \(f(v_0)\) have opposite signs. Therefore \(\lambda _1 \ge \frac{\frac{1}{D}f(v_0)^2}{\operatorname {vol}G\, f(v_0)^2} = \frac{1}{D\, \operatorname {vol}G}\).

Write \(f = T^{-1/2}g\) where \(\mathcal{L}g = \lambda _G g\). Then

using \(L = T^{1/2}\mathcal{L}T^{1/2}\). On the other hand, \((Lf)(x) = \sum _{y\sim x}(f(x)-f(y))\), so \((T^{-1}Lf)(x) = \frac{1}{d_x}\sum _{y\sim x}(f(x)-f(y))\), which therefore equals \(\lambda _G f(x)\). (Alternatively, the same identity follows from a variational argument by perturbing \(f\) at a single vertex \(x_0\).)

The eigenvalues of \(I-\mathcal{L}\) are \(1-\lambda _i\), so \(\operatorname {tr}(I-\mathcal{L})^2 = \sum _i (1-\lambda _i)^2\). Separating the \(i=0\) term \((1-\lambda _0)^2 = 1\) and bounding each remaining \(|1-\lambda _i| \le \bar\lambda \) gives \(\le 1 + (n-1)\bar\lambda ^2\). For the combinatorial form, \(I - \mathcal{L}= T^{-1/2}AT^{-1/2}\) (Lemma 7), so \((I-\mathcal{L})^2 = T^{-1/2}A T^{-1} A T^{-1/2}\) and, since \(A(x,y)^2 = A(x,y)\),

Expanding \(\sum _{\{ x,y\} }\left(\frac{1}{d_x}-\frac{1}{d_y}\right)^2 = \sum _{\{ x,y\} }\left(\frac{1}{d_x^2}+\frac{1}{d_y^2}\right) - \sum _{\substack {x,y\\ x\sim y}}\frac{1}{d_x d_y}\), and noting \(\sum _{\{ x,y\} }\left(\frac{1}{d_x^2}+\frac{1}{d_y^2}\right) = \sum _x \frac{d_x}{d_x^2} = \sum _x \frac{1}{d_x}\), rearranges to the claimed identity.

Since \(\sum _{i\ne 0}(1-\lambda _i)^2 = \operatorname {tr}(I-\mathcal{L})^2 - 1\) and there are \(n-1\) such terms, \(\max _{i\ne 0}|1-\lambda _i|^2 \ge \frac{1}{n-1}\bigl(\operatorname {tr}(I-\mathcal{L})^2 - 1\bigr)\). For a \(k\)-regular graph every \(d_x = k\), so the correction sum in Lemma 34 vanishes and \(\operatorname {tr}(I-\mathcal{L})^2 = \sum _x \frac{1}{k} = \frac{n}{k}\). Hence \(\max _{i\ne 0}|1-\lambda _i|^2 \ge \frac{1}{n-1}\bigl(\frac{n}{k}-1\bigr) = \frac{n-k}{(n-1)k}\).

Apply formula (1.6) (Lemma 17) with the test function \(f(x) = \frac{1}{d_x} - \frac{1}{d_H}\): the numerator becomes \(\sum _{x\sim y}\left(\frac{1}{d_x}-\frac{1}{d_y}\right)^2\) (constants cancel in differences) and the denominator \(\sum _x \left(\frac{1}{d_x}-\frac{1}{d_H}\right)^2 d_x\); since \(\lambda _{n-1}\) is the supremum over all \(f\), the left inequality follows. The right inequality is \(\lambda _{n-1} = 1 + (\lambda _{n-1}-1) \le 1 + |1-\lambda _{n-1}| \le 1 + \bar\lambda \).

By Lemma 34, \(1 + (n-1)\bar\lambda ^2 \ge \operatorname {tr}(I-\mathcal{L})^2 = \sum _x \frac{1}{d_x} - \sum _{x\sim y}\left(\frac{1}{d_x}-\frac{1}{d_y}\right)^2\), and \(\sum _x \frac{1}{d_x} = \frac{n}{d_H}\). By Lemma 38, \(\sum _{x\sim y}\left(\frac{1}{d_x}-\frac{1}{d_y}\right)^2 \le (1+\bar\lambda )\sum _x\left(\frac{1}{d_x}-\frac{1}{d_H}\right)^2 d_x\). Expanding, and using \(\sum _x \frac{1}{d_x} = \frac{n}{d_H}\), \(\sum _x 1 = n\) and \(\sum _x d_x = \operatorname {vol}G = nk\),

Substituting, \(1 + (n-1)\bar\lambda ^2 \ge \frac{n}{d_H} - (1+\bar\lambda )\frac{n}{d_H}\left(\frac{k}{d_H}-1\right) = \frac{n}{d_H}\left(1 - (1+\bar\lambda )\left(\frac{k}{d_H}-1\right)\right)\).

Choose \(u,v\) at distance \(D \ge 2t+2\) (take \(t+1 = D/2\)). Contract \(G\) into a weighted path \(H\) with \(2t+2\) edges and vertices \(x_0, x_1, \dots , x_t, y_t, \dots , y_1, y_0\) and \(z\): vertices at distance \(i\) from \(u\) (\(0\le i\le t\)) are contracted to \(x_i\), those at distance \(j\) from \(v\) to \(y_j\), and all remaining vertices to \(z\). To bound \(\lambda _H\) from above, use the test function

with \(a,b\) chosen so that \(\sum _x f(x) d_x = 0\). A direct computation shows the Rayleigh quotient of \(f\) on \(H\) is at most \(1 - \frac{2\sqrt{k-1}}{k}\bigl(1 - \frac{1}{t+1}\bigr) + \frac{1}{t+1}\) (the bound being tightest when the edge weights satisfy \(w(x_i,x_{i+1}) = k(k-1)^{i-1}\), and similarly for the \(y\)’s). By Lemma 45, \(\lambda _1 = \lambda _G \le \lambda _H\); substituting \(t+1 = D/2\), i.e. \(\frac{1}{t+1} = \frac{2}{D}\), gives the stated bound.

As in the unweighted case, \(\langle g, \mathcal{L}g\rangle = \sum _x f(x) L f(x) = \sum _{x\sim y}(f(x)-f(y))^2 w(x,y)\) for \(g = T^{1/2}f\), and \(\langle g,g\rangle = \sum _x f(x)^2 d_x\). The Courant–Fischer principle for \(\mathcal{L}\) restricted to the orthogonal complement of \(\phi _0 \propto T^{1/2}\mathbf{1}\) (equivalently \(\sum _x f(x) d_x = 0\)) yields the formula.

Let \(\tilde f\) be a harmonic eigenfunction achieving \(\lambda _H\), so \(\sum _p \tilde f(p) d_p^H = 0\). Lift it to \(f : V(G)\to \mathbb {R}\) by \(f(x) = \tilde f(\bar x)\), where \(\bar x\) is the class of \(x\) in \(H\). Contraction preserves degrees and volume (\(d_x^G\) sum to \(d_p^H\) on each class), so \(\sum _x f(x) d_x^G = \sum _p \tilde f(p) d_p^H = 0\) and \(\sum _x f(x)^2 d_x^G = \sum _p \tilde f(p)^2 d_p^H\). Edges of \(G\) inside a contracted class join vertices with equal \(f\)-value, contributing \(0\) to the Dirichlet sum, while edges between classes have their weights added into the corresponding edge of \(H\); hence \(\sum _{x\sim y}(f(x)-f(y))^2 w_G(x,y) = \sum _{p\sim q}(\tilde f(p)-\tilde f(q))^2 w_H(p,q)\). Therefore the Rayleigh quotient of \(f\) on \(G\) equals \(\lambda _H\), and by Lemma 43, \(\lambda _G \le \lambda _H\).

Entrywise \(P(u,v) = \frac{w(u,v)}{d_u} = (T^{-1}A)(u,v)\). Since \(I - \mathcal{L}= T^{-1/2}AT^{-1/2}\) (Lemma 7, valid for weighted \(A\)), \(T^{-1/2}(I-\mathcal{L})T^{1/2} = T^{-1/2}\bigl(T^{-1/2}AT^{-1/2}\bigr)T^{1/2} = T^{-1}A = P\).

The row vector \(\mathbf{1}T\) has \(v\)-entry \(d_v\). Then \((\mathbf{1}T P)(v) = \sum _u d_u P(u,v) = \sum _u d_u \frac{w(u,v)}{d_u} = \sum _u w(u,v) = d_v\), so \(\mathbf{1}T P = \mathbf{1}T\). Normalizing to a probability vector gives \(\pi = \mathbf{1}T/\operatorname {vol}G\).

Irreducibility is equivalent to \(G\) being connected, which by Lemma 29 is equivalent to \(\lambda _1 {\gt} 0\). Aperiodicity is equivalent to \(G\) being non-bipartite, which by Lemma 30 is equivalent to \(\lambda _{n-1} {\lt} 2\). These conditions are also sufficient: the \(L_2\)-convergence bound (Lemma 51) then shows \(fP^s \to \pi \).

Write \(fT^{-1/2} = \sum _i a_i \phi _i\). Since \(\phi _0 = T^{1/2}\mathbf{1}/\sqrt{\operatorname {vol}G}\) and \(\langle f,\mathbf{1}\rangle = 1\), we get \(a_0 = \frac{\langle fT^{-1/2}, T^{1/2}\mathbf{1}\rangle }{\sqrt{\operatorname {vol}G}} = \frac{1}{\sqrt{\operatorname {vol}G}}\), whence \(a_0 \phi _0 T^{1/2} = \frac{\mathbf{1}T}{\operatorname {vol}G} = \pi \) (Lemma 49). By Lemma 48, \(P^s = T^{-1/2}(I-\mathcal{L})^s T^{1/2}\), so

Each \(|1-\lambda _i| \le 1-\lambda '\), and \(\| \sum _{i\ne 0} a_i\phi _i\| \le \| fT^{-1/2}\| \le \| f\| /\min _y\sqrt{d_y}\), while multiplying by \(T^{1/2}\) scales each coordinate by at most \(\max _x\sqrt{d_x}\). Hence \(\| fP^s - \pi \| \le (1-\lambda ')^s \frac{\max _x\sqrt{d_x}}{\min _y\sqrt{d_y}}\) (using \(\| f\| \le 1\)). Finally \(1-\lambda ' \le e^{-\lambda '}\) gives the exponential bound.

Adding the loop weight \(c\, d_v\) leaves the combinatorial Laplacian unchanged: the diagonal entry becomes \(d_v' - w'(v,v) = (1+c)d_v - (w(v,v)+c\, d_v) = d_v - w(v,v)\), and off-diagonal entries are untouched, so \(L' = L\). The new degree matrix is \(T' = (1+c)T\), hence \(\mathcal{L}' = T'^{-1/2}L'T'^{-1/2} = \frac{1}{1+c}T^{-1/2}LT^{-1/2} = \frac{1}{1+c}\mathcal{L}\), giving \(\lambda _k' = \frac{\lambda _k}{1+c}\). The stated special values follow by substituting the indicated \(c\).

It suffices to take sets \(A\) with \(\operatorname {vol}A \le \tfrac 12 \operatorname {vol}G\). Then

using \(|P^s(y,x)-\pi (x)| \le \pi (x)\Delta (s)\) and \(\sum _{x\in A}\pi (x) \le \tfrac 12\).

By Cauchy–Schwarz, \(\sum _x |P^s(y,x)-\pi (x)| = \sum _x \frac{|P^s(y,x)-\pi (x)|}{\sqrt{\pi (x)}}\sqrt{\pi (x)} \le \bigl(\sum _x \frac{(P^s(y,x)-\pi (x))^2}{\pi (x)}\bigr)^{1/2}\bigl(\sum _x \pi (x)\bigr)^{1/2}\), so \(2\Delta _{TV}(s) = \max _y\sum _x|P^s(y,x)-\pi (x)| \le \Delta '(s)\). For the upper bound, \(\Delta '(s) = \max _x\bigl(\sum _y \frac{(P^s(x,y)-\pi (y))^2}{\pi (y)}\bigr)^{1/2} \le \max _x\bigl(\sum _y \Delta (s)^2 \pi (y)\bigr)^{1/2} = \Delta (s)\), using \(|P^s(x,y)-\pi (y)| \le \pi (y)\Delta (s)\) and \(\sum _y \pi (y) = 1\).

Let \(\psi _x\) denote the characteristic (row) vector of \(x\). Expand \(\psi _x T^{1/2} = \sum _i \alpha _i \phi _i\) and \(\psi _y T^{-1/2} = \sum _i \beta _i \phi _i\); here \(\alpha _0 = d_x/\sqrt{\operatorname {vol}G}\) and \(\beta _0 = 1/\sqrt{\operatorname {vol}G}\), and the \(i=0\) terms combine to \(\pi (x)\). Using \(P^t = T^{-1/2}(I-\mathcal{L})^t T^{1/2}\) (Lemma 48),

Let \(\bar\lambda = \max _{i\ne 0}|1-\lambda _i|\). Bounding \(|1-\lambda _i|^t \le \bar\lambda ^t\) and applying Cauchy–Schwarz to \(\sum _{i\ne 0}|\alpha _i\beta _i| \le \| \psi _x T^{1/2}\| \, \| \psi _y T^{-1/2}\| = \sqrt{d_x}\cdot \frac{1}{\sqrt{d_y}}\),

Setting \(\lambda = 1 - \bar\lambda \) gives the first bound with \(\lambda = \lambda _1\) when \(2\ge \lambda _{n-1}+\lambda _1\). Otherwise apply the same computation to the lazy-modified walk of Lemma 52 with \(c = \frac{\lambda _1+\lambda _{n-1}}{2}-1\), whose gap is \(\lambda = \frac{2\lambda _1}{\lambda _{n-1}+\lambda _1} \ge \frac{2\lambda _1}{2+\lambda _1}\), yielding the second bound. Solving \(e^{-t\lambda }\frac{\operatorname {vol}G}{\min _x d_x} \le \epsilon \) for \(t\) gives the stated step count.

Averaging the maximum over \(\pi \),

using \(P^s = T^{-1/2}(I-\mathcal{L})^s T^{1/2}\) and \(\pi \leftrightarrow I_0\). Writing \(\psi _x = \sum _i \phi _i(x)\phi _i\),

When \(G\) is vertex-transitive the summand over \(x\) is independent of \(x\), so the initial inequality is an equality.

By Lemma 57, \(\Delta _{TV}(s) \le \tfrac 12\Delta '(s)\). For a vertex-transitive graph the inequality in Lemma 59 is an equality, so \(\Delta '(s) = \bigl(\sum _{i\ne 0}(1-\lambda _i)^{2s}\bigr)^{1/2}\).

By Example 1.6 (Lemma 24) the eigenvalues of \(Q_n\) are \(\frac{2k}{n}\) with multiplicity \(\binom nk\), so the lazy-walk eigenvalues (Lemma 52) are \(\lambda _k' = \frac{\lambda _k(\lambda _{n-1}-\lambda _1)}{\lambda _{n-1}+\lambda _1} = \frac{\lambda _k(n-1)}{n+1}\), where \(\lambda _{n-1} = 2\) and \(\lambda _1 = 2/n\) are the largest and smallest nontrivial eigenvalues of \(Q_n\); hence \(\lambda _k' = \frac{2k(n-1)}{n(n+1)}\) and \(1 - \lambda _k' = 1 - \frac{2k(n-1)}{n(n+1)}\). \(Q_n\) is vertex-transitive, so by Theorem 61,

provided \(s \ge \tfrac 14 n\log n + cn\), using \(\binom nk \le n^k = e^{k\log n}\) and \(1 - x \le e^{-x}\). For the relative pointwise distance, Theorem 58 (computed directly via the characters \(\phi _S(X) = (-1)^{|S\cap X|}/2^{n/2}\)) gives

whenever \(s \ge \tfrac 12 n\log n + cn\). Thus the rate under relative pointwise distance is about twice that under total variation distance.