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

For stationary edge flow $Q(x,y)={\pi }^G(x)P(x,y)$, the bottleneck ratio isUsing $f=1_S$ in the variational characterization,Taking the infimum gives ${\gamma }^G\le 2{\Phi }_{\ast }^G$.

Put $B_r=B(x,s+r)$. Every transition leaving $B_r$ enters $B_{r+1}$, and stationarity bounds its flow by the stationary mass newly reached:While ${\pi }^G(B_r)\le 1/2$, the definition of ${\Phi }_{\ast }^G$ therefore givesIteration for $r=0,\dots ,t-1$ proves the formula.

Choose vertices $x,y$ at distance $d_G$, put $r=\lfloor (d_G-1)/4\rfloor$ and $R=\lfloor (d_G-1)/2\rfloor$. The radius-$R$ balls about $x$ and $y$ are disjoint, so one has stationary mass at most $1/2$; call its center $z$. Apply part b from radius $r$ to radius $R$:Here the exponent should be $R-r$, and $R-r\ge (d_G-2)/4$. ThereforeSince the relaxation time is $t_{\mathrm{rel}}^G=1/{\gamma }^G$, part a yields