Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Some Low Distortion Metric Ramsey Problems
| |
|
Some Low Distortion Metric Ramsey Problems Yair Bartal1 , Nathan Linial1 , Manor Mendel1 and Assaf Naor2  | (1) | Institute of Computer Science, Hebrew
University, Jerusalem 91904, Israel |
| (2) | Theory Group, Microsoft Research, One
Microsoft Way 113/2131, Redmond, WA 98052-6399, USA |
Received: 17 December 2002 Revised: 21 December 2003 Published online: 2 July 2004 Abstract
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$.
Fulltext Preview (Small, Large)
|
|
|
|
|
|