Theorem A — Energy Isolation

Prerequisites: Chapters 2–8 (all of Part I).

Theorem A. For any fruit $F\in {\mathfrak{F}}_t$: $\frac{{\sum }_{i,j\in F}{W}_t(i,j)}{{\mathrm{vol}}_t(F)}\ge 1-\theta .$

Proof. (Complete; reproduced from Chapter 4.)

Step 1. ${\mathrm{vol}}_t(F)={\sum }_{i,j\in F}{W}_t(i,j)+{\mathrm{cut}}_t(F,\bar{F})$.

Step 2. By (F2), ${\varphi }_t(F)\le \theta$. By (F1), ${\mathrm{vol}}_t(F)=\min \{{\mathrm{vol}}_t(F),{\mathrm{vol}}_t(\bar{F})\}$, so ${\mathrm{cut}}_t(F,\bar{F})\le \theta \cdot {\mathrm{vol}}_t(F)$.

Step 3. ${\sum }_{i,j\in F}{W}_t(i,j)\ge (1-\theta ){\mathrm{vol}}_t(F)$. Divide by ${\mathrm{vol}}_t(F)>0$. $\square$

Sharpness. Equality when ${\varphi }_t(F)=\theta$ and ${\mathrm{vol}}_t(F)=\frac{1}{2}{\mathrm{vol}}_t(V)$.