The book asserts this counterexample without giving the explicit eigenfunction and the failing inequality; it should be reconstructed.

Sketch: let \(a,b\in \mathcal{K}\), \(x\in \delta S\), with \(ax,bx\in S\). Since \(a^{-1},b^{-1}\in \mathcal{K}\), the vertex \(x\) is adjacent to both \(ax\) and \(bx\), so \(ax\) and \(bx\) are joined by a path of length \(2\) through \(x\notin S\). If \(ax\not\sim bx\) and \(ax\neq bx\), this path is a shortest path leaving \(S\), contradicting (B); hence \(ax\sim bx\), which in the invariant/abelian setting gives \(b^{-1}a\in \mathcal{K}\). The degenerate case \(ax=bx\) and the exact passage \(ab^{-1}\in \mathcal{K}\Rightarrow b^{-1}a\in \mathcal{K}\) in a general (nonabelian) group are not spelled out in the book and need to be completed.

Let \(S_1,S_2\) be strongly convex and \(S=S_1\cap S_2\). Take \(a,b\in \mathcal{K}\) and \(x\in \delta S\) with \(ax\in S\) and \(bx\in S\); then \(ax,bx\in S_1\) and \(ax,bx\in S_2\). Since \(x\in \delta S\) we have \(x\notin S_1\cap S_2\), so \(x\notin S_1\) or \(x\notin S_2\). Suppose \(x\notin S_1\). As \(x\) is adjacent to the vertex \(ax\in S_1\cap S_2\subseteq S_1\), we have \(x\in \delta S_1\); and \(ax,bx\in S_1\). By strong convexity of \(S_1\) (condition (A)), \(b^{-1}a\in \mathcal{K}\). The case \(x\notin S_2\) is symmetric, using \(S_2\). Hence \(S\) satisfies (A) and is strongly convex.

We verify condition (B) for \(H_i\), which by 342 yields strong convexity. A single edge changes exactly two coordinates by \(\pm 1\), so the graph distance between \(u,v\in V(\Gamma _t)\) equals \(\tfrac 12\sum _l|u_l-v_l|\), and a shortest path moves one unit at a time from a coordinate that must decrease to one that must increase, never moving a coordinate in both directions. For such a path the \(i\)-th coordinate is monotone between \(u_i\) and \(v_i\), hence stays \(\ge \min (u_i,v_i)\). If \(u,v\in H_i\) then \(u_i,v_i\ge 0\), so every intermediate vertex has \(i\)-th coordinate \(\ge 0\) and lies in \(H_i\). Thus (B) holds and \(H_i\) is strongly convex. By 343 the intersection \(\bigcap _i H_i\) is strongly convex.

Let \(X\subseteq \delta (F_1\cap F_2)\). Partition \(X\) into \(X_1=X\cap \delta F_1\) and \(X_2=X\setminus \delta F_1\); clearly \(X_2\subseteq F_1\). Since \(F_1\) and \(F_2\) are convex,

Since \(N^{*}(X_2)\setminus F_2\subseteq F_1\setminus \delta F_1\), the two sets are disjoint:

Hence

so \(F_1\cap F_2\) is convex.

The reduction of \(S\) to an intersection of single-entry halfplanes is immediate, and convexity of \(S\) then follows from 346 once each halfplane is shown convex. The verification of the boundary expansion property (9.2) for an individual halfplane is stated in the book only as “easy to see” and is left to be completed.

Every summand of \(Lg(v)=\frac1k\sum _{a\in \mathcal{K}}\bigl(g(v)-g(av)\bigr)\) is non-negative, so the sum is non-negative.

Using \(f^2(x)-f^2(ax)=2f(x)\bigl(f(x)-f(ax)\bigr)-\bigl(f(x)-f(ax)\bigr)^2\) and summing over \(a\in \mathcal{K}\),

The first term equals \(2f(x)\, Lf(x)=2\lambda f^2(x)\), giving the claim.

By definition,

With \(p=f(x)-f(ax)\) and \(q=f(bx)-f(abx)\) we have \(p^2-q^2=-(p-q)^2+2(p-q)p\), where \(p-q=f(x)-f(ax)-f(bx)+f(abx)\), so

The first term is \(\le 0\). Writing \(f(abx)=f(bax)+\bigl(f(abx)-f(bax)\bigr)\),

For the inner sum of the first term, \(\frac1k\sum _b\bigl(f(x)-f(bx)\bigr)=Lf(x)=\lambda f(x)\) and \(\frac1k\sum _b\bigl(f(bax)-f(ax)\bigr)=-Lf(ax)=-\lambda f(ax)\), so \(\frac1k\sum _b\bigl(f(x)-f(ax)-f(bx)+f(bax)\bigr)=\lambda \bigl(f(x)-f(ax)\bigr)\), and the first term equals \(\frac{2\lambda }{k}\sum _a\bigl(f(x)-f(ax)\bigr)^2\). For the second term, invariance \(a\mathcal{K}a^{-1}=\mathcal{K}\) lets us reindex \(b\mapsto aba^{-1}\in \mathcal{K}\), under which \(abx=(aba^{-1})ax\) and so \(\sum _b f(abx)=\sum _b f(bax)\); hence \(\sum _b\bigl(f(abx)-f(bax)\bigr)=0\). Therefore

Write \(\rho (x)=\frac1k\sum _{a\in \mathcal{K}}\bigl(f(x)-f(ax)\bigr)^2\) and \(\Phi (x)=\rho (x)+\alpha \lambda f^2(x)\). Combining 351 (\(L\rho \le 2\lambda \rho \)) and 350 (\(Lf^2=2\lambda f^2-\rho \)),

Let \(v\) maximize \(\Phi \). By 349, \(0\le L\Phi (v)\le 2\alpha \lambda ^2 f^2(v)-(\alpha -2)\lambda \, \rho (v)\), so for \(\alpha {\gt}2\),

Hence for every \(x\),

which is the assertion.

Take \(\alpha =4\) in 352: then \(\frac{\alpha ^2}{\alpha -2}=8\), and dropping the non-negative term \(\alpha \lambda f^2(x)\) on the left gives the bound.

By the Dirichlet condition, \(f(x)=0\) for every \(x\in \delta S\). To extend \(f\) to the vertices lying just outside \(S\cup \delta S\), we impose the system of \(|\delta S|\) equations

whose unknowns are the values \(f(z)\) for \(z\notin S\cup \delta S\) with \(z\sim y\in S\cup \delta S\). This is a linear system in which each equation is indexed by a boundary vertex and involves the unknowns adjacent to it. The boundary expansion property (9.2) says that any \(j\) of these equations (\(j\le |\delta S|\)) involve at least \(j\) distinct unknowns; by Hall’s condition the equation–variable incidence has a system of distinct representatives, so the system can be solved (choose a private variable for each equation and back-substitute). Hence the extension exists.

By 354 we may assume \(f\) is extended so that \(Lf=\lambda f\) holds on \(S\cup \delta S\). For \(g\in \mathcal{K}\) put \(\phi _g(x)=\bigl(f(x)-f(gx)\bigr)^2+k\alpha \lambda f^2(x)\) for \(x\in S\cup \delta S\). The maximum of \(\phi _g(x)\) over \(g\in \mathcal{K}\) and \(x\in S\cup \delta S\) is attained at some edge \(\{ z,az\} \) with \(z\in S\): if the maximum were at \(x\in \delta S\), then \(f(x)=0\) so \(\phi _g(x)=f^2(gx)\), whereas the reverse edge gives \(\phi _{g^{-1}}(gx)=f^2(gx)+k\alpha \lambda f^2(gx)\ge \phi _g(x)\), with \(gx\in S\) (else \(f(gx)=0\) and \(\phi _g(x)=0\)).

Write \(\phi =\phi _a\). For \(x\in S\),

Using \(p^2-q^2=2(p-q)p-(p-q)^2\) with \(p=f(x)-f(ax)\), \(q=f(bx)-f(abx)\) and discarding the negative square,

since \(\frac1k\sum _b(f(x)-f(bx))=Lf(x)=\lambda f(x)\) and \(\frac1k\sum _b(f(ax)-f(abx))=Lf(ax)=\lambda f(ax)\) on \(S\cup \delta S\). Also, using \(f^2(x)-f^2(bx)=2(f(x)-f(bx))f(x)-(f(x)-f(bx))^2\),

Now let \(z\) be the maximizer above. By 349, \(0\le L\phi (z)\le Y+Z\). Since \(\bigl(f(z)-f(az)\bigr)^2\le \sum _b\bigl(f(z)-f(bz)\bigr)^2\),

so for \(\alpha {\gt}2\),

Finally, for all \(x\in S\), \(g\in \mathcal{K}\) with \(gx\in S\),

Take \(\alpha =4\) in 355, so \(\frac{k\lambda \alpha ^2}{\alpha -2}=8k\lambda \), and drop the non-negative term \(k\alpha \lambda f^2(x)\) on the left.

For \(g\in \mathcal{K}\) put \(\phi _g(x)=\bigl(f(x)-f(gx)\bigr)^2+k\alpha \lambda f^2(x)\), and let \(\{ z,az\} \) be an edge in \(S\) at which the maximum of \(\phi _g(x)\), over all \(g\in \mathcal{K}\) and \(x,gx\in S\), is achieved.

Claim: \(\phi _g(x)\le \phi _a(z)\) for all \(x,gx\in \delta S\cup S\). We treat three cases; throughout, the Neumann condition means that at a boundary vertex \(x\) the value \(f(x)\) is the average of \(f\) over the neighbors of \(x\) lying in \(S\), and \(\left(\tfrac 1w\sum b_i\right)^2\le \tfrac 1w\sum b_i^2\) is convexity (359).

Case 1: \(gx\in S\), \(x\in \delta S\). Let \(W=\delta x\cap S\), \(w=|W|\), so the Neumann condition gives \(f(x)=\frac1w\sum _{b\in W}f(bx)\). Then

By strong convexity, \(bx\sim gx\) for every \(b\in W\), so each summand equals \(\phi _{gb^{-1}}(bx)\le \max _g\phi _g(bx)\); hence \(\phi _g(x)\le \frac1w\sum _{b\in W}\max _g\phi _g(bx)\le \phi _a(z)\).

Case 2: \(gx\in \delta S\), \(x\in S\). Let \(W'=\delta (gx)\cap S\), \(w'=|W'|\), so \(f(gx)=\frac1{w'}\sum _{b\in W'}f(bgx)\). Then

using that \(bgx\sim x\) by strong convexity.

Case 3: \(x,gx\in \delta S\). Put \(W_1=\{ b:bx\in S,\ bgx\in S\} \), \(W_2=\{ b:bx\in S,\ bgx\notin S\} \), \(W_3=\{ b:bx\notin S,\ bgx\in S\} \), with \(w_i=|W_i|\) and \(w=w_1+w_2+w_3\). Using the Neumann conditions at \(x\) and at \(gx\) one checks

which exhibits \(f(x)-f(gx)\) as a mean of the \(w\) differences \(\{ f(bx)-f(bgx)\} _{b\in W_1}\), \(\{ f(bx)-f(gx)\} _{b\in W_2}\), \(\{ f(x)-f(bgx)\} _{b\in W_3}\); likewise \(f(x)\) is the mean of \(\{ f(bx)\} _{b\in W_1\cup W_2}\) together with \(w_3\) copies of \(f(x)\). By convexity,

Grouping term by term: for \(b\in W_1\) both \(bx,bgx\in S\) and \(bx\sim bgx\), giving \(\phi _g(bx)\le \phi _a(z)\); for \(b\in W_2\) we have \(bx\sim gx\) (since \(bgx\in \delta S\) has neighbors \(bx,gx\in S\), so strong convexity applies), reducing to Case 2; for \(b\in W_3\) we have \(x\sim bgx\) (since \(bx\in \delta S\) has neighbors \(x,bgx\in S\)), reducing to Case 1. Each grouped term is \(\le \phi _a(z)\), hence \(\phi _g(x)\le \phi _a(z)\). This proves the Claim.

Given the Claim, \(z\) maximizes \(\phi =\phi _a\) over all relevant edges, and the remaining maximum-principle computation is identical to that in the proof of 355: \(0\le L\phi (z)\) yields \(\bigl(f(z)-f(az)\bigr)^2\le \frac{2k\lambda \alpha }{\alpha -2}f^2(z)\), and therefore \(\bigl(f(x)-f(ax)\bigr)^2+k\alpha \lambda f^2(x)\le \frac{k\lambda \alpha ^2}{\alpha -2}\sup _{y\in S}f^2(y)\).

Take \(\alpha =4\) in 357, so \(\frac{k\lambda \alpha ^2}{\alpha -2}=8k\lambda \), and drop the non-negative term \(k\alpha \lambda f^2(x)\) on the left.

Let \(f\) be an eigenfunction on \(S\) achieving \(\lambda _S=\lambda \), normalized so that \(\sup _{x\in S}|f(x)|=1=\sup _{x\in S}f(x)\). Let \(u\in S\) with \(f(u)=\max _{x\in S}f(x)=1\), and let \(v\in S\) with \(f(v){\lt}0\); such \(v\) exists because \(\sum _{x\in S}f(x)=0\). Choose a shortest path \(P=(u=v_0,v_1,\dots ,v_t=v)\) in \(S\), so \(t\le D\). Set

By 358, each term satisfies \(\bigl(f(v_i)-f(v_{i+1})\bigr)^2\le 8k\lambda \sup _{y\in S}f^2(y)=8k\lambda \), so

On the other hand, by 359 applied to \(b_i=f(v_i)-f(v_{i+1})\) (note \(\sum _i b_i=f(u)-f(v)\)) and \(t\le D\),

since \(f(u)=1\) and \(f(v){\lt}0\) give \(f(u)-f(v){\gt}1\). Combining the two bounds, \(\frac1D\le 8k\lambda D\), whence \(\lambda \ge \frac{1}{8kD^2}\).