For stationary edge flow $Q(x,y)=\pi^G(x)P(x,y)$, the <bottleneck ratio> is
$$
\Phi_*^G
=\min_{0<\pi^G(S)\leq1/2}
\frac{Q(S,S^c)}{\pi^G(S)}.
$$
Using $f=\mathbf1_S$ in the variational characterization,
$$
\gamma^G
\leq\frac{\mathcal E(f,f)}{\operatorname{Var}_{\pi^G}f}
=\frac{Q(S,S^c)}{\pi^G(S)\pi^G(S^c)}
\leq2\frac{Q(S,S^c)}{\pi^G(S)}.
$$
Taking the infimum gives $\gamma^G\leq2\Phi_*^G$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 215 / 4 / a / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/iii/paper-215/4/a/solution