Theorem F — Spectral Stability

Prerequisites: Theorem A (energy isolation), Chapter 8.

Theorem F. Let $\Vert \delta W{\Vert }_{\infty }:={\max }_{i,j}|W_t^{\prime }(i,j)-W_t(i,j)|$.

(i) $|{\varphi }_t^{\prime }(F)-{\varphi }_t(F)|\le C_1\Vert \delta W{\Vert }_{\infty }|V{|}^2/{\mathrm{vol}}_t(F)$, where $C_1=2(1+\theta )\le 4$.

(ii) If ${\varphi }_t(F)\le \theta -ϵ$ with $ϵ>0$, then $F\in {\mathfrak{F}}_t^{\prime }$ provided $\Vert \delta W{\Vert }_{\infty }<ϵ\cdot {\mathrm{vol}}_t(F)/(C_1|V{|}^2)$.

Proof. (Complete; reproduced from Chapter 8.)

(i) Write $\varphi =\mathrm{cut}/\mathrm{vol}$ (under (F1), denominator is $\mathrm{vol}(F)$).

Numerator perturbation: $|{\Delta }_{\mathrm{cut}}|\le |F|\cdot |\bar{F}|\cdot \Vert \delta W{\Vert }_{\infty }\le |V{|}^2\Vert \delta W{\Vert }_{\infty }$.

Denominator perturbation: $|{\Delta }_{\mathrm{vol}}|\le |F|\cdot |V|\cdot \Vert \delta W{\Vert }_{\infty }\le |V{|}^2\Vert \delta W{\Vert }_{\infty }$.

Numerator: $|{\Delta }_c\cdot \mathrm{vol}-\mathrm{cut}\cdot {\Delta }_v|\le \Vert \delta W{\Vert }_{\infty }|V{|}^2(\mathrm{vol}+\mathrm{cut})\le \Vert \delta W{\Vert }_{\infty }|V{|}^2(1+\theta )\mathrm{vol}$.

Denominator: $(\mathrm{vol}+{\Delta }_v)\cdot \mathrm{vol}\ge {\mathrm{vol}}^2/2$ for $|{\Delta }_v|\le \mathrm{vol}/2$.

Result: $|{\varphi }^{\prime }-\varphi |\le 2(1+\theta )\Vert \delta W{\Vert }_{\infty }|V{|}^2/\mathrm{vol}=C_1\Vert \delta W{\Vert }_{\infty }|V{|}^2/\mathrm{vol}$.

(ii) Set ${\delta }_0=ϵ/(C_1|V{|}^2/{\mathrm{vol}}_t(F))$. Then $|{\varphi }^{\prime }-\varphi |<ϵ$, so ${\varphi }_t^{\prime }(F)<\theta$. Volume condition preserved similarly. $\square$

Explicit constant. $C_1=2(1+\theta )$. For $\theta =0.1$, $C_1=2.2$. The perturbation size requirement is $\Vert \delta W{\Vert }_{\infty }<\frac{ϵ\mathrm{vol}(F)}{2.2|V{|}^2}$, or equivalently $\Vert \delta W{\Vert }_{\infty }\cdot \frac{|V{|}^2}{\mathrm{vol}(F)}<\frac{ϵ}{2.2}$.