Let \(f\) be a harmonic eigenfunction associated with \(\lambda _1\), so that its Rayleigh quotient \(\sum _{\{ x,y\} \in E}(f(x)-f(y))^2 w_{x,y}\big/\sum _x f^2(x)d_x=\lambda _1\) and \(\sum _x f(x)d_x=0\). For small \(\epsilon {\gt}0\) put \(f'=1+\epsilon f\). Then, using \(\sum _x f(x)d_x=0\),

By 402, \(\alpha \le I/II\) where

and, using \(\sum _x f(x)d_x=0\) and \(\log (1+x)=x-x^2/2+O(x^3)\),

Hence \(\alpha \le I/II\to \dfrac {\sum _{\{ x,y\} }(f(x)-f(y))^2 w_{x,y}}{2\sum _x f^2(x)d_x}=\dfrac {\lambda _1}{2}\) as \(\epsilon \to 0\).

Define \(q\) by \(\tfrac 1p+\tfrac 1q=1\). For a vertex \(x\) let \(\psi _x\) be the indicator of \(x\). For \(f:V\to \mathbb R\), by Hölder’s inequality

Now

Choosing \(s=\tfrac 1\beta \log \log \tfrac {\operatorname {vol}G}{\min _x d_x}\) makes \(p=e^{\beta s}=\log \tfrac {\operatorname {vol}G}{\min _x d_x}\), so \(\big(\tfrac {\operatorname {vol}G}{\min _x d_x}\big)^{1/p}=e\). Combining with 408 (12.10) and (12.11),

Let \(I_0\) be the projection onto the trivial eigenfunction \(\phi _0\); since \(H_sI_0=I_0\) we have \(H_{s+r}-I_0=H_s(H_r-I_0)\), and applying the last display to \(g=\Pi ^{-1/2}(H_r-I_0)\Pi ^{1/2}f\) gives

using \(\| H_r-I_0\| _2\le e^{-\lambda r}\). Replacing \(\Pi ^{1/2}f\) by an arbitrary \(g\) yields

Finally, since \(H_{2s+2r}-I_0=(H_{s+r}-I_0)^2\) is self-adjoint in the \(\pi \)-inner product,

by (12.12) and Cauchy–Schwarz. Taking \(r=c/(2\lambda )\) and \(t=2s+2r\) gives \(\Delta (t)\le e^{2-c}\) with \(t=\tfrac 2\beta \log \log \tfrac {\operatorname {vol}G}{\min _x d_x}+\tfrac {c}{\lambda }\).

Following the notation of Theorem 12.2, with \(s=\tfrac 1\beta \log \log \tfrac {\operatorname {vol}G}{\min _x d_x}\),

by the pointwise bound underlying (12.12). Taking \(r=c/\lambda \) and \(t=s+r\) gives \(\Delta _{TV}(t)\le \tfrac 12 e^{1-c}\) with \(t=\tfrac 1\beta \log \log \tfrac {\operatorname {vol}G}{\min _x d_x}+\tfrac {c}{\lambda }\).

The case \(p=1\) is trivial (left side \(0\)). For \(p{\gt}1\) assume WLOG \(a\ge b\ge 0\) and write \(a=u^2\), \(b=v^2\) with \(u\ge v\ge 0\); the claim becomes \(4(p-1)(u^p-v^p)^2\le p^2(u^2-v^2)(u^{2p-2}-v^{2p-2})\). Writing each difference as an integral, \(u^p-v^p=\int _v^u p\, t^{p-1}\, dt\), \(u^2-v^2=\int _v^u 2t\, dt\), \(u^{2p-2}-v^{2p-2}=\int _v^u(2p-2)t^{2p-3}\, dt\), we must show

after cancelling \(p^2\) and \(4(p-1)\). Since \(t^{p-1}=t^{1/2}\cdot t^{(2p-3)/2}\), this is exactly the Cauchy–Schwarz inequality \(\big(\int t^{1/2}t^{(2p-3)/2}\, dt\big)^2\le \big(\int t\, dt\big)\big(\int t^{2p-3}\, dt\big)\); for \(p{\gt}1\) the integral \(\int _0^u t^{2p-3}\, dt\) converges, covering the boundary case \(b=0\).

By 402, for any nontrivial \(f\), \(\sum _{x\sim y}(f(x)-f(y))^2 w(x,y)\ge \alpha \sum _x f^2(x)d_x\log \frac{f^2(x)}{\sum _z f^2(z)\pi (z)}\). Replacing \(f\) by \(f^{p/2}\),

By Lemma 410 (with \(a=f(x),b=f(y)\)), \(\big(f^{p/2}(x)-f^{p/2}(y)\big)^2\le \frac{p^2}{4(p-1)}(f(x)-f(y))(f^{p-1}(x)-f^{p-1}(y))\), so

Replace \(f\) by \(g=f\Pi ^{1/2}H_t\Pi ^{-1/2}\) and set \(p=p(t)=1+e^{4\alpha t}\), so \(p'=4\alpha (p-1)\). Then (12.15) rearranges to

Define \(F(t)={}_\pi \| g\| _p=G(t)^{1/p}\) with \(G(t)=\sum _x g^p(x)\pi (x)\); then \(F(0)={}_\pi \| f\| _2\). From \(\log F=\tfrac 1p\log G\),

Writing \(G'(t)=I+II\) with \(II=p'\sum _x g^p\pi \log g\) and, using the weighted heat equation \(\frac{d}{dt}H_t=-\mathcal L H_t\) (weighted Lemma 10.3) and \(\mathcal L=\Pi ^{-1/2}(T-A)\Pi ^{... }\) summation by parts,

Substituting into (12.17) and simplifying,

by (12.16). Hence \({}_\pi \| g\| _p=F(t)\le F(0)={}_\pi \| f\| _2\), which is the assertion.

Theorem 411 shows the heat kernel satisfies hypothesis (12.10) of Theorem 408 with \(p=e^{4\alpha t}\) (dropping the additive \(1\)), i.e. with \(\beta =4\alpha \). Substituting \(\beta =4\alpha \) into the bound of Theorem 12.2 gives \(t\ge \frac{2}{4\alpha }\log \log \frac{\operatorname {vol}G}{\min _x d_x}+\frac c\lambda =\frac{1}{2\alpha }\log \log \frac{\operatorname {vol}G}{\min _x d_x}+\frac c\lambda \).

By Theorem 411 the hypothesis of Theorem 409 holds with \(\beta =4\alpha \). Substituting into the bound of Theorem 12.3 gives \(t\ge \frac{1}{4\alpha }\log \log \frac{\operatorname {vol}G}{\min _x d_x}+\frac c\lambda \).

Let \(g:V'\to \mathbb R\) achieve \(\alpha '\) and define \(f:V\to \mathbb R\) by \(f(x)=g(\rho (x))\). Writing \(g^2(e')=(g(x')-g(y'))^2\) for \(e'=x'y'\) and \(S(g)=\sum _{x'}g^2(x')d'_{x'}\log \frac{g^2(x')}{\sum _z g^2(z)\pi '(z)}\),

Exactly as in the proof of Lemma 4.14, hypotheses (ii)(a),(b) give \(I\ge \frac{1}{\ell m}\), and by definition of \(\alpha \), \(II=\sum _e f^2(e)w_e/S(f)\ge \alpha \). It remains to show \(III\ge c\). Define

which satisfies \(F(\xi ,\zeta )\ge 0\) and, for fixed \(\zeta \), is convex in \(\xi \). Choosing the common normalizing constant \(c_0\) so that \(S(f)=\sum _{x\in V}F(f^2(x),c_0)d_x\) and \(S(g)=\sum _{x'\in V'}F(g^2(x'),c_0)d'_{x'}\) (possible by convexity, adjusting \(c_0\)), and using \(f^2(x)=g^2(\rho (x))\),

using \(F\ge 0\) and hypothesis (i). Hence \(III=S(f)/S(g)\ge c\), and \(\alpha '=I\cdot II\cdot III\ge \frac{c}{\ell m}\alpha \).

For regular graphs, hypothesis (i) of Lemma 414 holds with \(c=k/k'\) (each fiber \(\rho ^{-1}(x')\) has total degree at least \(\frac{k}{k'}d'_{x'}\)), so substituting \(c=k/k'\) into (12.18) gives \(\alpha '\ge \frac{k}{k'\ell m}\alpha \).

Apply Lagrange’s method, differentiating the log-Rayleigh quotient (the right side of (12.4)) with respect to \(f(x)\). This gives

for some constant \(c_1\). Substituting the value of \(\alpha \) this simplifies to

Multiplying (12.29) by \(f(x)\) and summing over \(x\in V\),

Since \(f\) achieves \(\alpha \), \(\sum _{x\sim y}(f(x)-f(y))^2=\alpha \sum _x f^2(x)d_x\log f^2(x)\), so the \(\log f^2\) terms cancel and we are left with \(-2\alpha \sum _x f^2+c_2\sum _x f^2=0\), i.e. \(c_2=2\alpha \). Substituting back into (12.29) gives \(Lf(x)=\alpha f(x)d_x\log f^2(x)\).

Since \(f\) is a harmonic eigenfunction, \(Lf(x)=\lambda d_x f(x)\) with \(L\) the combinatorial Laplacian; WLOG \(f\ge 0\). By summation by parts and Lemma 410,

Apply the discrete Sobolev inequality (12.30), \(\sum _{u\sim v}|g(u)-g(v)|^2 w(x,y)\ge c\big(\sum _v|g(v)|^{2\gamma }d_v\big)^{1/\gamma }\) with \(\gamma =\frac{\delta }{\delta -2}\) and \(c=c_\delta (\delta -1)^2/(4\delta ^2)\), taking \(g=f^{p/2}\):

i.e., for \(q\ge 0\),

Iterating from \(q=2\) (where \(\big(\sum f^{2\gamma }d\big)^{1/\gamma }\le c_1\, 4\lambda \sum f^2 d\), \(c_1=c^{-1}\)) through \(q=2\gamma ,2\gamma ^2,\dots ,2\gamma ^{i}\):

As \(i\to \infty \) the left side tends to \(\sup _x f^2(x)\). Moreover \(1+\frac1\gamma +\cdots \le \frac{1}{1-1/\gamma }=\frac\delta 2\), and \(4\big(\frac{4\gamma ^2}{2\gamma -1}\big)^{1/\gamma }\big(\frac{4\gamma ^4}{2\gamma ^2-1}\big)^{1/\gamma ^2}\cdots \le 4^{\delta /2}\gamma ^{\frac1\gamma +\frac2{\gamma ^2}+\cdots }\le 4^{\delta /2}\gamma ^{\delta /(2\gamma -2)}\le (4e^2)^{\delta /2}\). Hence

The proof of Theorem 428 used the eigenfunction property only through inequality (12.31), i.e. \(\sum _x\lambda f^p d_x\ge \sum _{x\sim y}\frac{4(p-1)}{p^2}(f^{p/2}(x)-f^{p/2}(y))^2 w\). The stated hypothesis \(\sum _x\lambda f^p d_x\ge \sum _x f^{p-1}Lf\) yields exactly (12.31), and the Moser iteration then gives the same conclusion.

Replace \(f\) by \(g_x=\psi _x\Pi ^{1/2}(H_t-I_0)\Pi ^{-1/2}\) in Theorem 428 (via Corollary 429). Using self-adjointness of \(H_{2t}-I_0\),

Since \(g_x\perp \phi _0\), we have \(e^{-t\lambda }\sum _y g_x^p(y)d_y\ge \sum _y g_x^{p-1}(y)Lg_x(y)\), so Corollary 429 gives

Therefore

with \(c=c''c_\delta ^{-1}\). Requiring the right side \(\le e^{-c_0}\) gives \(t\ge \frac{2c_0+\delta \log c+2\log (\operatorname {vol}G/\min _x d_x)}{\lambda \delta }=O\big(\frac{\log \operatorname {vol}G}{\lambda \delta }+\frac{c'}{\lambda }\big)\) with \(c'=\log (c''c_\delta ^{-1})\).