Every finite metric space has a large subset embeddable into R^d with small distortion

Analysis 1 Minute

You need to know: Euclidean space {\mathbb R}^d, metric space (X,\rho) with metric \rho.

Background: We say that a subset S of metric space (X,\rho) can be embedded into metric space (Y,\rho') with distortion at most \alpha if there exists a function f:S\to Y such that m \rho(A,B) \leq \rho'(f(A),f(B)) \leq M \rho(A,B), \, \forall A,B \in S, where m,M>0 are constants such that \frac{M}{m}\leq \alpha.

The Theorem: On 4th December 2002, Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor submitted to the Annals of Mathematics a paper in which they proved the existence of constant C>0 such that for every \alpha>1, every n-point metric space has a subset of size n^{1-C\frac{\log(2\alpha)}{\alpha}} which can be embedded into {\mathbb R}^d with distortion at most \alpha.

Short context: In 1985, Bourgain proved that every n-point metric space X can be embedded into {\mathbb R}^d with distortion at most C\log n (where the dimension d depends on n but the constant C does not). The bound C\log n is essentially sharp. The Theorem states, however, that reasonably large subsets of X can be embedded into {\mathbb R}^d with much smaller distortion. In a subsequent work Mendel and Naor showed that the Theorem holds for even larger subset of size n^{1-\frac{C}{\alpha}}, and that this is optimal up to the value of the constant C.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 5.8 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment