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,\bar{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,\bar{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,\bar{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:

   $$\phi_t(F_1)=\frac{\mathrm{cut}_t(F_1,\bar{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{cases}\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{cases}$$
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)=\phi_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}.\qquad\square$$