Some Low Distortion Metric Ramsey Problems

In this note we consider the metric Ramsey problem for the normed spaces $\ell_p$. Namely, given some $1\le p \le \infty$ and $\alpha \ge 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 $\ell_p$ with distortion at most $ \alpha$. In [1] it is shown that in the case of $\ell_2$, the dependence of $m$ on $\alpha$ undergoes a phase transition at $\alpha =2$. Here we consider this problem for other $\ell_p$, and specifically the occurrence of a phase transition for $p\neq 2$. It is shown that a phase transition does occur at $\alpha=2$ for every $p\in [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 < \infty$ there are arbitrarily large metric spaces, no four points of which embed isometrically in $\ell_p$.

Authors and Affiliations

1. Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel

   Yair Bartal, Nathan Linial & Manor Mendel

2. Theory Group, Microsoft Research, One Microsoft Way 113/2131, Redmond, WA 98052-6399, USA

   Assaf Naor

Corresponding authors

Correspondence to Yair Bartal, Nathan Linial, Manor Mendel or Assaf Naor.

Reprints and permissions