Markov convexity and local rigidity of distorted metrics

Manor Mendel, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages49-58
Number of pages10
DOIs
StatePublished - 2008
Externally publishedYes
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Keywords

  • Bd-ramsey
  • Markov convexity
  • Metric dichotomy
  • P-convexity
  • Tree metrics
  • Uniform convexity

Fingerprint Dive into the research topics of 'Markov convexity and local rigidity of distorted metrics'. Together they form a unique fingerprint.

  • Cite this

    Mendel, M., & Naor, A. (2008). Markov convexity and local rigidity of distorted metrics. In Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 (pp. 49-58). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1377676.1377686