Markov convexity and local rigidity of distorted metrics

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 L₁, and the class of all finite metric spaces.