On metric ramsey-type dichotomies

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


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.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)289-303
عدد الصفحات15
دوريةJournal of the London Mathematical Society
مستوى الصوت71
رقم الإصدار2
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - أبريل 2005
منشور خارجيًانعم

ملاحظة ببليوغرافية

Funding Information:
The first and second authors’ research was supported in part by grants from the Israeli National Science Foundation. The third author’s research was supported in part by the Landau Center.


أدرس بدقة موضوعات البحث “On metric ramsey-type dichotomies'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا