2004/06/17 by Yair Bartal, Nathan Linial, Nathan Linial. Manor Mendel +2 · 3 citations
Computer Science · Mathematics · #Advanced Banach Space Theory #Advanced Topology and Set Theory #Computational Geometry and Mesh Generation #math.MG #msc:05C12 #msc:05C55 #msc:52C45 #msc:54E40
paper · pdf · doi:10.1007/s00454-004-1100-z
published as Discrete Comput. Geom. 33(1): 25-41, 2005 · 14 pages, to be published in Discrete and Computational Geometry
arxiv created 2004/06/17 · openalex publication_date 2004/07/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this note, we consider the metric Ramsey problem for the normed spaces lp. 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 lp with distortion at most alpha. In [arXiv:math.MG/0406353] it is shown that in the case of l2, the dependence of m on alpha undergoes a phase transition at alpha=2. Here we consider this problem for other lp, 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 lp.