Some low distortion metric ramsey problems

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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.

שפה מקוריתאנגלית
עמודים (מ-עד)27-41
מספר עמודים15
כתב עתDiscrete and Computational Geometry
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2005
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Some low distortion metric ramsey problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי