Limitations to fréchet's metric embedding method

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

Fréchet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Fréchet embedding is Bourgain's embedding [4]. The authors have recently shown [2] that for every ε > 0, any n-point metric space contains a subset of size at least n1-ε which embeds into ℓ2 with distortion O(log(2/ε)/ε). The embedding used in [2] is non-Fréchet, and the purpose of this note is to show that this is not coincidental. Specifically, for every ε > 0, we construct arbitrarily large n-point metric spaces, such that the distortion of any Fréchet embedding into ℓp on subsets of size at least n 1/2+ε is Ω((log n)1/P).

Original languageEnglish (US)
Pages (from-to)111-124
Number of pages14
JournalIsrael Journal of Mathematics
Volume151
DOIs
StatePublished - May 15 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Limitations to fréchet's metric embedding method'. Together they form a unique fingerprint.

  • Cite this