## Abstract

In this note we consider the metric Ramsey problem for the normed spaces ℓ_{p}. Namely, given some 1 ≤ p ≤ ∞ and α ≥ 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 ℓ_{p} with distortion at most α. In [1] it is shown that in the case of ℓ_{2}, the dependence of m on α undergoes a phase transition at α = 2. Here we consider this problem for other ℓ_{p}, and specifically the occurrence of a phase transition for p ≠ 2. It is shown that a phase transition does occur at α = 2 for every p ∈ [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 < ∞ there are arbitrarily large metric spaces, no four points of which embed isometrically in ℓ_{p}.

Original language | English (US) |
---|---|

Pages (from-to) | 27-41 |

Number of pages | 15 |

Journal | Discrete and Computational Geometry |

Volume | 33 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2005 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Computational Theory and Mathematics