This post continues my series on favorite theorems of the twenty-first century. For an overview of the categories and earlier selections, see this post.
My choice for 2002 in Analysis is a theorem of Bartal, Linial, Mendel and Naor on large Euclidean subsets of finite metric spaces. In a striking “metric Ramsey” result, they proved that every -point metric space contains a subset of size which embeds into Euclidean space with distortion at most . The theorem was proved in 2002 and published in 2005 (Bartal et al. 2005).
Recall from this previous blog post that a metric space is said to admit a bi-Lipschitz embedding into a metric space if there are constants and a map such that When holds with , we say that embeds into with distortion at most . Thus a low-distortion embedding is one which changes all distances only by a controlled multiplicative factor.
The study of low-distortion embeddings has been a central part of the Ribe program and of the geometry of finite metric spaces, but it also has a more algorithmic face: many problems in theoretical computer science become easier once an arbitrary finite metric space is represented inside a better understood one, such as Euclidean space or . A celebrated theorem of Bourgain (Bourgain 1985) says that every -point metric space embeds into Euclidean space with distortion at most , where the dimension may depend on but is a universal constant. This logarithmic bound is essentially sharp in general, so one cannot hope to embed every finite metric space into Hilbert space with bounded distortion.
The theorem of Bartal, Linial, Mendel and Naor changes the question in a beautiful way. Instead of asking whether the whole metric space embeds well, one asks whether a large subset embeds well. This is a metric analogue of Ramsey-type phenomena: an arbitrary large structure may be complicated globally, but it must contain a large substructure with a much more regular geometry. Their result shows that, although an -point metric space can be very far from Euclidean as a whole, it always contains a nearly full-size subset whose metric geometry is Euclidean up to any prescribed distortion , with the loss in the exponent tending to zero as .
Here is equipped with its usual Euclidean metric, and the dimension is allowed to depend on the metric space and on . The point is not the dimension, but rather the simultaneous control of two competing quantities: the subset is large, and the distortion is bounded independently of . For fixed , the theorem guarantees a subset of polynomial size in ; as grows, the exponent approaches , so the subset becomes closer and closer to having full cardinality.
This result is especially elegant because it sits between two extremes. On the one hand, Bourgain’s theorem guarantees an embedding of the entire space, but with distortion of order . On the other hand, if one is allowed to pass to very small subsets, then good embeddings are much easier to find. The theorem of Bartal, Linial, Mendel and Naor says that one can keep a very large subset while reducing the distortion all the way down to a fixed constant. In this sense, it identifies a powerful hidden Euclidean structure inside every finite metric space.
In 2007, Mendel and Naor (Mendel and Naor 2007) sharpened this phenomenon by showing that one can find an even larger subset of size with the same conclusion as in Theorem . They also proved that this dependence on is optimal up to the value of the universal constant . Thus the original theorem of Bartal, Linial, Mendel and Naor was not only a major advance in metric Ramsey theory, but also the first and crutial step toward the essentially sharp form of the finite metric Ramsey theorem for Euclidean embeddings.