On embedding expanders into \(\ell_p\) spaces (Q1376045): Difference between revisions

If \(M\) is a metric space, with metric \(\rho\), and \(X\) a normed space, a map \(f: M\to X\) is called a \(D\)-embedding \((D\geq 1)\) if \[ {1\over D} \rho(x, y)\leq\|f(x)- f(y)\|\leq \rho(x, y)\quad\text{for any }x,y\in M. \] The number \(D\) is called the distortion of the mapping. The result of the paper is the following: there exists constants \(c_1>0\) and \(n_0\) such that for any \(p\geq 1\) and any \(n\geq n_0\) there is a \(n\)-point metric space which \(D\)-embeds into \(\ell_p\) only for \(D\geq (c_1/p)\log n\). Conversely, any \(n\)-point metric space can be embedded into \(\ell_p\) with distortion at most \((c_2/p)\log n\) where \(c_2\) is a constant, and \(1\leq p<\log n\).