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.
My Menu
Saved Items

Some Low Distortion Metric Ramsey Problems

Yair BartalContact Information, Nathan LinialContact Information, Manor MendelContact Information and Assaf NaorContact Information

(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$.

Contact InformationYair Bartal
Email: yair@cs.huji.ac.il

Contact InformationNathan Linial
Email: nati@cs.huji.ac.il

Contact InformationManor Mendel
Email: mendelma@cs.huji.ac.il

Contact InformationAssaf Naor
Email: anaor@microsoft.com
Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)