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

Read article Fix p>2. We prove that the Euclidean distortion of every n-point subset of Lₚ is p³ (n) ^12 +o (1), thus, in particular, demonstrating that all n-point subsets of Lₚ exhibit an asymptotic improvement over the O (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ₚ is O (p² 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ₚ that for any n-point subset C of Lₚ, any Banach space Z, and any 1-Lipschitz function f: C, there exists a O (p² n) -Lipschitz function F: Lₚ that extends f. We obtain analogous separation and extension statements for doubling subsets of Lₚ. DOI: https: //doi. org/10. 15781/d72xfr59