<p>I am reading the <a href="http://arxiv.org/abs/1111.1055" rel="nofollow">paper</a> above by Lee, Gharan and Trevisan, and I am having trouble with <strong>lemma 4.8</strong> on page 23. How do we form the set $T_1, \ldots, T_{r'}$ such that $r'&gt;(1-\delta/2)k$ and each set $T_i$ satisfies both the upper bound and lower bound with respect to $\epsilon$ as in the paper ?
I am struggling with this for a while, so any help is greatly appreciated.</p>

CC BY-SA 3.0
2013-07-01T20:58:27.557Z
Why not ask the authors?
vb le
CC BY-SA 3.0
2013-07-01T22:43:58.700Z
$T_1$ is the union of $S_1, \ldots, S_{i_1}$ where $i_1$ is the first number s.t. the bounds on top of p. 23 are satisfied. $T_2$ is the union of $S_{i_1 + 1}, \ldots, S_{i_2}$ where $i_2$ is defined similarly. You get the idea...
Sasho Nikolov
CC BY-SA 3.0
2013-07-05T03:42:00.673Z
Thank you Sasho. You meant $diam(S_{i_1})\leq \Delta$ ? The partition guarantees $S_i$ always satisfies that for all i. The problem is that when we union a few $S_i$, that property may no longer hold. 
Since the $T_i$'s have to satisfy both the upper and the lower bounds at the same time, taking union of too few $S_i$ may not give us the lower bound while taking union of too many $S_i$ may violates $diam(T_i)\leq \Delta$ (thus, will not give us the upper bound).
Son P Nguyen
<spectral-graph-theory>
Multi-way spectral partitioning and higher-order Cheeger inequalities
Son P Nguyen
# Multi-way spectral partitioning and higher-order Cheeger inequalities

(Asked by: username_0 on 2013-07-01)

I am reading the [paper](http://arxiv.org/abs/1111.1055) above by Lee, Gharan and Trevisan, and I am having trouble with **lemma 4.8** on page 23. How do we form the set $T\_1, \ldots, T\_{r'}$ such that $r'>(1-\delta/2)k$ and each set $T\_i$ satisfies both the upper bound and lower bound with respect to $\epsilon$ as in the paper ?
I am struggling with this for a while, so any help is greatly appreciated.

**Tags:** spectral-graph-theory

> **Comments:**
> **username_1**: Why not ask the authors?  
> **username_2**: $T_1$ is the union of $S_1, \ldots, S_{i_1}$ where $i_1$ is the first number s.t. the bounds on top of p. 23 are satisfied. $T_2$ is the union of $S_{i_1 + 1}, \ldots, S_{i_2}$ where $i_2$ is defined similarly. You get the idea...  
> **username_0**: Thank you Sasho. You meant $diam(S_{i_1})\leq \Delta$ ? The partition guarantees $S_i$ always satisfies that for all i. The problem is that when we union a few $S_i$, that property may no longer hold.  Since the $T_i$'s have to satisfy both the upper and the lower bounds at the same time, taking union of too few $S_i$ may not give us the lower bound while taking union of too many $S_i$ may violates $diam(T_i)\leq \Delta$ (thus, will not give us the upper bound).  

---

## 0 answers

