Fruit

Open source document →

1. #1

   Step 1. Since there are no internal edges between and :

   $${\mathrm{cut}}_t(F,\bar{F})={\mathrm{cut}}_t(F_1,\bar{F})+{\mathrm{cut}}_t(F_2,\bar{F})$$
2. #2

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ):

   $${\mathrm{cut}}_t(F_k,\overline{F_k})={\mathrm{cut}}_t(F_k,V\setminus F_k)={\mathrm{cut}}_t(F_k,\bar{F})+0$$
3. #3

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ): (the zero comes from no -- edges). So:

   $${\mathrm{cut}}_t(F_k,\overline{F_k})={\mathrm{cut}}_t(F_k,\bar{F}).$$
4. #4

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ): (the zero comes from no -- edges). So: Step 2 (Both components satisfy (F2)). We show that both and satisfy the energy ratio condition (F2).

   $$\sum _{i,j\in F}{W}_t(i,j)\ge (1-\theta ){\mathrm{vol}}_t(F).$$
5. #5

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ): (the zero comes from no -- edges). So: Step 2 (Both components satisfy (F2)). We show that both and satisfy the energy ratio condition (F2).

   $$\sum _{i,j\in F}{W}_t(i,j)=\sum _{i,j\in F_1}{W}_t(i,j)+\sum _{i,j\in F_2}{W}_t(i,j).$$
6. #6

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ): (the zero comes from no -- edges). So: Step 2 (Both components satisfy (F2)). We show that both and satisfy the energy ratio condition (F2).

   $$\frac{{\sum }_{i,j\in F_k}{W}_t(i,j)}{{\mathrm{vol}}_t(F_k)}\ge (1-\theta ).$$
7. #7

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ): (the zero comes from no -- edges). So: Step 2 (Both components satisfy (F2)). We show that both and satisfy the energy ratio condition (F2).

   $$\sum _{i,j\in F}{W}_t(i,j)<(1-\theta ){\mathrm{vol}}_t(F_1)+{\mathrm{vol}}_t(F_2)\le (1-\theta ){\mathrm{vol}}_t(F),$$
8. #8

   Step 1. Since there are no internal edges between and : and in particular, for each component ( ): (the zero comes from no -- edges). So: Step 2 (Both components satisfy (F2)). We show that both and satisfy the energy ratio condition (F2).

   $${\mathrm{cut}}_t(F_k,\overline{F_k})={\mathrm{vol}}_t(F_k)-\sum _{i,j\in F_k}{W}_t(i,j)\le \theta \cdot {\mathrm{vol}}_t(F_k).$$
9. #9

   Conclusion. By Step 2, satisfies (F2). By Step 3, satisfies (F1). Therefore:

   $${\varphi }_t(F_1)=\frac{{\mathrm{cut}}_t(F_1,\overline{F_1})}{{\mathrm{vol}}_t(F_1)}\le \theta .$$
10. #10

    Lower bound ( ). Use the variational characterisation of and test with the normalised indicator of any set :

    $$f_S(i)=\{\begin{array}{ll}\sqrt{{\mathrm{vol}}_t(\bar{S})/{\mathrm{vol}}_t(V)}& i\in S,\\ -\sqrt{{\mathrm{vol}}_t(S)/{\mathrm{vol}}_t(V)}& i\notin S.\end{array}$$
11. #11

    Step 1. Volume decomposition:

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

    Step 1. Volume decomposition: Step 2. By (F2), . By (F1), . Thus:

    $${\mathrm{cut}}_t(F,\bar{F})={\varphi }_t(F)\cdot {\mathrm{vol}}_t(F)\le \theta \cdot {\mathrm{vol}}_t(F).$$
13. #13

    Step 5. The expected absorption time (escape time) from the stationary distribution satisfies the standard bound (see Levin--Peres--Wilmer, Theorem 12.4):

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