On some low distortion metric Ramsey problems

Abstract

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.

14 pages, to be published in Discrete and Computational Geometry

References in corpus (2)

• On metric Ramsey-type phenomena
• Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$

Cited by in corpus (9)

• On metric Ramsey-type phenomena
• Ramsey-type theorems for metric spaces with applications to online problems
• Euclidean quotients of finite metric spaces
• Ultrametric subsets with large Hausdorff dimension
• An introduction to the Ribe program
• Embedding proper ultrametric spaces into ${\ell }_p$ and its application to nonlinear Dvoretzky's theorem
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Clan Embeddings into Trees, and Low Treewidth Graphs
• On metric spaces with the properties of de Groot and Nagata in dimension one