DISTORTION OF EMBEDDINGS OF BINARY TREES INTO DIAMOND GRAPHS

Abstract

Diamond graphs and binary trees are important examples in the theory of metric embeddings and also in the theory of metric characterizations of Banach spaces. Some results for these families of graphs are parallel to each other; for example superreflexivity of Banach spaces can be characterized both in terms of binary trees (Bourgain, 1986) and diamond graphs (Johnson-Schechtman, 2009). In this connection, it is natural to ask whether one of these families admits uniformly bilipschitz embeddings into the other. This question was answered in the negative by Ostrovskii (2014), who left it open to determine the order of growth of the distortions. The main purpose of this paper is to get a sharp up-to-a-logarithmic-factor estimate for the distortions of embeddings of binary trees into diamond graphs and, more generally, into diamond graphs of any finite branching k >= 2. Estimates for distortions of embeddings of diamonds into infinitely branching diamonds are also obtained.