Main Theorems A–H

Open source document →

1. #1

   Step 1 (Restricted chain). Define the restricted sub-stochastic matrix on :

   $$P_F(i,j):=\frac{W_t(i,j)}{d_t(i)}(i,j\in F),{\tilde{P}}_F:=\frac{1}{2}(I{|}_F+P_F).$$
2. #2

   Step 2 (Conductance bound). The conductance of the restricted chain on (with absorbing boundary) is:

   $${\Phi }_F:=\underset{\varnothing \ne S⊊F}{\min }\frac{{\sum }_{i\in S}{\sum }_{j\in F\setminus S}{\tilde{P}}_F(i,j){\pi }_F(i)+{\sum }_{i\in S}\frac{r_{F,t}(i)}{2}{\pi }_F(i)}{{\pi }_F(S)}$$
3. #3

   The numerator's first term is the internal flow out of within ; the second term is the leakage from to the exterior. Consider the cut of within the full graph. For any :

   $$\sum _{i\in S}\sum _{j\notin S}{P}_t(i,j){\pi }_F(i)=\frac{{\mathrm{cut}}_t(S,V\setminus S)}{{\mathrm{vol}}_t(F)}\cdot {\mathrm{vol}}_t(S).$$
4. #4

   In the worst case (taking to be itself with absorbing exterior), the effective conductance is bounded by . More precisely, for any with :

   $${\Phi }_F(S)\le \frac{{\mathrm{cut}}_t(S,\bar{S})}{{\mathrm{vol}}_t(S)}\le {\varphi }_t(S).$$
5. #5

   Step 4 (Escape time). The expected absorption time from the quasi-stationary distribution satisfies (see Aldous--Fill, Theorem 12.4; or Montenegro--Tetali, Theorem 3.3):

   $${\mathbb{E}}_{{\pi }_F}[T_{\mathrm{esc}}]\ge \frac{1}{2{\tilde{\gamma }}_F}\ge \frac{1}{2\theta }.$$
6. #6

   (ii) Case . The optimal gauge satisfies the linear system (Theorem 7.11). The residual angles are . These solve:

   $$\tilde{\alpha }=(I-B^T{L}^{†}B\mathrm{diag}(W))\alpha =:\Pi \alpha .$$
7. #7

   The operator is the projection onto the cycle space of the graph. The residual curvature at node is:

   $$\rho (i)=\sum _{j\sim i}{W}_t(i,j){\tilde{\alpha }}_{ij}^2.$$
8. #8

   The source of non-zero is the curvature (holonomy around cycles). Near doors, the cycles passing through the exterior create non-trivial holonomy. The Green's function of the graph Laplacian on has the well-known decay property: for a graph with spectral gap ,

   $$|L^{†}(i,j)|\le \frac{C_0}{\mathrm{vol}(F^{\circ })}\cdot e^{-\sqrt{{\lambda }_2}{d}_{\mathrm{graph}}(i,j)}$$
9. #9

   At the optimal gauge , the Euler--Lagrange equation on each node reads:

   $$\sum _{j\sim i}{W}_t(i,j){\nabla }_{h(i)}{d}_G(g_t^h(i,j),e{)}^2=0.$$
10. #10

    The energy on is then controlled by a discrete maximum principle: interior values of cannot exceed boundary values (door-adjacent). Summing:

    $$\sum _{i\in F_{\mathrm{deep}}}\rho (i)\le \frac{|F_{\mathrm{deep}}|}{|F_{\mathrm{near}}|}\cdot \mu \cdot \sum _{i\in F_{\mathrm{near}}}\rho (i)$$
11. #11

    Denominator perturbation: .

    $$|{\varphi }^{\prime }-\varphi |=\left|\frac{\mathrm{cut}+{\Delta }_c}{\mathrm{vol}+{\Delta }_v}-\frac{\mathrm{cut}}{\mathrm{vol}}\right|=\left|\frac{{\Delta }_c\cdot \mathrm{vol}-\mathrm{cut}\cdot {\Delta }_v}{(\mathrm{vol}+{\Delta }_v)\cdot \mathrm{vol}}\right|.$$