On some low distortion metric Ramsey problems
| dc.creator | Bartal, Yair | |
| dc.creator | Mendel, Nathan Linial. Manor | |
| dc.creator | Naor, Assaf | |
| dc.date | 2004-06-17 | |
| dc.date.accessioned | 2026-07-07T05:09:21Z | |
| dc.date.available | 2026-07-07T05:09:21Z | |
| dc.description | In this note, we consider the metric Ramsey problem for the normed spaces l_p. Namely, given some 1<=p<=infinity and alpha>=1, and an integer n, we ask for the largest m such that every n-point metric space contains an m-point subspace which embeds into l_p with distortion at most alpha. In [arXiv:math.MG/0406353] it is shown that in the case of l_2, the dependence of $m$ on alpha undergoes a phase transition at alpha=2. Here we consider this problem for other l_p, and specifically the occurrence of a phase transition for p other than 2. It is shown that a phase transition does occur at alpha=2 for every p in the interval [1,2]. For p>2 we are unable to determine the answer, but estimates are provided for the possible location of such a phase transition. We also study the analogous problem for isometric embedding and show that for every 1<p<infinity there are arbitrarily large metric spaces, no four points of which embed isometrically in l_p. | |
| dc.description | 14 pages, to be published in Discrete and Computational Geometry | |
| dc.identifier | https://arxiv.org/abs/math/0406358 | |
| dc.identifier | http://arxiv.org/abs/math/0406358 | |
| dc.identifier | Discrete Comput. Geom. 33(1): 25-41, 2005 | |
| dc.identifier | doi:10.1007/s00454-004-1100-z | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/71596 | |
| dc.subject | Metric Geometry | |
| dc.subject | 52C45; 05C55; 54E40; 05C12; 54E40 | |
| dc.title | On some low distortion metric Ramsey problems | |
| dc.type | text |