Mathematics – Metric Geometry
Scientific paper
2004-06-17
Ann. of Math. (2) 162 (2005), no. 2, 643--709
Mathematics
Metric Geometry
67 pages, published version
Scientific paper
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(\frac{\log(1/\epsilon)}{\epsilon}) 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.
Bartal Yair
Linial Nathan
Mendel Manor
Naor Assaf
No associations
LandOfFree
On metric Ramsey-type phenomena does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On metric Ramsey-type phenomena, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On metric Ramsey-type phenomena will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-203719