On metric Ramsey-type phenomena

Abstract

The main question studied in this article may be viewed as a nonlinear analogue of Dvoretzky’s theorem in Banach space theory or as part of Ramsey theory in combinatorics. Given a finite metric space on $n$ points, we seek its subspace of largest cardinality which can be embedded with a given distortion in Hilbert space. We provide nearly tight upper and lower bounds on the cardinality of this subspace in terms of $n$ and the desired distortion. Our main theorem states that for any $\epsilon>0$, every $n$ point metric space contains a subset of size at least $n^{1-\epsilon}$ which is embeddable in Hilbert space with $O\left(\frac{\log(1/\epsilon)}{\epsilon}\right)$ distortion. The bound on the distortion is tight up to the $\log(1/\epsilon)$ factor. We further include a comprehensive study of various other aspects of this problem.

Authors

Yair Bartal

Institute of Computer Science
Hebrew University
91904 Jerusalem
Israel

Nathan Linial

Institute of Computer Science
Hebrew University
91904 Jerusalem
Israel

Manor Mendel

Computer Science Division
The Open University of Israel
43107 Ra'anana
Israel

Assaf Naor

Theory Group
Microsoft Research
Redmond, WA 98052
United States