I am reading the paper 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.

  • 7
    $\begingroup$ Why not ask the authors? $\endgroup$ – vb le Jul 1 '13 at 20:58
  • 1
    $\begingroup$ $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... $\endgroup$ – Sasho Nikolov Jul 1 '13 at 22:43
  • $\begingroup$ 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). $\endgroup$ – Son P Nguyen Jul 5 '13 at 3:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.