On metric Ramsey-type phenomena
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor · Annals of Mathematics · 2005
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 > 0, every n point metric space contains a subset of size at least n 1-which is embeddable in Hilbert space with O log(1/ ) distortion.The bound on the distortion is tight up to the log(1/ ) factor.We further include a comprehensive study of various other aspects of this problem.