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.
Yair Bartal 1 ; Nathan Linial 1 ; Manor Mendel 2 ; Assaf Naor 3
@article{10_4007_annals_2005_162_643,
author = {Yair Bartal and Nathan Linial and Manor Mendel and Assaf Naor},
title = {On metric {Ramsey-type} phenomena},
journal = {Annals of mathematics},
pages = {643--709},
year = {2005},
volume = {162},
number = {2},
doi = {10.4007/annals.2005.162.643},
mrnumber = {2183280},
zbl = {1114.46007},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.643/}
}
TY - JOUR AU - Yair Bartal AU - Nathan Linial AU - Manor Mendel AU - Assaf Naor TI - On metric Ramsey-type phenomena JO - Annals of mathematics PY - 2005 SP - 643 EP - 709 VL - 162 IS - 2 UR - http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.643/ DO - 10.4007/annals.2005.162.643 LA - en ID - 10_4007_annals_2005_162_643 ER -
%0 Journal Article %A Yair Bartal %A Nathan Linial %A Manor Mendel %A Assaf Naor %T On metric Ramsey-type phenomena %J Annals of mathematics %D 2005 %P 643-709 %V 162 %N 2 %U http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.643/ %R 10.4007/annals.2005.162.643 %G en %F 10_4007_annals_2005_162_643
Yair Bartal; Nathan Linial; Manor Mendel; Assaf Naor. On metric Ramsey-type phenomena. Annals of mathematics, Tome 162 (2005) no. 2, pp. 643-709. doi: 10.4007/annals.2005.162.643
Cité par Sources :