Trees and Markov convexity
James R. Lee, Assaf Naor, Yuval Peres · Symposium on Discrete Algorithms · 2006
We give combinatorial, geometric, and probabilistic characterizations of the distortion of tree metrics into Lp spaces. This requires the development of new embedding techniques, as well as a method for proving distortion lower bounds which is based on the wandering of Markov chains in Banach spaces, and a new metric invariant we call Markov convexity. Trees are thus the first non-trivial class of metric spaces for which one can give a simple and complete characterization of their distortion into a Hilbert space, up to universal constants. Our results also yield an efficient algorithm for constructing such embeddings.