Euclidean quotients of finite metric spaces

Abstract

This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embedings into l_p, and the particular case of the hypercube.

arXiv comment36 pages, 0 figures. To appear in Advances in Mathematics

References in corpus (4)

• On metric Ramsey-type phenomena
• Ramsey-type theorems for metric spaces with applications to online problems
• On some low distortion metric Ramsey problems
• Limitations to Frechet's Metric Embedding Method

Cited by in corpus (15)

• Metric Cotype
• Nonlinear spectral calculus and super-expanders
• Ramsey partitions and proximity data structures
• $L_p$ compression, traveling salesmen, and stable walks
• Expanders with respect to Hadamard spaces and random graphs
• Coarse embeddability into Banach spaces
• Coarse and uniform embeddings
• Ultrametric skeletons
• Maximum gradient embeddings and monotone clustering
• Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces $L_p$ and ${\ell }_p$ for $0<p<\infty$
• $(\beta )$-distortion of some infinite graphs
• An average John theorem
• Quantitative nonlinear embeddings into Lebesgue sequence spaces
• A note on dichotomies for metric transforms
• There is no equivariant coarse embedding of $L_p$ into ${\ell }_p$