On metric ramsey-type dichotomies

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)289-303
Number of pages15
JournalJournal of the London Mathematical Society
Volume71
Issue number2
DOIs
StatePublished - Apr 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'On metric ramsey-type dichotomies'. Together they form a unique fingerprint.

  • Cite this