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

Current address:

Princeton University, Princeton, NJ 08544