Premium
On Metric Ramsey‐Type Dichotomies
Author(s) -
Bartal Yair,
Linial Nathan,
Mendel Manor,
Naor Assaf
Publication year - 2005
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610704006155
Subject(s) - equilateral triangle , metric space , mathematics , metric (unit) , combinatorics , context (archaeology) , subspace topology , graph , discrete mathematics , mathematical analysis , geometry , paleontology , operations management , economics , biology
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.