Geodesic
On metric Ramsey-type phenomena
Yair Bartal1 ; Nathan Linial1 ; Manor Mendel2 ; Assaf Naor3
1 Institute of Computer Science, Hebrew University, 91904 Jerusalem, Israel
2 Computer Science Division, The Open University of Israel, 43107 Ra'anana, Israel
3 Theory Group, Microsoft Research, Redmond, WA 98052, United States
Annals of mathematics, Tome 162 (2005) no. 2, pp. 643-709.

Voir la notice de l'article provenant de la source Annals of Mathematics website

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.
DOI : 10.4007/annals.2005.162.643

Yair Bartal 1 ; Nathan Linial 1 ; Manor Mendel 2 ; Assaf Naor 3

1 Institute of Computer Science, Hebrew University, 91904 Jerusalem, Israel
2 Computer Science Division, The Open University of Israel, 43107 Ra'anana, Israel
3 Theory Group, Microsoft Research, Redmond, WA 98052, United States 
@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},
     publisher = {mathdoc},
     volume = {162},
     number = {2},
     year = {2005},
     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
PB  - mathdoc
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
%I mathdoc
%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. http://geodesic.mathdoc.fr/articles/10.4007/annals.2005.162.643/

Cité par Sources :