View Related Documents

Abstract

In this note we consider the metric Ramsey problem for the normed spaces lp\ell_p. Namely, given some 1 £ p £ ¥1\le p \le \infty and a ³ 1\alpha \ge 1, and an integer nn, we ask for the largest mm such that every nn-point metric space contains an mm-point subspace which embeds into lp\ell_p with distortion at most a \alpha. In [1] it is shown that in the case of l2\ell_2, the dependence of mm on a\alpha undergoes a phase transition at a = 2\alpha =2. Here we consider this problem for other lp\ell_p, and specifically the occurrence of a phase transition for p ¹ 2p\neq 2. It is shown that a phase transition does occur at a = 2\alpha=2 for every p Î [1,2]p\in [1,2]. For $p > 2$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$1 < p < \infty there are arbitrarily large metric spaces, no four points of which embed isometrically in lp\ell_p.

Fulltext Preview

Image of the first page of the fulltext document