Euclidean embedding, randomized clustering, and Lipschitz extension for finite and doubling subsets of $L_p$ when $p>2$

Read article Fix $p>2$. We prove that the Euclidean distortion of every $n$-point subset of $L_p$ is $p^3(\log n)^{\frac12 +o(1)}$, thus, in particular, demonstrating that all $n$-point subsets of $L_p$ exhibit an asymptotic improvement over the $O(\log n)$ Euclidean distortion guarantee that Bourgain’s embedding theorem provides for arbitrary $n$-point metric spaces. We also prove that the separation modulus of every $n$-point subset of $L_p$ is $O(p^2 \sqrt{\log n})$, which is sharp up to the dependence on $p$. We deduce from (a refinement of) this asymptotic evaluation of the finitary separation modulus of $L_p$ that for any $n$-point subset $\mathcal{C}$ of $L_p$ , any Banach space $\mathbf{Z}$, and any $1$-Lipschitz function $f:$\mathcal{C}\to\mathbf{Z}$, there exists a $O(p^2\log n)$-Lipschitz function $F:L_p\to\mathbf{Z}$ that extends $f$. We obtain analogous separation and extension statements for doubling subsets of $L_p$. DOI: https://doi.org/10.15781/d72xfr59