On metric Ramsey-type phenomena

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

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


This paper deals with Ramsey-type theorems for metric spaces. Such a theorem states that every n point metric space contains a large subspace which can be embedded with some fixed distortion in a metric space from some special class. Our main theorem states that for any ε > 0, every n point metric space contains a subspace of size at least n1-εwhich is embeddable in an ultrumetric with O(log(1/e/e) dis-tortion. This in particular provides a bound for embedding in Euclidean spaces. The bound on the distortion is tight up to the log(1/ε) factor even for embedding in arbitrary Euclidean spaces. This result can be viewed as a non-linear analog of Dvoretzky's theorem, a cornerstone of modern Banach space theory and convex geometry. Our main Ramsey-type theorem and techniques naturally extend to give theorems for classes of hierarchically well-separated trees which have algorithmic implications, and can be viewed as the solution of a natural clustering problem. We further include a comprehensive study of various other aspects of the metric Ramsey problem.

שפה מקוריתאנגלית
עמודים (מ-עד)463-472
מספר עמודים10
כתב עתConference Proceedings of the Annual ACM Symposium on Theory of Computing
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2003
פורסם באופן חיצוניכן
אירוע35th Annual ACM Symposium on Theory of Computing - San Diego, CA, ארצות הברית
משך הזמן: 9 יוני 200311 יוני 2003

טביעת אצבע

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

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