Expand the left side as \(\sum _{i=0}^{n}x_{i+1}y_i-\sum _{i=0}^{n}x_i y_i\) and reindex the first sum by \(i\mapsto i-1\) to obtain \(\sum _{i=1}^{n+1}x_i y_{i-1}-\sum _{i=0}^{n}x_i y_i=\sum _{i=1}^{n}x_i(y_{i-1}-y_i)+x_{n+1}y_n-x_0y_0\). The stated vanishing is immediate.

Label the vertices so that \(f(v_1)\ge f(v_2)\ge \cdots \ge f(v_n)\), and abbreviate \(f(i)=f(v_i)\), \(d_i=d_{v_i}\). For \(1\le i\le n-1\) let \(A_i=\{ \{ v_j,v_k\} \in E(G):j\le i{\lt}k\} \) be the set of edges of the cut \((\{ v_1,\dots ,v_i\} ,\{ v_{i+1},\dots ,v_n\} )\) and put \(a_i=|A_i|\). Set

so that \(S_i=S_i^{+}\) when \(f(i)\ge m\) and \(S_i=S_i^{-}\) when \(f(i){\lt}m\), and \(S_i\) is the volume of the smaller side of the cut \(A_i\). By 1,

Use the convention \(S_0=S_{n+1}=0\), set \(h(i)=f(i)-m\), and let \(i_0\) satisfy \(f(i_0)=m\), so \(h(i)\ge 0\) for \(i\le i_0\) and \(h(i){\lt}0\) for \(i{\gt}i_0\). Since \(f\) is monotone, applying Lemma 387,

We treat \(W_1\); \(W_2\) is symmetric. Writing \(S_{i+1}=S_i+d_i\) on this side and using \((S_i+d_i)^{\frac{\delta -1}{\delta }}-S_i^{\frac{\delta -1}{\delta }}\ge \frac{\delta -1}{\delta }\, d_i\, S_i^{-1/\delta }\),

where the middle inequality uses \(\big(h(i)^{\frac{\delta }{\delta -1}}S_i\big)^{1/\delta }\le \big(\sum _{i\le i_0}|h(i)|^{\frac{\delta }{\delta -1}}d_i\big)^{1/\delta }\). Combining with the analogous bound for \(W_2\) and applying Lemma 383 (superadditivity of \(x\mapsto x^{\frac{\delta -1}{\delta }}\)),

which is the claim with \(c_1=c_\delta \frac{\delta -1}{\delta }\).

Let \(m_0\) be the value of \(m\) produced in Theorem 388. Since the minimum over \(m\) is at most the value at \(m=m_0\),

This follows from the proof of Theorem 388 applied to the truncated function \(f_w\). In the ordering of that proof, \(f_w\) is constant equal to \(f(w)\) outside \(S_w\), so all cuts \(A_i\) with \(f(i)\) strictly between \(m\) and \(f(w)\) contribute nothing, and for \(f(w)\ge m\)

by Lemma 387. Adding \(a_w|f(w)-m|\) and running the \(W_1\)-estimate of Theorem 388 over the vertices of \(S_w\) yields the stated lower bound.

Use the notation of Theorem 388: order \(f(1)\ge \cdots \ge f(n)\), set \(h(i)=f(i)-m\) with \(f(i_0)=m\), and write \(h_i(x)=h_{v_i}(x)\) for the truncation of Corollary 390 at \(w=v_i\). Representing the square of a gradient through its level cuts,

We bound \(P_1\), assuming without loss of generality that all \(h(i){\gt}0\); \(P_2\) is symmetric. Applying summation by parts (Lemma 387) and then Corollary 390 to the inner sums,

Hence \(2P_1\ge \sum _{i\le i_0}h(i)a_{i+1}(h(i)-h(i+1))\). Applying Lemma 387 once more,

so that

Define

By Corollary 390, \(T_i=\sum _{u\sim v}|f_{v_i}(u)-f_{v_i}(v)|+a_i(f(i)-m)\ge c_\delta \frac{\delta -1}{\delta }\, T_i'^{\, \frac{\delta -1}{\delta }}\), and directly from the definition \(T_i-T_{i-1}=(a_i-a_{i-1})h(i-1)\), so \((a_{i+1}-a_i)h(i)=T_{i+1}-T_i\). Using \(T_{i+1}'=T_i'+h(i)^{\frac{\delta }{\delta -1}}d_i\) and \((1+x)^{\frac{\delta -1}{\delta }}-1\ge \frac{\delta -1}{\delta }\, x\, (1+x)^{-1/\delta }\),

the last two steps using Hölder’s inequality (Lemma 382) and \(T_i'^{\, 1/\delta }\le \big(\sum _{i{\lt}i_0}h(i)^{\frac{\delta }{\delta -1}}d_i\big)^{1/\delta }\), with \(\gamma =\frac{2\delta }{\delta -2}\) so that \(2/\gamma =\frac{\delta -2}{\delta }\). Symmetrically \(P_2\ge c_\delta \frac{(\delta -1)^2}{4\delta ^2}\big(\sum _{i{\gt}i_0}|h(i)|^{\gamma }d_i\big)^{2/\gamma }\). Since \(\gamma \ge 2\), i.e. \(2/\gamma \le 1\), superadditivity (Lemma 383) gives

Taking square roots yields the inequality at this \(m\) with \(c_2=\sqrt{c_\delta }\, \frac{\delta -1}{2\delta }\); minimizing the right-hand side over \(m\) gives the stated form.

Apply Hölder’s inequality (Lemma 382) with \(\frac1p+\frac1q=1\), \(p=\gamma -1\), \(q=\frac{\gamma -1}{\gamma -2}\), and

which gives

It remains to prove \(\sum _{y}\big|\frac{H_{t/2}(x,y)}{\sqrt{d_y}}-m\big|d_y\le 3\sqrt{d_x}\). Put \(m'=\frac{\sqrt{d_x}}{\operatorname {vol}G}\). By Lemma 365, \(\sum _y H_{t/2}(x,y)\sqrt{d_y}=\sqrt{d_x}\), hence

Writing \(N_x^{-}=\{ y:H_{t/2}(x,y)/\sqrt{d_y}{\lt}m'\} \), equation 6 gives \(\sum _y|\frac{H_{t/2}(x,y)}{\sqrt{d_y}}-m'|d_y=2\sum _{y\in N_x^{-}}(m'-\frac{H_{t/2}(x,y)}{\sqrt{d_y}})d_y\le 2\sum _{y\in N_x^{-}}m'd_y=2\frac{\sqrt{d_x}}{\operatorname {vol}G}\sum _{y\in N_x^{-}}d_y\le 2\sqrt{d_x}\). Therefore, provided \(m'\ge m/2{\gt}0\),

Finally \(m'\ge m/2\): with \(M_x^{+}=\{ y:H_{1/2}(y,x)/\sqrt{d_y}\ge m\} \) (of volume \(\ge \operatorname {vol}G/2\) by the definition of \(m\)) and \(H\ge 0\),

Set \(\gamma =\frac{2\delta }{\delta -2}\). By the semigroup property \(H_t(x,y)=\sum _z H_{t/2}(x,z)H_{t/2}(z,y)\) and symmetry, \(H_t(x,x)=\sum _y H_{t/2}(x,y)^2\). Differentiating and using that \(y\mapsto H_{t/2}(x,y)\) solves the heat equation,

Applying Theorem 391 to \(y\mapsto H_{t/2}(y,x)/\sqrt{d_y}\),

Insert Lemma 392: since \(\big(\sum _y(\cdot )^{\gamma }d_y\big)^{2/\gamma }=\big[\big(\sum _y(\cdot )^{\gamma }d_y\big)^{\frac{1}{\gamma -1}}\big]^{\frac{2(\gamma -1)}{\gamma }}\ge \big[\sum _y(\frac{H_{t/2}}{\sqrt{d}}-m)^2 d_y\big]^{\frac{2(\gamma -1)}{\gamma }}(3\sqrt{d_x})^{-\frac{2(\gamma -2)}{\gamma }}\), and using \(\sum _y(\frac{H_{t/2}(x,y)}{\sqrt{d_y}}-m)^2 d_y\ge \sum _y(\frac{H_{t/2}(x,y)}{\sqrt{d_y}}-m')^2 d_y=H_t(x,x)-2m'\sqrt{d_x}+m'^2\operatorname {vol}G=H_t(x,x)-\frac{d_x}{\operatorname {vol}G}\) (by 6 and \(m'=\sqrt{d_x}/\operatorname {vol}G\)),

Note \(1-\frac{2(\gamma -1)}{\gamma }=-\frac{2}{\delta }\) and \(\frac{2(\gamma -2)}{\gamma }=\frac{4}{\delta }\). Writing \(u(t)=H_t(x,x)-\frac{d_x}{\operatorname {vol}G}\ge 0\),

Integrating from \(0\) to \(t\) and using \(u(0)=H_0(x,x)-\frac{d_x}{\operatorname {vol}G}=1-\frac{d_x}{\operatorname {vol}G}\le 1\),

so that, since \(\frac{2(\gamma -2)}{\gamma }\cdot \frac{\delta }{2}=2\),

Summing over \(x\) and using \(\sum _x d_x/\operatorname {vol}G=1\) gives \(\sum _x H_t(x,x)-1\le c_3\operatorname {vol}G/t^{\delta /2}\). Finally, by the spectral decomposition \(\sum _x H_t(x,x)=\sum _x\sum _i e^{-\lambda _i t}\phi _i^2(x)=\sum _i e^{-\lambda _i t}\), whence \(\sum _{i\neq 0}e^{-\lambda _i t}=\sum _i e^{-\lambda _i t}-1\le c_3\operatorname {vol}G/t^{\delta /2}\).

Since the eigenvalues are ordered, for every \(t{\gt}0\) Theorem 393 gives

Hence \(k\le c_3\operatorname {vol}G\cdot \inf _{t{\gt}0}\frac{e^{\lambda _k t}}{t^{\delta /2}}\). The function \(t\mapsto e^{\lambda _k t}/t^{\delta /2}\) is minimized at \(t=\frac{\delta }{2\lambda _k}\), giving value \(\big(\frac{2\lambda _k e}{\delta }\big)^{\delta /2}\), so \(k\le c_3\operatorname {vol}G\big(\frac{2\lambda _k e}{\delta }\big)^{\delta /2}\). Solving for \(\lambda _k\),