TY - JOUR
T1 - Euclidean quotients of finite metric spaces
AU - Mendel, Manor
AU - Naor, Assaf
N1 - Funding Information:
·Corresponding author. Fax: +1-425-936-7329. E-mail addresses: [email protected] (M. Mendel), [email protected] (A. Naor). 1Supported in part by a grant from the Israeli Science Foundation (195/02), and by the Landau Center.
PY - 2004/12/20
Y1 - 2004/12/20
N2 - This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and α≥1, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embeddings into ℓp, and the particular case of the hypercube.
AB - This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and α≥1, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embeddings into ℓp, and the particular case of the hypercube.
UR - http://www.scopus.com/inward/record.url?scp=4344706090&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=4344706090&partnerID=8YFLogxK
U2 - 10.1016/j.aim.2003.12.001
DO - 10.1016/j.aim.2003.12.001
M3 - Article
AN - SCOPUS:4344706090
SN - 0001-8708
VL - 189
SP - 451
EP - 494
JO - Advances in Mathematics
JF - Advances in Mathematics
IS - 2
ER -