Limitations to fréchet's metric embedding method

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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).

שפה מקוריתאנגלית
עמודים (מ-עד)111-124
מספר עמודים14
כתב עתIsrael Journal of Mathematics
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2006
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Funding Information:
* Supported in part by a grant from tile Israeli National Science Foundation. ** Supported in part by a grant from the Israeli National Science Foundation. t Supported in part by the Landau Center. Received July 13, 2003

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Limitations to fréchet's metric embedding method'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי