Sparsest-cut and negative-type metrics
Recall that the sparsest-cut value $\beta$ is
defined as:
\[
\beta = \min_{\varnothing\neq S\subseteq V}\;
\frac{|\delta(S,\overline{S})|}{|S|\cdot|\overline{S}|}
\]
Arora-Rao-Vazirani: Key Theorem
Assume $x_1,\dots,x_n\in S^{d-1}=
\{x\in\mathbb{R}^d\,|\,\|x\|=1\}$ are
such that for all $i,j,k\in[n]$
it holds that $\angle x_ix_jx_k \leq \pi/2$,
as well as:
\[
\frac{1}{\binom{n}{2}}\sum_{i 0
\]
then there exist
$S,T$ such that:
- $|S|=\Omega(n)$,
- $|T|=\Omega(n)$,
- $d(S,T)=\Omega\Big(\frac{1}{\sqrt{\log n}}\Big)$, and
- $d(x_i,x_j)=\|x_i-x_j\|^2$
and so forth until the end of proof.
$\square$
|