# Markov convexity and local rigidity of distorted metrics

Manor Mendel, Assaf Naor

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

The geometry of discrete tree metrics is studied from the following perspectives: (1) Markov p-convexity, which was shown by Lee, Naor, and Peres to be a property of p-convex Banach space, is shown here to be equivalent to p-convexity of Banach spaces. (2) On the other hand, there exists an example of a metric space which is not Markov p-convex for any p < ∞, but does not uniformly contain complete binary trees. Note that the previous item implies that Banach spaces contain complete binary trees uniformly if and only if they are not Markov p-convex for any p < ∞. (3) For every B > 4, a metric space X is constructed such that all tree metrics can be embedded in X with distortion at most B, but when large complete binary trees are embedded in X, the distortion tends to B. Therefore the class of finite tree metrics do exhibit a dichotomy in the distortions achievable when embedding them in other metric spaces. This is in contrast to the dichotomy exhibited by the class of finite subsets of L1, and the class of all finite metric spaces.

اللغة الأصلية الإنجليزيّة Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 49-58 10 https://doi.org/10.1145/1377676.1377686 نُشِر - 2008 24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, الولايات المتّحدةالمدة: ٩ يونيو ٢٠٠٨ → ١١ يونيو ٢٠٠٨

### سلسلة المنشورات

الاسم Proceedings of the Annual Symposium on Computational Geometry

### !!Conference

!!Conference 24th Annual Symposium on Computational Geometry, SCG'08 الولايات المتّحدة College Park, MD ٩/٠٦/٠٨ → ١١/٠٦/٠٨

## بصمة

أدرس بدقة موضوعات البحث “Markov convexity and local rigidity of distorted metrics'. فهما يشكلان معًا بصمة فريدة.