2004/06/18 by YAIR BARTAL, Yair Bartal, Nathan Linial +5
Mathematics · #Advanced Topology and Set Theory #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #math.CO #msc:05C12 #msc:05C55 #msc:52C45 #msc:54E40
paper · pdf · doi:10.1112/s0024610704006155
published as J. London Math. Society 71(2): 289-303, 2005 · 14 pages, 0 figures
arxiv created 2004/06/18 · openalex publication_date 2005/04/01 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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.