Limitations to Frechet's Metric Embedding Method
| dc.creator | Batal, Yair | |
| dc.creator | Linial, Nathan | |
| dc.creator | Mendel, Manor | |
| dc.creator | Naor, Assaf | |
| dc.date | 2004-06-21 | |
| dc.date.accessioned | 2026-07-07T12:54:54Z | |
| dc.date.available | 2026-07-07T12:54:54Z | |
| dc.description | 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 Ω((\log n)^{1/p}). | |
| dc.description | 10 pages, 1 figure | |
| dc.identifier | https://arxiv.org/abs/math/0406404 | |
| dc.identifier | http://arxiv.org/abs/math/0406404 | |
| dc.identifier | Israel J. Math. 151: 111-124, 2006 | |
| dc.identifier | doi:10.1007/BF02777357 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/224095 | |
| dc.subject | Metric Geometry | |
| dc.title | Limitations to Frechet's Metric Embedding Method | |
| dc.type | text |