Euclidean quotients of finite metric spaces

Manor Mendel; Assaf Naor

doi:10.1016/j.aim.2003.12.001

Euclidean quotients of finite metric spaces

Manor Mendel, Assaf Naor

Research output: Contribution to journal › Article › peer-review

49 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	451-494
Number of pages	44
Journal	Advances in Mathematics
Volume	189
Issue number	2
DOIs	https://doi.org/10.1016/j.aim.2003.12.001
State	Published - Dec 20 2004
Externally published	Yes

All Science Journal Classification (ASJC) codes

Mathematics(all)

Access to Document

10.1016/j.aim.2003.12.001

Cite this

@article{a6999aabaf5a4eb7a7e025c72c61ad49,

title = "Euclidean quotients of finite metric spaces",

abstract = "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.",

author = "Manor Mendel and Assaf Naor",

note = "Funding Information: ·Corresponding author. Fax: +1-425-936-7329. E-mail addresses: mendelma@cs.huji.ac.il (M. Mendel), anaor@microsoft.com (A. Naor). 1Supported in part by a grant from the Israeli Science Foundation (195/02), and by the Landau Center.",

year = "2004",

month = dec,

day = "20",

doi = "10.1016/j.aim.2003.12.001",

language = "English (US)",

volume = "189",

pages = "451--494",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Academic Press Inc.",

number = "2",

}

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: mendelma@cs.huji.ac.il (M. Mendel), anaor@microsoft.com (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 -

Euclidean quotients of finite metric spaces

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this