Small-set amplification — Lemma 4.2

If $\alpha \le 0$, then $\rho \alpha n\le 0$, so the minimum in the conclusion is nonpositive and the conclusion follows from nonnegativity of cardinality. Hence suppose $\alpha >0$. The norm bound in [F1] then implies $d^{\ast }\ge 0$. If $d^{\ast }=0$, the same bound gives $A=0$. Connectedness therefore forces $n=1$: a path between distinct vertices would contain an edge. If ${\mathcal{C}}_{\beta }$ is empty, the first quantity in the minimum is zero; otherwise nesting gives $\mathrm{\mid }{\mathcal{C}}_{\gamma }\mathrm{\mid }=1\ge n\mathrm{/}2$. Thus the conclusion holds when $d^{\ast }=0$.

Now suppose $d^{\ast }>0$. The two matrix-order bounds in [F1], tested on a nonzero vector, give $c^{+}\ge c^{-}$. The assumed inequality $c^{+}\mathrm{\ne }{c}^{-}$ therefore gives $c^{+}-c^{-}>0$. Put $X={\mathcal{C}}_{\beta }$, $Y={\mathcal{C}}_{\gamma }$, $k=1+c^{-}-\epsilon >0$, and $s=\sin (\beta -\gamma )$. Suppose for contradiction that $\mathrm{\mid }Y\mathrm{\mid }$ is smaller than the stated minimum. Then $\mathrm{\mid }Y\mathrm{\mid }<n\mathrm{/}2$, $\mathrm{\mid }Y\mathrm{\mid }<(1+\epsilon \mathrm{/}(c^{+}-c^{-}))\mathrm{\mid }X\mathrm{\mid }$, and $\mathrm{\mid }Y\mathrm{\mid }<\rho \alpha n$. By nesting, $\mathrm{\mid }X\mathrm{\mid }\le \mathrm{\mid }Y\mathrm{\mid }<\rho \alpha n$. Thus all hypotheses of [F4] hold.

The bound and normalization in [F3] verify the order-parameter hypothesis of the three-region kernel inequality. By [F4], $e(X,Y^c)>ke(X,X)\mathrm{/}(2(1+\rho )\alpha )$. The angular hypothesis gives $s\ge 2(1+\rho )\alpha \mathrm{/}k>0$. Multiplying the strict inequality by $s$ and using $e(X,X)\ge 0$ yields $se(X,Y^c)>e(X,X)$. This contradicts the inequality in [F3]. Hence the supposition in step 2.1 is impossible, proving the conclusion in all cases.