TY - GEN

T1 - Markov convexity and local rigidity of distorted metrics

AU - Mendel, Manor

AU - Naor, Assaf

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Bd-ramsey

KW - Markov convexity

KW - Metric dichotomy

KW - P-convexity

KW - Tree metrics

KW - Uniform convexity

UR - http://www.scopus.com/inward/record.url?scp=57349111077&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=57349111077&partnerID=8YFLogxK

U2 - 10.1145/1377676.1377686

DO - 10.1145/1377676.1377686

M3 - Conference contribution

AN - SCOPUS:57349111077

SN - 9781605580715

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 49

EP - 58

BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08

T2 - 24th Annual Symposium on Computational Geometry, SCG'08

Y2 - 9 June 2008 through 11 June 2008

ER -