On metric ramsey-type dichotomies

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

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


The classical Ramsey theorem states that every graph contains either a large clique or a large independent set. Here similar dichotomic phenomena are investigated in the context of finite metric spaces. Namely, statements are provided of the form 'every finite metric space contains a large subspace that is nearly equilateral or far from being equilateral'. Two distinct interpretations are considered for being 'far from equilateral'. Proximity among metric spaces is quantified through the metric distortion α. Tight asymptotic answers are provided for these problems. In particular, it is shown that a phase transition occurs at α = 2.

שפה מקוריתאנגלית
עמודים (מ-עד)289-303
מספר עמודים15
כתב עתJournal of the London Mathematical Society
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - אפר׳ 2005
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Funding Information:
The first and second authors’ research was supported in part by grants from the Israeli National Science Foundation. The third author’s research was supported in part by the Landau Center.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On metric ramsey-type dichotomies'. יחד הם יוצרים טביעת אצבע ייחודית.

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