On metric Ramsey-type phenomena

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Number of pages10
StatePublished - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003


Other35th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA


  • Dvoretzky theorem
  • Finite metric spaces
  • Ramsey theory

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'On metric Ramsey-type phenomena'. Together they form a unique fingerprint.

Cite this