Limitations to Frechet's Metric Embedding Method

Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding. The authors have recently shown that for every e>0 any n-point metric space contains a subset of size a...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2004-06
Main Authors: Batal, Yair, Linial, Nathan, Manor Mendel, Naor, Assaf
Format: Article
Language:English
Subjects:
Distortion
Embedding
Metric space
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Frechet's classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Frechet embedding is Bourgain's embedding. The authors have recently shown that for every e>0 any n-point metric space contains a subset of size at least n^(1-e) which embeds into l_2 with distortion O(\log(2/e) /e). The embedding we used is non-Frechet, and the purpose of this note is to show that this is not coincidental. Specifically, for every e>0, we construct arbitrarily large n-point metric spaces, such that the distortion of any Frechet embedding into l_p on subsets of size at least n^{1/2 + e} is \Omega((\log n)^{1/p}).
ISSN:2331-8422
DOI:10.48550/arxiv.0406404