### 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 L_{1}, and the class of all finite metric spaces.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 |

Pages | 49-58 |

Number of pages | 10 |

DOIs | |

State | Published - 2008 |

Externally published | Yes |

Event | 24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States Duration: Jun 9 2008 → Jun 11 2008 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

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

Country | United States |

City | College Park, MD |

Period | 6/9/08 → 6/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

*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