Trees and Markov convexity

James R. Lee^{∗}  Assaf Naor ^{†}  Yuval Peres^{‡}

Abstract

We show that an infinite weighted tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not contain arbitrarily large complete binary trees with uniformly bounded distortion. We also introduce a new metric invariant called Markov convexity, and show how it can be used to compute the Euclidean distortion of any metric tree up to universal factors.

1 Introduction

Given two metric spaces (X, d_{X}), (Y, d_{Y}), and a mapping f : X → Y, we denote the Lipschitz constant of f by ∥f∥_{Lip}. If f is injective then the (bi-Lipschitz) distortion of f is defined as dist(f) = ∥f∥_{Lip} ·∥f^{−1}∥_{Lip}. The smallest distortion with which X embeds into Y is denoted c_{Y} (X), i.e. c_{Y} (X) = inf{dist(f) : f : X ↪ Y }. When Y = L_{p} for some p ≥ 1 we use the shorter notation c_{p}(X) = c_{L_{p}}(X). The parameter c_{2}(X) is known in the literature as the Euclidean distortion of X.

The ubiquitous problem of embedding metric spaces into “simpler” spaces occurs in various aspects of functional analysis, Riemannian geometry, group theory, and computer science. In most cases low distortion embeddings are used to “simplify” a geometric object by representing it as a subset of a better understood geometry. In other cases, embeddings are used to characterize important invariants such as various notions of dimensionality in metric spaces, and superreflexivity, type and cotype of normed spaces. More recently, striking applications of bi-Lipschitz embeddings were found in computer science, where the information obtained from concrete geometric representations of finite spaces is used to design efficient approximation algorithms and data structures.

The present paper is devoted to the study of the Euclidean (and L_{p}) distortion of trees. In what follows by a metric tree we mean the shortest path metric induced on the vertices of a weighted graph-theoretical tree T = (V, E). In fact, all of our results will hold true for arbitrary subsets of metric trees, which are characterized among all metric spaces by the well known four point condition: For every four points x, y, u, v two of the three numbers {d(x, y) + d(u, v), d(x, u) + d(y, v), d(x, v) + d(y, u)} are the same, and that number is at least as large as the third (see [10]). But, because our statements are asymptotic in nature, this does not increase the generality of our results, since Gupta [16] proved that any finite subset of a metric tree is bi-Lipschitz equivalent to a metric tree with distortion at most 8. The ℝ-tree corresponding to a tree T is the one-dimensional simplicial complex induced by T, i.e. the path metric obtained by replacing each edge in T by an interval whose length is the weight of the edge. The ℝ-tree corresponding to T will be denoted T_{ℝ}. In what follows, when we refer to an ℝ-tree we mean an ℝ-tree corresponding to some metric tree. We will see later that for every metric tree T and every p ≥ 1, c_{p}(T) has the same order of magnitude as c_{p}(T_{ℝ}), so in most cases the distinction between metric trees and ℝ-trees will not be important, though in a few instances we will need to distinguish the two notions.

∗Computer Science and Engineering, University of Washington. This research was conducted while the author was at U. C. Berkeley and the Institute for Advanced Study. jrl@cs.washington.edu

†Microsoft Research. anaor@microsoft.com

‡Microsoft Research and U. C. Berkeley. peres@stat.berkeley.edu

Let B_{k} denote the complete binary tree of depth k (with unit edge weights). In a famous paper [6] Bourgain proved that the Euclidean distortion of B_{k} is Θ (\sqrt{log k}). Moreover, he showed that a Banach space Y is superreflexive (i.e. admits an equivalent uniformly convex norm) if and only if lim_{k→∞} c_{Y} (B_{k}) = ∞. This remarkable characterization of a linear property of Banach spaces in terms of their metric structure sparked a considerable amount of work on problems of a similar flavor (see the introduction of [30] for more information on this topic). Among the corollaries of Bourgain’s work is the following dichotomy: For a Banach space Y either c_{Y} (B_{k}) = 1 for all k, or there exists α > 0 such that c_{Y} (B_{k}) = Ω ((log k)^{α}) (similar phenomena are known to hold in a few other cases—see [7, 30]). Moreover, Bourgain used his theorem to solve a question posed by Gromov, showing that the hyperbolic plane does not admit a bi-Lipschitz embedding into Hilbert space. Similar applications of Bourgain’s theorem to prove that certain metric spaces do not embed into Hilbert space were obtained by Benjamini and Schramm [5] in the case of graphs with positive Cheeger constant, and by Leuzinger [21] in the case of certain Tits buildings.

The bi-Lipschitz structure of trees has been studied extensively. Trees are the “building blocks” of hyperbolic geometry, and embeddings of certain non-positively curved spaces into products of trees are used in several contexts (see for example [9, 8, 31, 20]). Similar results (known as “probabilistic embeddings into trees”) are a powerful tool in computer science (see for example [4, 12]). We refer to [10, 27, 18] for other results on the Lipschitz structure of trees. In spite of these applications, and the vast amount of work on trees in the Lipschitz category, the following natural problem remained open: When does an infinite metric tree embed with finite distortion into Hilbert space? One of the main results of this paper is the following answer to this question.

Theorem 1.1. Let T = (V, E) be an infinite metric tree. Then the following conditions are equivalent.

1. c_{2}(T) = ∞.

2. sup_{k∈ℕ} c_{T} (B_{k}) < ∞.

3. For every k ∈ ℕ, c_{T} (B_{k}) = 1.

In other words, a metric tree admits a bi-Lipschitz embedding into Hilbert space if and only if it does not bi-Lipschitzly contain arbitrarily large complete binary trees. Thus there is a unique obstruction to a tree being non-Euclidean. Similar “unique obstruction” results are known only in very few cases: As we mentioned above, Bourgain [6] proved that complete binary trees are the unique obstruction to a Banach space being superreflexive; Bourgain, Milman and Wolfson [7] showed that Hamming cubes are the unique obstruction to a metric space having non-trivial type; Mendel and Naor [30] showed that ℓ_{∞}^{n} integer grids are the unique obstruction to a metric space having finite cotype; Thomassen [35] proved that certain transient graphs must contain transient trees, and Benjamini and Schramm [5] proved that a graph with positive Cheeger constant must contain a tree with positive Cheeger constant. Another result in the spirit of Theorem 1.1 is the tree Szemeredi theorem of Furstenberg and Weiss [14]: A subset of positive density in the infinite complete binary tree must contain arbitrarily large copies of complete binary trees.

It is not surprising that the Theorem 1.1 is a “local” result, in the sense that it deals with finite subsets of the metric tree T. Indeed, it is well known that a metric space embeds into Hilbert space if and only if all of its finite subsets do. It is thus natural to expect characterizations in the spirit of Theorem 1.1 to be local. Let us say that a metric space X is finitely representable in a metric space Y if there exists a constant D ≥ 1 such that for every finite subset F ⊆ X we have c_{Y} (F) ≤ D (this is an obvious adaptation of standard terminology from Banach space theory). Thus, denoting by B_{∞} the infinite unweighted complete binary tree, Theorem 1.1 can be rephrased as follows: A metric tree T admits a bi-Lipschitz embedding into Hilbert space if and only if B_{∞} is not finitely representable in T. The following section contains optimal quantitative versions of this result, and explains the ingredients of its proof.

1.1 Markov convexity and quantitative bounds

Quantitative bounds on the Euclidean distortion of trees were obtained in [24, 28, 25, 17]. In particular, Matoušek proved in [28] that for any n-point metric tree T we have c_{2}(T) = O (\sqrt{log log n}). This result cannot be improved due to Bourgain’s lower bound for the complete binary tree. Gupta, Krauthgamer and Lee [17] obtained upper bounds on the Euclidean distortion of trees in terms of their doubling constant; in particular, they showed that every doubling tree admits a bi-Lipschitz embedding into a finite-dimensional Euclidean space. We present a new simpler proof of this fact in Section 2.3, where we also recall the definition of the doubling constant.

We shall now state an optimal quantitative version of Theorem 1.1. Given a metric space (X, d_{X}), k ∈ ℕ and c > 1, we denote

ℬ_{X}(c) = max {k ∈ ℕ : c_{X}(B_{k}) < c} .

In what follows we write A ∼^{<} B to mean A = O(B). If A ∼^{<} B and B ∼^{<} A then we write A ≈ B.

Theorem 1.2. Let T be an arbitrary metric tree. Then for every c > 1,

\frac{1}{c}\sqrt{log ℬ_{T} (c)} ∼^{<} c_{2}(T) ∼^{<} \sqrt{\frac{c}{c − 1} · ℬ_{T} (c)} .

The lower bound in Theorem 1.2 is simply Bourgain’s lower bound, and is therefore optimal. Somewhat surprisingly, the upper bound in Theorem 1.2 cannot be improved. The construction of a family of trees exhibiting this, which we call the Cantor trees, is presented in Section 3.3.3.

It follows that in order to obtain tight bounds on the Euclidean distortion of a given metric tree T we need an invariant which is more refined than the size of the biggest binary tree contained in T. This is achieved via the following definition. Let {X_{t}}_{t=0}^{∞} be a Markov chain on a state space Ω. Given an integer k ≥ 0 we denote by {X̃_{t}(k)}_{t=0}^{∞} the process which equals X_{t} for time t ≤ k, and evolves independently (with respect to the same transition probabilities) for time t > k. Observe that for k < 0, X̃_{t}(k) and X_{t} evolve independently for all t ≥ 0.

Definition 1.3. Let (X, d) be a metric space and p > 0. We shall say that (X, d) is Markov pconvex with constant Π if for every Markov chain {X_{t}}_{t=0}^{∞} on a state space Ω, and every f : Ω → X, we have for every m ∈ ℕ,

∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [d (f (X_{t}) , f(X̃_{t}(t − 2^{k})))^{p}]}{2^{kp}} ≤ Π^{p} ∑_{t=1}^{2^{m}} 𝔼[d(f(X_{t}), f(X_{t−1}))^{p}].  (1)

The least constant Π above is called the Markov p-convexity constant of X, and is denoted Π_{p}(X). We shall say that X is Markov p-convex if Π_{p}(X) < ∞.

To understand this notion, recall that the chains X_{t} and X̃_{t}(t − 2^{k}) run together for the first t − 2^{k} steps, and then evolve independently for the remaining 2^{k} steps. Thus the left hand side in (1) is measuring the sum, over many “dyadic scales” k ∈ {0, 1, 2, …} of the average of the pth power of the normalized “drift” of the chain in X with respect to scale k. We will say that X has non-trivial Markov convexity if X is Markov p-convex for some p < ∞. We note that L_{2} is Markov 2-convex. More generally, the name comes from the fact that if X is a Banach space which admits an equivalent uniformly convex norm whose modulus of convexity is of power type p, then X is also Markov p-convex. These results are proved in Section 3.1.

In Bourgain’s paper [6] there is an implicit “non-linear” notion of uniform convexity related to the presence of complete binary trees. For the results in this paper, we require the above “Markov variant,” analogous to Ball’s notion of Markov type [2]. The search for Poincaré-type inequalities on metric spaces which are analogs of classical Banach space invariants have been fruitfully investigated by several authors—we refer to the papers [11, 15, 7, 34, 2, 32, 31, 30] for a discussion of this research direction, to which Definition 1.3 belongs. The following theorem shows that Markov convexity determines the Euclidean distortion of a tree, up to universal factors.

Theorem 1.4. Let T be a metric tree. Then c_{2}(T) ≈ Π_{2}(T_{ℝ}).

Recall that T_{ℝ} denotes the ℝ-tree corresponding to T. See Remark 3.3 for a discussion of why we have to pass to ℝ-trees in Theorem 1.4.

We also obtain a combinatorial way to compute the Euclidean distortion of any tree. Let T = (V, E) be a metric tree, and let χ : E → ℤ be an edge coloring. We call χ a monotone coloring if all of its color classes are paths contained in a root-leaf path (such paths are called monotone paths in what follows). For δ ∈ (0, 1), the coloring χ is called δ-strong if it is monotone and for every u, v ∈ V at least half of the length of the path joining u and v can be covered by color classes of length at least δd_{T} (u, v). We define δ^{∗}(T) to be the largest δ for which T admits a δ-strong coloring. The following theorem shows that δ^{∗}(T) determines the Euclidean distortion of T.

Theorem 1.5. Let T be a metric tree. Then

c_{2}(T) ≈ \sqrt{1 + log (\frac{1}{δ^{∗}(T)})}.

The upper bound on c_{2}(T) in Theorem 1.5 continues a theme that also appeared in [24, 28, 17]: Certain edge colorings can be used to construct embeddings into L_{2}. Specifically, our proof draws on ideas from Matoušek’s embedding [28]. But, Matoušek’s argument requires colorings with a small number of colors, the existence of which depends only on the topology of T and does not take into account the edge lengths. Our argument for the upper bound, which is contained in Theorem 2.6, builds on Matoušek’s proof while taking the metric into consideration, and is therefore more involved.

The lower bound on c_{2}(T) in Theorem 1.5 goes through Theorem 1.4. We construct a special coloring of T, and show that if the coloring is not δ-strong, then we can construct a Markov chain on T which wanders too quickly for T to have a small Markov 2-convexity constant. This is done by locating a special type of subtree of T, which we call a weak prototype—see Section 3.3 for the definition, where it is shown that weak prototypes cannot have good Markov convexity properties. This “reconstruction paradigm” is inspired by a result of [17] which shows that if a certain procedure fails to produce a good coloring, then the tree under consideration must have a large doubling constant. Our approach is able to pick out significantly more delicate sub-structures (e.g. embedded complete binary trees or the aforementioned “weak prototypes”). A key difficulty that arises in our setting involves choosing the “scale” at which the required weak prototype embeds into T. This “scale selection” argument is a central part of our proof of Theorem 1.2, Theorem 1.4, and Theorem 1.5—we refer to Section 2.2 and Section 4 for the details.

We remark that all of our results can be applied to compute the L_{p} distortion of trees. Namely, we show that for every p, c > 1 and every metric tree T,

\frac{1}{c} (log ℬ_{T} (c)) ^{min\{ \frac{1}{p} , \frac{1}{2} \}} ∼^{<} c_{p}(T) ∼^{<} (\frac{c}{c − 1} · ℬ_{T} (c)) ^{min\{ \frac{1}{p} , \frac{1}{2} \}} .  (2)

and

c_{p}(T) ≈ Π_{max\{p,2\}}(T_{ℝ}) ≈ [log (\frac{2}{δ^{∗}(T)})]^{min\{ \frac{1}{p} , \frac{1}{2} \}} ,  (3)

where the implied constants may depend only on p; see Theorem 4.1.

The use of Markov convexity as a metric invariant, and thus a tool for proving distortion lower bounds, is not limited to the case of trees. In Section 3.2 we investigate classes of spaces which can be shown not to embed into L_{2} by analyzing their Markov convexity. In particular, we prove a lower bound on the Euclidean distortion of balls of finitely generated groups (equipped with the word metric) which admit a bounded non-constant harmonic function. We also bound from below the Euclidean distortion of the lamplighter group over the cycle (see Section 3.2 for the definition). In a future paper, which will be devoted to embeddings of the lamplighter group, we use the methods of [31] to show that this group has Markov type 2 in the sense of Ball [2]. Thus, Markov convexity is the only known invariant which demonstrates that this group does not well-embed into Hilbert space.

Our results, specifically Theorem 1.5, have algorithmic implications. Given an n-point metric space X, the problem of efficiently computing its distortion in a class of metric spaces up to a small factor has attracted a lot of attention in recent years, and is known as the “relative embedding” problem. We refer to [1] and the references therein for a discussion of this topic, and also for some hardness results. The Euclidean distortion of an n-point metric space can be computed in polynomial time, since this problem can be cast as a semidefinite program [23]. Hence Theorem 1.5 yields a polynomial time algorithm for estimating the parameter log (\frac{1}{δ^{∗}(T)}) up to a constant factor for any tree T. In conjunction with (3), this gives a polynomial time algorithm which computes the L_{p} distortion of any tree up to a universal constant factor. Note that it not known whether the L_{p} distortion of a general finite metric space can be approximated efficiently.

1.2 Some open problems

We end this introduction by stating some interesting open problems that arise from our work.

Problem 1. In Section 3.1 we show that every p-uniformly convex Banach space is Markov pconvex. We also show that if X is a Banach lattice which is Markov p-convex then it is also q-uniformly convex for every q > p. The relation between Markov p-convexity and uniform pconvexity for general Banach spaces is unclear.

Problem 2. One corollary of our results is that if a metric tree is not Markov p-convex for any p < ∞ then it contains arbitrarily large complete binary trees with distortion arbitrarily close to 1. It is possible that this holds true for arbitrary metric spaces, and not just metric trees. If this is the case, then it would correspond to known results in Banach space theory, and would complement the existing theory of metric type and cotype.

Problem 3. It would be interesting to investigate other “unique obstruction” results of the type described here. In particular, can one classify the obstructions to a planar graph being embeddable in L_{2}? Another interesting generalization would be to classify the subsets of ℍ^{2}—the hyperbolic plane—which embed into L_{2}; it seems plausible that complete binary trees are the only obstruction in this case, just as for tree metrics. In a similar vein, it might be the case that the only subsets of a product of trees which do not admit a bi-Lipschitz embedding into L_{2} are those that contain arbitrarily large bi-Lipschitz copies of complete binary trees. If true, then in combination with the result of [8], this would imply the same result for the hyperbolic plane.

Problem 4. In Section 3.2 we give lower bounds on the Euclidean distortion of the lamplighter group over the n-cycle. We do not know what is the correct asymptotic behavior of this distortion. It is also unknown whether or not these groups embed into L_{1} with uniformly bounded distortion.

Figure 1: A schematic description of the implications between the sections in this paper.

2 Distortion bounds via the containment of binary trees

The purpose of this section is to prove the following theorem which, when combined with Bourgain’s lower bound for binary trees [6], implies Theorem 1.1 and Theorem 1.2.

Theorem 2.1. Let T be an arbitrary metric tree and p ≥ 1. Then for every c > 1,

c_{p}(T) ≤ 130 (\frac{c}{c − 1} · ℬ_{T} (c)) ^{min\{ \frac{1}{p} , \frac{1}{2} \}} .

In Section 3.3.3 we will show that the asymptotic dependence on ℬ_{T} (c) in the upper bound of Theorem 2.1 cannot be improved.

2.1 Coloring based upper bounds

We begin with some definitions and notation. Let T = (V, E) be a finite graph-theoretic tree with positive edge lengths ℓ : E → (0, ∞), and let d_{T} be the induced path metric on V. We also fix some arbitrary root r ∈ T. A monotone path in T is a connected subset (also called a segment in what follows) of some root-leaf path. By an edge-coloring of T, we mean a map χ : E → ℤ. We say that the coloring is monotone if for every m ∈ ℤ the color class χ^{−1}(m) is a monotone path. For u, v ∈ V we let P (u, v) ⊆ E denote the unique path from u to v, and set P (v) = P (v, r). Given an edge coloring χ : E → ℤ, k ∈ χ(E), and u, v ∈ V, we write

ℓ_{k}^{χ}(u, v) := ∑_{\begin{matrix}e∈P (u,v) \\ χ(e)=k \end{matrix}} ℓ(e).

We also set ℓ_{k}^{χ}(v) = ℓ_{k}^{χ}(v, r). Finally, given u, v ∈ V we let lca(u, v) denote the least common ancestor of u and v in T.

Definition 2.2 (ε-good coloring). We say that a coloring χ : E → ℤ is ε-good if it is monotone, and for every u, v ∈ T, the unique path from u to v contains a monochromatic segment of length at least ε · d_{T} (u, v). We define ε^{∗}(T) to be the largest ε for which T admits an ε-good coloring.

The following simple lemma will not be used in the proof of Theorem 2.1, but we include it since it illustrates the relation between colorings and embeddings, and it will be used eventually in Section 2.3.

Lemma 2.3. For every weighted tree T and p ≥ 1,

c_{p}(T) ≤ \frac{2^{1/p}}{ε^{∗}(T)}.

Proof. Fix ε < ε^{∗}(T) and let χ : E → ℤ be an ε-good coloring. Let {e_{k}}_{k∈ℤ} be the standard basis of ℓ_{p} = ℓ_{p}(ℤ). Define f : V → ℓ_{p} by

f(v) = ∑_{k∈ℤ}ℓ_{k}^{χ}(v)e_{k}.

(Recall that ℓ_{k}(v) is the distance that the segment colored k contributes to the path joining v to the root).

Fix u, v ∈ V and write w = lca(u, v). The fact that the coloring χ is monotone implies that χ(P (u, w)) ∩ χ(P (v, w)) = ∅. Thus

d_{T} (u, v) = ∑_{e∈P (u,w)} ℓ(e) + ∑_{e∈P (v,w)} ℓ(e) = ∑_{k∈ℤ}|ℓ_{k}^{χ}(u) − ℓ_{k}^{χ}(v)| = ∥f(u) − f(v)∥_{1} ≥ ∥f(u) − f(v)∥_{p}.

On the other hand, since χ is ε-good, there are a, b ∈ ℤ such that ℓ_{a}^{χ}(u, w) ≥ εd_{T} (u, w) and ℓ_{b}^{χ}(v, w) ≥ εd_{T} (v, w). It follows that

∥f(u) − f(v)∥_{p} ≥ ([ℓ_{a}^{χ}(u, w)]^{p} + [ℓ_{b}^{χ}(v, w)]^{p})^{1/p} ≥ \frac{ε}{2^{1/p}} [d_{T} (u, w) + d_{T} (v, w)] = \frac{ε}{2^{1/p}} d_{T} (u, v). (4)

To get tighter control on the Euclidean distortion of trees we introduce the notion of δ-strong colorings.

Definition 2.4 (δ-strong coloring). We say that a coloring χ : E → ℤ is δ-strong if it is monotone, and for every u, v ∈ V

∑_{k∈ℤ}ℓ_{k}^{χ}(u, v) · 1_{\{ℓ_{k}^{χ}(u,v)≥δd_{T} (u,v)\}} ≥ \frac{1}{2}d_{T} (u, v).

In words, we demand that at least half of the shortest path joining u and v is covered by color classes of length at least δd_{T} (u, v). As before, we define δ^{∗}(T) to be the largest δ for which T admits an δ-strong coloring.

The notions of δ-strong colorings and ε-good colorings are related via the following simple lemma.

Lemma 2.5. Every weighted tree T satisfies δ^{∗}(T) ≥ 2^{−3/ε^{∗}(T)}.

Proof. Let χ be an ε-good coloring of T. We will prove that it is also 2^{−3/ε}-strong. In fact, we shall show that for every α ∈ (0, 1] and u, v ∈ V, the total length of the monochromatic segments of length at least αd_{T} (u, v) on the path P (u, v) satisfies

∑_{k∈ℤ}ℓ_{k}^{χ}(u, v) · 1_{\{ℓ_{k}^{χ}(u,v)≥αd_{T} (u,v)\}} ≥ (1 − (\frac{α}{ε})^{ε/2}) d_{T} (u, v).  (5)

Choosing α = 2^{−3/ε} in (5), and using the fact that 2^{1/ε} ≥ \frac{1}{ε}, we deduce that χ is 2^{−3/ε}-strong. The proof of (5) is by induction on d_{T} (u, v). If d_{T} (u, v) is minimal then P (u, v) is an edge, and hence monochromatic, so that the assertion holds trivially. In general, since the coloring χ is ε-good, there are two vertices on the path P (u, v) such that the segment P (a, b) is monochromatic and d_{T} (a, b) ≥ εd_{T} (u, v). Without loss of generality we assume that d_{T} (a, u) < d_{T} (b, u). If ε < α then there is nothing to prove, so assume that ε ≥ α. Denoting A = d_{T} (u, a), B = d_{T} (b, v) and D = d_{T} (u, v), we apply the inductive hypothesis to the paths joining u and a and b and v, to get that

∑_{k∈ℤ}ℓ_{k}^{χ}(u, v) · 1_{\{ℓ_{k}^{χ}(u,v)≥αd_{T} (u,v)\}} ≥ d_{T} (a, b) + (1 − (\frac{Dα}{Aε})^{ε/2}) A + (1 − (\frac{Dα}{Bε})^{ε/2}) B

= D − (\frac{Dα}{ε})^{ε/2} (A^{1−ε/2} + B^{1−ε/2})
≥ D − 2 (\frac{Dα}{ε})^{ε/2} (\frac{A + B}{2} )^{1−ε/2}  (6)
≥ D − 2 (\frac{Dα}{ε})^{ε/2} (\frac{(1 − ε)D}{2} )^{1−ε/2}  (7)
≥ (1 − (\frac{α}{ε})^{ε/2}) D,  (8)

Where in (6) we used the concavity of the function t ↦ t^{1−ε/2}, in (7) we used the fact that D = A+B+d_{T} (a, b) ≥ A+B+εD, and in (8) we used the elementary inequality 2^{ε/2}(1−ε)^{1−ε/2} ≤ 1, which is valid for every ε ∈ [0, 1].

In [28], Matoušek proves that if χ is a monotone edge-coloring of T such that every root-leaf path contains at most M distinct color classes, then c_{p}(T) ≤ O ((log M)^{min\{ \frac{1}{p} , \frac{1}{2} \}}). Clearly any such coloring is 1/(2M)-strong. The next theorem generalizes Matoušek’s result along these lines.

We suggest that the reader skip this rather technical proof upon a first reading. In particular, the much simpler Lemma 2.3 suffices for the proof of Theorem 1.1, although it does not give the optimal quantitative bounds of Theorem 1.2.

Theorem 2.6. For every weighted tree T = (V, E) and p ≥ 1,

c_{p}(T) ≤ 4 [log (\frac{2}{δ^{∗}(T)})]^{min\{ \frac{1}{p} , \frac{1}{2} \}} .

Proof. We may assume that p ∈ [2, ∞), since if p ∈ [1, 2) the required result follows by embedding T into ℓ_{2} ⊆ L_{p}. Fix δ < min{δ^{∗}(T), 1/2} and let χ : E → ℤ be a δ-strong coloring. Let {e_{k}}_{k∈ℤ} be as in Lemma 2.3. For v ∈ V we denote by (k_{1}(v), …, k_{m_{v}}(v)) the sequence of color classes encountered on the path from the root to v. We shall denote by d_{j}(v) the distance that the color class k_{j}(v) contributes to the path from the root to v, i.e.

d_{j}(v) = ∑_{\begin{matrix}e∈P (v) \\ χ(e)=k_{j}(v) \end{matrix}} ℓ(e).

Now let

s_{i}(v) = ∑_{j=i}^{m_{v}} max \{0, d_{j}(v) − \frac{δ}{2} ∑_{h=i}^{j} d_{h}(v)\} ,

and define f : V → ℓ_{p}(ℤ) by

f(v) = ∑_{i=1}^{m_{v}}[d_{i}(v)]^{1/p}[s_{i}(v)]^{(p−1)/p}e_{k_{i}(v)}.

We will break the proof the proof of the fact that f satisfies the required distortion bound into several claims.

Claim 2.7. For all v ∈ V and j ∈ {1, …, m_{v}},

s_{i}(v) ≥ \frac{1}{4} ∑_{j=i}^{m_{v}} d_{j}(v).

Proof. This is where the fact that χ is a δ-strong coloring comes in. Indeed,

s_{i}(v) = ∑_{j=i}^{m_{v}} max \{0, d_{j}(v) − \frac{δ}{2} ∑_{h=i}^{j} d_{h}(v)\} ≥ ∑_{\begin{matrix}j∈\{i,...,m_{v}\} \\ d_{j}(v)≥δ ∑_{h=i}^{mv} d_{h}(v) \end{matrix}} \frac{d_{j}(v)}{2} ≥ \frac{1}{4} ∑_{j=i}^{m_{v}} d_{j}(v).

Claim 2.8. ∥f∥_{Lip} ≤ [5 log(3/δ)]^{1/p}.

Proof. We need to show that for every edge (u, v) ∈ E, ∥f(u) − f(v)∥_{p} ≤ 10[log(1/δ)]^{1/p}. Assume that v is further than u from the root of T. In this case k_{1}(u) = k_{1}(v), …, k_{m_{u}}(u) = k_{m_{u}}(v) and m_{v} ∈ {m_{u}, m_{u} +1}. If m_{v} = m_{u} +1 then we denote for the sake of simplicity d_{m_{v}}(u) = s_{m_{v}}(u) = 0. With this notation we have that

∥f(u) − f(v)∥_{p}^{p} = ∑_{i=1}^{m_{v}} |[d_{i}(u)]^{1/p}[s_{i}(u)]^{(p−1)/p} − [d_{i}(v)]^{1/p}[s_{i}(v)]^{(p−1)/p}|^{p}

= ∑_{i=1}^{m_{v}−1} d_{i}(v) |[s_{i}(u)]^{(p−1)/p} − [s_{i}(v)]^{(p−1)/p}|^{p} +
|[d_{m_{v}}(u)]^{1/p}[s_{m_{v}}(u)]^{(p−1)/p} − [d_{m_{v}}(v)]^{1/p}[s_{m_{v}}(v)]^{(p−1)/p}|^{p} .

Note that by our definitions, s_{m_{v}}(u) = d_{m_{v}}(u) and s_{m_{v}}(v) = d_{m_{v}}(v). Thus

∥f(u) − f(v)∥_{p}^{p} = ∑_{i=1}^{m_{v}−1} d_{i}(v) |[s_{i}(u)]^{(p−1)/p} − [s_{i}(v)]^{(p−1)/p}|^{p} + |d_{m_{v}}(u) − d_{m_{v}}(v)|^{p}

≤ ∑_{i=1}^{m_{v}−1} d_{i}(v) |[s_{i}(u)]^{(p−1)/p} − [s_{i}(v)]^{(p−1)/p}|^{p} + [d_{T} (u, v)]^{p}.  (9)

Observe that for all i ∈ {1, …, m_{v} − 1}, s_{i}(v) ≥ s_{i}(u). Thus

|[s_{i}(u)]^{(p−1)/p} − [s_{i}(v)]^{(p−1)/p}| ≤ \frac{|s_{i}(u) − s_{i}(v)|}{[s_{i}(v)]^{1/p}},  (10)

where we used the elementary inequality y^{α} − x^{α} ≤ \frac{y−x}{y^{1−α}}, which is valid for all y ≥ x > 0 and α ∈ (0, 1).

Observe that for every i ≤ m_{v} − 1,

s_{i}(v) − s_{i}(u) = max \{0, d_{m_{v}}(v) − \frac{δ}{2} ∑_{h=i}^{m_{v}} d_{h}(v)\} − max \{0, d_{m_{v}}(u) − \frac{δ}{2} ∑_{h=i}^{m_{v}} d_{h}(u)\} ≤ d_{T} (u, v). (11)

Thus, combining (10) and (11) we see that

∑_{i=1}^{m_{v}−1} d_{i}(v) |[s_{i}(u)]^{(p−1)/p} − [s_{i}(v)]^{(p−1)/p}|^{p} ≤ ∑_{i=1}^{m_{v}−1} d_{i}(v) · \frac{|s_{i}(u) − s_{i}(v)|^{p}}{s_{i}(v)}

≤ [d_{T} (u, v)]^{p} · ∑_{\begin{matrix}i∈\{1,...,m_{v}−1\} \\ s_{i}(u)≠s_{i}(v) \end{matrix}} \frac{d_{i}(v)}{s_{i}(v)}

≤ 4[d_{T} (u, v)]^{p} · ∑_{\begin{matrix}i∈\{1,...,m_{v}−1\} \\ s_{i}(u)≠s_{i}(v) \end{matrix}} \frac{d_{i}(v)}{∑_{j=i}^{m_{v}} d_{j}(v)}, (12)

where in the last line we used Claim 2.7.

Observe that for every x_{1}, …, x_{k} > 0,

∑_{i=1}^{k} \frac{x_{i}}{x_{i} + x_{i+1} + ⋯ + x_{k} + 1} ≤ ∑_{i=k}^{1} ∫_{x_{i+1}+···+x_{k}}^{x_{i}+···+x_{k}} \frac{dt}{t + 1} = ∫_{0}^{x_{1}+···+x_{k}} \frac{dt}{t + 1} = log(x_{1} + ⋯ + x_{k} + 1)

Thus

∑_{\begin{matrix}i∈\{1,...,m_{v}−1\} \\ s_{i}(u)≠s_{i}(v) \end{matrix}} \frac{d_{i}(v)}{∑_{j=i}^{m_{v}} d_{j}(v)} = ∑_{\begin{matrix}i∈\{1,...,m_{v}−1\} \\ s_{i}(u)≠s_{i}(v) \end{matrix}} \frac{d_{i}(v)/d_{m_{v}}(v)}{(∑_{j=i}^{m_{v}−1} d_{j}(v)/d_{m_{v}}(v)) + 1}

≤ log (1 + \frac{1}{d_{m_{v}}(v)} ∑_{\begin{matrix}i∈\{1,...,m_{v}−1\} \\ s_{i}(u)≠s_{i}(v) \end{matrix}} d_{i}(v)) .  (13)

Let i be the smallest integer in {1, …, m_{v} − 1} such that s_{i}(u) ≠ s_{i}(v). Then by the definition of s_{i}(·),

d_{m_{v}}(v) > \frac{δ}{2} ∑_{h=i}^{m_{v}} d_{h}(v).

It follows that

log (1 + \frac{1}{d_{m_{v}}(v)} ∑_{\begin{matrix}i∈\{1,...,m_{v}−1\} \\ s_{i}(u)≠s_{i}(v) \end{matrix}} d_{i}(v)) ≤ log (1 + \frac{1}{d_{m_{v}}(v)} ∑_{h=i}^{m_{v}} d_{h}(v)) ≤ log (1 + \frac{2}{δ}) .

Plugging this bound into (13), and using (12) and (9), we get that

∥f(u) − f(v)∥_{p} ≤ [4 log (1 + \frac{2}{δ}) + 1]^{1/p} · d_{T} (u, v) ≤ [5 log(3/δ)]^{1/p} · d_{T} (u, v).

Our final claim bounds ∥f^{−1}∥_{Lip}.

Figure 2: A schematic description of the location of u and v in the tree T. The bold segment corresponds to the color class k_{j}(u) = k_{j}(v).

Claim 2.9. The embedding f is invertible, and ∥f^{−1}∥_{Lip} ≤ 48.

Proof. Fix u, v ∈ V, u ≠ v, and let j be the integer satisfying k_{1}(u) = k_{1}(v), …, k_{j}(u) = k_{j}(v) and k_{j+1}(u) ≠ k_{j+1}(v). It follows that d_{1}(u) = d_{1}(v), …, d_{j−1}(u) = d_{j−1}(v), and we may assume without loss of generality that d_{j}(u) ≥ d_{j}(v). With this notation (see Figure 2.1 below),

d_{T} (u, v) = d_{j}(u) − d_{j}(v) + ∑_{i=j+1}^{m_{u}} d_{i}(u) + ∑_{i=j+1}^{m_{v}} d_{i}(v).  (14)

On the other hand,

∥f(u) − f(v)∥_{p}^{p} ≥ |[d_{j}(u)]^{1/p}[s_{j}(u)]^{(p−1)/p} − [d_{j}(v)]^{1/p}[s_{j}(v)]^{(p−1)/p}|^{p} +
∑_{i=j+1}^{m_{u}} d_{i}(u)[s_{i}(u)]^{p−1} + ∑_{i=j+1}^{m_{v}} d_{i}(v)[s_{i}(v)]^{p−1}.  (15)

Using Claim 2.7 we see that

∑_{i=j+1}^{m_{u}} d_{i}(u)[s_{i}(u)]^{p−1} ≥ \frac{1}{4^{p−1}} ∑_{i=j+1}^{m_{u}} d_{i}(u) (∑_{h=i}^{m_{u}} d_{h}(u))^{p−1}

≥ \frac{1}{4^{p−1}} ∑_{i=j+1}^{m_{u}} ∫_{d_{i+1}(u)+···+d_{mu}(u)}^{d_{i}(u)+···+d_{mu}(u)} t^{p−1}dt

= \frac{1}{4^{p−1}} ∫_{0}^{d_{j+1}(u)+···+d_{mu}(u)} t^{p−1}dt

= \frac{1}{p4^{p−1}} · ( ∑_{i=j+1}^{m_{u}} d_{i}(u))^{p} .  (16)

Similarly,

∑_{i=j+1}^{m_{v}} d_{i}(v)[s_{i}(v)]^{p−1} ≥ \frac{1}{p4^{p−1}} · ( ∑_{i=j+1}^{m_{v}} d_{i}(v))^{p} .  (17)

We now consider two cases: Case 1. \frac{d_{j}(u)−d_{j}(v)}{2} ≤ ∑_{i=j+1}^{m_{v}} d_{i}(v). In this case, using (14) we see that

[d_{T} (u, v)]^{p} ≤ 3^{p} ( ∑_{i=j+1}^{m_{u}} d_{i}(u) + ∑_{i=j+1}^{m_{v}} d_{i}(v))^{p}
≤ 3^{p} · 2^{p−1} ( ∑_{i=j+1}^{m_{u}} d_{i}(u))^{p} + 3^{p} · 2^{p−1} ( ∑_{i=j+1}^{m_{v}} d_{i}(v))^{p}
≤ p4^{p−1} · 3^{p} · 2^{p−1}∥f(u) − f(v)∥_{p}^{p},

where in the last inequality we plugged the bounds (16) and (17) into (15). Thus we get that

∥f(u) − f(v)∥_{p} ≥ \frac{1}{48} · d_{T} (u, v),

as required. Case 2. \frac{d_{j}(u)−d_{j}(v)}{2} > ∑_{i=j+1}^{m_{v}} d_{i}(v). In this case we observe that

s_{j}(u) = ∑_{i=j}^{m_{u}} max \{0, d_{i}(u) − \frac{δ}{2} ∑_{h=j}^{i} d_{h}(u)\} ≥ (1 − \frac{δ}{2}) d_{j}(u),

and similarly

s_{j}(v) ≤ (1 − \frac{δ}{2}) d_{j}(v) + ∑_{i=j+1}^{m_{v}} d_{i}(v) ≤ (1 − \frac{δ}{2}) d_{j}(v) + \frac{d_{j}(u) − d_{j}(v)}{2}.

Thus

[d_{j}(u)]^{1/p}[s_{j}(u)]^{(p−1)/p} − [d_{j}(v)]^{1/p}[s_{j}(v)]^{(p−1)/p} ≥ (1 − \frac{δ}{2})^{(p−1)/p} d_{j}(u) −

(1 − \frac{δ}{2})^{(p−1)/p} d_{j}(v) · (1 + \frac{d_{j}(u) − d_{j}(v)}{(2 − δ)d_{j}(v)})^{(p−1)/p}

≥ (1 − \frac{δ}{2})^{(p−1)/p} d_{j}(u) − (1 − \frac{δ}{2})^{(p−1)/p} d_{j}(v) · (1 + \frac{d_{j}(u) − d_{j}(v)}{(2 − δ)d_{j}(v)})
= (1 − \frac{δ}{2})^{(p−1)/p} · \frac{1 − δ}{2 − δ} · [d_{j}(u) − d_{j}(v)]
≥ \frac{d_{j}(u) − d_{j}(v)}{4}.

where we used the fact that δ ≤ \frac{1}{2}. Using (15) and the bounds (16) and (17), it follows that

∥f(u) − f(v)∥_{p}^{p} ≥ \frac{1}{4^{p}} [d_{j}(u) − d_{j}(v)]^{p} + \frac{1}{p4^{p−1}} · ( ∑_{i=j+1}^{m_{u}} d_{i}(u))^{p} + \frac{1}{p4^{p−1}} · ( ∑_{i=j+1}^{m_{v}} d_{i}(v))^{p}

≥ \frac{1}{p4^{p} · 3^{p−1}} (d_{j}(u) − d_{j}(v) + ∑_{i=j+1}^{m_{u}} d_{i}(u) + ∑_{i=j+1}^{m_{v}} d_{i}(v))^{p}

≥ \frac{1}{24^{p}} · [d_{T} (u, v)]^{p}.

Claim 2.9, together with Claim 2.8, concludes the proof of Theorem 2.6.

2.2 Relating coloring bounds to the containment of large binary trees

The following theorem, in conjunction with Theorem 2.6 and Lemma 2.5, implies Theorem 2.1. If one is concerned with simply giving some upper bound on c_{p}(T) in terms of ℬ_{T} (c), then it suffices to combine the following theorem with Lemma 2.3.

Theorem 2.10. For every weighted tree T = (V, E) and every c > 1,

ℬ_{T} (c) ≥ \frac{c − 1}{250c} · \frac{1}{ε^{∗}(T)}.

Proof. We start by introducing some notation. For a vertex v ∈ V we denote by 𝒞 (v) the set of all children of v in T. Given u ∈ 𝒞 (v) we denote by T_{u} = (V_{u}, E_{u}) the subtree rooted at u. We also let F_{u} denote the tree F_{u} = (V_{u} ∪ {v}, E_{u} ∪ {(v, u)}), i.e. F_{u} is T_{u} plus the “incoming” edge (v, u).

Recall that B_{k} = (V_{k}, E_{k}) is the complete binary tree of height k. Let r_{k} be the root of B_{k}, and define an auxiliary tree M_{k} by M_{k} = (V_{k} ∪ {m_{k}}, E_{k} ∪ {(m_{k}, r_{k})}) (i.e. M_{k} is B_{k} with an extra incoming edge). Given a connected subtree H of T rooted at r_{H}, we shall say that H admits a copy of M_{k} at scale j if there exits a one-to-one mapping f : M_{k} → H such that

1. f(m_{k}) = r_{H}

2. ∥f∥_{Lip} ≤ \frac{9c}{c−1} · 4^{j} and ∥f^{−1}∥_{Lip} ≤ \frac{c−1}{9·4^{j}} (thus in particular dist(f) ≤ c).

We define

μ_{j}(H) = max {k ∈ ℕ : H admits a copy of M_{k} at scale j} ,

or μ_{j}(H) = −1 if no such k exists.

We shall now define a function g : V → ℤ ∪ {∞} and a coloring χ : E → ℤ. These mappings will be constructed by induction as follows. We start by setting g(r) = ∞. Assume inductively that the construction is done so that whenever v ∈ V is such that g(v) is defined, if u is a vertex on the path P (v) then g(u) has already been defined, and for every edge e ∈ E incident with v, χ(e) has been defined.

Let v ∈ V be a vertex closest to the root r for which g(v) hasn’t yet been defined. Then, by our assumption, for every e ∈ P (v), χ(e) has been defined, and for every vertex u other than v lying on the path P (v), g(u) has been defined. Let β_{χ}(v) ⊆ V denote the set of breakpoints of χ in P (v), i.e. the set of vertices on P (v) for which the incoming and outgoing edges have distinct colors (for convenience, in what follows we shall also consider the root r as a breakpoint of χ). We define

g(v) = max {j ∈ ℤ : ∀ u ∈ β_{χ}(v), d_{T} (u, v) ≥ 4^{min{g(u),j}}} .

Having defined g(v) we choose one of its children w ∈ 𝒞 (v) for which

μ_{g(v)}(F_{w}) = max_{z∈𝒞 (v)} μ_{g(v)}(F_{z}).

Letting u be the father of v on the path P (v), we set χ(v, w) = χ(u, v), and we assign arbitrary new (i.e. which haven’t been used before) distinct colors to each of the edges {(v, z)}_{z∈𝒞 (v)\{w}}. In other words, given the “scale” j = g(v) we order the children of v according to the size of the copy of M_{k} which they admit beneath them at scale j. We then continue coloring with the color χ(u, v) the path P (v) along the edge joining v and its child which admits the largest M_{k} at scale j, and color the remaining edges incident with v by arbitrary distinct new colors.

This definition clearly results in a monotone coloring χ. To motivate this somewhat complicated construction, we shall now prove some of the crucial properties of χ and g which will be used later.

Claim 2.11. Let P be any monotone path in T, and let (b_{1}, b_{2}, …, b_{m}) be the sequence of breakpoints along P ordered down the tree (i.e. in increasing distance from the root). Assume that j ∈ ℤ satisfies for every i ∈ \{2, …, m\}, d_{T} (b_{i}, b_{i−1}) ≤ 4^{j}, and assume also that d_{T} (b_{1}, b_{m}) ≥ \frac{30c}{c−1} · 4^{j}. Then there exists a subsequence of the indices 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ m such that

1. k ≥ \frac{c−1}{20c·4^{j}} · d_{T} (b_{1}, b_{m}).

2. For every s ∈ {1, …, k} we have g(b_{i_{s}}) = j.

3. For every s ∈ \{1, …, k − 1\} we have \frac{9}{c−1} · 4^{j} ≤ d_{T} (b_{i_{s+1}}, b_{i_{s}}) ≤ \frac{9c}{c−1} · 4^{j}.

Proof. We shall show that if i ∈ \{1, …, m\} is such that d_{T} (b_{i}, b_{m}) > \frac{4^{j+1}}{3} then there exists an index t ∈ {1, …, m} with g(b_{t}) = j and d_{T} (b_{t}, b_{i}) ≤ 4^{j+1}. Assuming this fact for the moment, we conclude the proof as follows. Let i_{1} be the smallest integer in {2, …, m} such that g(b_{i_{1}}) = j. Then d_{T} (b_{i_{1}}, b_{1}) ≤ 4^{j+1}. Assuming we defined i_{1} < i_{2} < ⋯ < i_{s}, if d_{T} (b_{i_{s}}, b_{m}) ≤ \frac{9c}{c−1} · 4^{j} we stop the construction, and otherwise we let t be the smallest integer bigger than i_{s} such that d_{T} (b_{t}, b_{i_{s}}) ≥ \frac{4c+5}{c−1} · 4^{j}. Since d_{T} (b_{t−1}, b_{i_{s}}) < \frac{4c+5}{c−1} · 4^{j}, we know that d_{T} (b_{t}, b_{i_{s}}) < \frac{4c+5}{c−1} · 4^{j} + 4^{j}. Thus d_{T} (b_{t}, b_{m}) > d_{T} (b_{i_{s}}, b_{m})− \frac{4c+5}{c−1} ·4^{j} −4^{j} > \frac{4^{j+1}}{3} (because we are assuming that d_{T} (b_{i_{s}}, b_{m}) < \frac{9c}{c−1} ·4^{j}). So, there exists i_{s+1} ∈ {1, …, m} such that g(b_{i_{s+1}}) = j and d_{T} (b_{i_{s+1}}, b_{t}) ≤ 4^{j+1}. Since by construction d_{T} (b_{t}, b_{i_{s}}) ≥ \frac{4c+5}{c−1} · 4^{j} > 4^{j+1} we deduce that i_{s+1} > i_{s} and

\frac{9}{c − 1} · 4^{j} ≤ d_{T} (b_{t}, b_{i_{s}}) − d_{T} (b_{i_{s+1}}, b_{t}) ≤ d_{T} (b_{i_{s+1}}, b_{i_{s}}) ≤ d_{T} (b_{i_{s+1}}, b_{t}) + d_{T} (b_{t}, b_{i_{s}}) ≤ \frac{9c}{c − 1} · 4^{j}.

This construction terminates after k steps, in which case we have that

d_{T} (b_{1}, b_{m}) = d_{T} (b_{1}, b_{i_{1}}) + ∑_{s=1}^{k−1} d_{T} (b_{i_{s}}, b_{i_{s+1}}) + d_{T} (b_{i_{k}}, b_{m}) ≤ 4^{j+1} + (k − 1) · \frac{9c}{c − 1} · 4^{j} + \frac{9c}{c − 1} · 4^{j}.

Since d_{T} (b_{1}, b_{m}) ≥ \frac{30c}{c−1} · 4^{j}, this implies the required result.

It remains to show that if i ∈ \{1, …, m\} is such that d_{T} (b_{i}, b_{m}) > \frac{4^{j+1}}{3} then there exists t ∈ {1, …, m} with g(b_{t}) = j and d_{T} (b_{t}, b_{i}) ≤ 4^{j+1}. We first claim that for every i ∈ {1, …, m} there is a breakpoint w ∈ β_{χ}(b_{i}) with g(w) ≥ j and d_{T} (w, b_{i}) < \frac{4^{j+1}}{3} . Indeed, if g(b_{i}) ≥ j then there is nothing to prove, so assume that g(b_{i}) < j. By the definition of g there exists a breakpoint w_{1} ∈ β_{χ}(b_{i}) such that

4^{min{g(w_{1}),g(b_{i})}} ≤ d_{T} (w_{1}, b_{i}) < 4^{min{g(w_{1}),g(b_{i})+1}}.

Thus necessarily g(w_{1}) ≥ g(b_{i}) + 1 and d_{T} (w_{1}, b_{i}) < 4^{g(b_{i})+1} < 4^{j}. If g(b_{i}) + 1 ≥ j then we are done by taking w = w_{1}. Otherwise, continuing in this manner we find a breakpoint w_{2} ∈ β_{χ}(w_{1}) ⊆ β_{χ}(b_{i}) with g(w_{2}) ≥ g(w_{1}) + 1 ≥ g(b_{i}) + 2 and d_{T} (w_{2}, w_{1}) < 4^{g(w_{1})+1}. This procedure terminates when we find a sequence b_{i} = w_{0}, w_{1}, w_{2}, …, w_{t} with g(w_{t}) ≥ j, g(w_{t−1}) < j, and for every 0 ≤ s ≤ t − 1, g(w_{s+1}) ≥ g(w_{s}) + 1 and d_{T} (w_{s+1}, w_{s}) < 4^{g(w_{s})+1}. Thus

d_{T} (b_{i}, w_{t}) = ∑_{s=0}^{t−1} d_{T} (w_{s+1}, w_{s}) < ∑_{s=0}^{t−1} 4^{g(w_{s})+1} < ∑_{s=−∞}^{j} 4^{s} = \frac{4^{j+1}}{3} .

Now, assume that d_{T} (b_{i}, b_{m}) > \frac{4^{j+1}}{3} . Let s be the largest integer in \{i + 1, …, m\} such that d_{T} (b_{s}, b_{i}) ≤ \frac{4^{j+1}}{3} (such an integer s exists since d_{T} (b_{i}, b_{i+1}) ≤ 4^{j}). Then \frac{4^{j+1}}{3} < d_{T} (b_{s+1}, b_{i}) ≤ \frac{4^{j+1}}{3} + 4^{j}. By the previous argument there is a break point w ∈ β_{χ}(b_{s+1}) with g(w) ≥ j and d_{T} (w, b_{s+1}) < \frac{4^{j+1}}{3} . This implies that w = b_{t} for some t ∈ \{i+1, …, s+1\}, and d_{T} (b_{i}, b_{t}) ≤ \frac{4^{j+1}}{3} +4^{j}.

We proved that as long as b_{i} satisfies d_{T} (b_{i}, b_{m}) > \frac{4^{j+1}}{3} , there are 1 ≤ t ≤ i ≤ s ≤ m such that g(b_{s}) ≥ j, g(b_{t}) ≥ j, and d_{T} (b_{t}, b_{i}) ≤ \frac{4^{j+1}}{3} , d_{T} (b_{s}, b_{i}) ≤ \frac{4^{j+1}}{3} + 4^{j}. Thus, by the definition of g,

4^{min\{g(b_{s}),g(b_{t})\}} ≤ d_{T} (b_{s}, b_{t}) ≤ \frac{2 · 4^{j+1}}{3} + 4^{j} < 4^{j+1}.

It follows that either g(b_{s}) = j or g(b_{t}) = j, as required.

To conclude the proof of Theorem 2.10 we may assume that ε^{∗}(T) < \frac{c−1}{240c}, since otherwise the assertion of Theorem 2.10 is trivial. Fix \frac{c−1}{240c} > ε > ε^{∗}(T). By the definition of ε^{∗}(T), the coloring χ constructed above is not ε-good. Thus, there exist two vertices u, v ∈ V such that the path P (u, v) does not contain a monochromatic segment of length at least εd_{T} (u, v). We may assume without loss of generality that u is an ancestor of v, and let (b_{1}, b_{2}, …, b_{m}) be the sequence of breakpoints along this path, enumerated down the tree (i.e. from u to v, not necessarily including u or v). Denoting D = d_{T} (u, v) we have that d_{T} (u, b_{1}), d_{T} (v, b_{m}), d_{T} (b_{i}, b_{i+1}) ≤ εD for all i ∈ {1, …, m − 1}. Fix j ∈ ℤ such that εD ≤ 4^{j} ≤ 4εD. This choice implies that d_{T} (b_{i}, b_{i+1}) ≤ 4^{j} and d_{T} (b_{1}, b_{m}) ≥ (1 − 2ε)D ≥ \frac{1−2ε}{4ε} · 4^{j} ≥ \frac{30c}{c−1} · 4^{j}. By Claim 2.11 there is an integer k ≥ \frac{(c−1)(1−2ε)D}{20c·4^{j}} ≥ \frac{c−1}{250c} · \frac{1}{ε} + 2 (using the upper bound on ε) and a sequence of breakpoints s_{1}, …, s_{k} on the path P (u, v) (ordered down the tree) such that g(s_{1}) = ⋯ = g(s_{k}) = j and for i ∈ \{1, …, k − 1\}, \frac{9}{c−1} · 4^{j} ≤ d_{T} (s_{i}, s_{i+1}) ≤ \frac{9c}{c−1} · 4^{j}.

The proof of Theorem 2.10 will be complete once we show that ℬ_{T} (c) ≥ k−2. For i ∈ {1, …, k} let t_{i} be the child of s_{i} along the path P (u, v). We will prove by reverse induction on i ∈ {1, …, k−1} Figure 3: A schematic description of the gluing procedure in the inductive step. Because s_{i} was a breakpoint it must have two copies of M_{k−i−1} at scale j below it.

that μ_{j}(F_{t_{i}}) ≥ k − i − 1, implying the required result. The base case is true, i.e. μ_{j}(F_{t_{k−1}}) ≥ 0, since the pair (s_{k−1}, s_{k}) constitutes a copy of M_{0} at scale j.

Assuming that μ_{j}(F_{t_{i}}) ≥ k − i − 1 we shall prove that μ_{j}(F_{t_{i−1}}) ≥ k − i. Since s_{i} was a breakpoint, the construction of χ implies that there must be a child t′_{i} of s_{i}, other than t_{i}, for which μ_{j}(F_{t′_{i}}) > μ_{j}(F_{t_{i}}) ≥ k − i − 1. Thus, there exist one to one mappings f, f′ : M_{k−i−1} → T such that f(m_{k−i−1}) = f′(m_{k−i−1}) = s_{i}, f(M_{k−i−1}) ⊆ F_{t_{i}}, f′(M_{k−i−1}) ⊆ F_{t′_{i}}, ∥f∥_{Lip}, ∥f′∥_{Lip} ≤ \frac{9c}{c−1} · 4^{j}, and ∥f^{−1}∥_{Lip}, ∥(f′)^{−1}∥_{Lip} ≤ \frac{c−1}{9·4^{j}}. Thinking of M_{k−i} as two disjoint copies of M_{k−i−1}, joined at the root m_{k−i}, we may “glue” f and f′ to an embedding \overline{f} of M_{k−i} by setting \overline{f}(m_{k−i}) = s_{i−1}. Since \frac{9}{c−1} · 4^{j} ≤ d_{T} (s_{i}, s_{i−1}) ≤ \frac{9c}{c−1} · 4^{j}, this results in an embedding at scale j of M_{k−i} into F_{t_{i−1}}, as required (see Figure 3).

2.3 Embedding into finite-dimensional spaces

We recall that the doubling constant λ(X) of a metric space X is the infimal value of λ for which every ball in X can be covered by λ balls of half the radius. If S ⊆ X is a δ-separated set in X, then a standard observation is that |S| ≤ λ(X)^{O(diam(S)/δ)}. This section is devoted to a simpler proof of the following theorem of Gupta, Krauthgamer, and Lee originally proved in [17]. (We stress that the only results we need for this section are Lemma 2.3 and Theorem 2.10.)

Theorem 2.12 ([17]). A tree metric T embeds into a finite-dimensional Euclidean space if and only if λ(T) < ∞. In other words, every doubling tree T admits a D-embedding into ℝ^{k} with D, k depending only on λ(T).

Let T = (V, E) be a weighted, rooted tree. Note that the “only if” part of Theorem 2.12 is trivial. In order to prove the remaining implication we need a coloring notion weaker than ε-good. Let χ : E → ℤ be a coloring of the edges of T which is not necessarily monotone. We will say that χ is ε-reasonable if the following holds for every u, v ∈ V. Let w = lca(u, v), and recall that P (w, u), P (w, v) denote the paths from w to u and v, respectively. Then there should exist a color c ∈ ℤ for which

|  ∑_{e∈P (w,u):χ(e)=c} ℓ(e) − ∑_{e∈P (w,v):χ(e)=c} ℓ(e)| ≥ εd_{T} (u, v).  (18)

Since a reasonable coloring is not necessarily monotone, it is possible to construct such colorings where χ^{−1}(E) is finite even though T might be infinite. The number of colors used, i.e. |χ^{−1}(E)|, controls the dimension of the embedding from Lemma 2.3.

Lemma 2.13. Let T = (V, E) be a weighted tree, and suppose that T admits an ε-reasonable coloring for some ε > 0. Then T embeds in ℝ^{k} (equipped, e.g. with the L_{2} norm) with distortion O(1/ε), and k = |χ^{−1}(E)|.

Proof. Let χ : E → ℤ be an ε-reasonable coloring of T. We use the embedding f : V → ℓ_{2} of Lemma 2.3. In particular, it is easy to check that the definition of the embedding does not require χ to be monotone. Observe that Im(f) lies naturally in span{e_{k} : k ∈ χ^{−1}(E)}, and thus we may assume that f : V → ℝ^{k} with k = |χ^{−1}(E)|.

From the proof of Lemma 2.3, we conclude that ∥f∥_{Lip} ≤ 1, and thus we need only consider ∥f^{−1}∥_{Lip}. But it is easy to see that condition (18) suffices to obtain a similar lower bound in equation (4) of Lemma 2.3.

We note that the dependence of k on |χ^{−1}(E)| in the above lemma can be improved to k = O(log |χ^{−1}(E)|) using a “nearly-orthogonal” set of vectors instead of the orthonormal set {e_{k}}_{k∈ℤ}. We refer to [17] for details.

Now, clearly ℬ_{T} (2) ≤ O(log λ(T)) since λ(B_{m}) = 2^{Θ(m)}, hence ε^{∗}(T) ≥ 1/O(log λ(T)) using Theorem 2.10. In light of Lemma 2.13 and the preceding remark, the following result completes the proof of Theorem 2.12. (Note that we can assume T finite by compactness—a tree embeds into a finite-dimensional Euclidean space if and only if every finite subset embeds with uniformly bounded distortion).

Theorem 2.14. Let T = (V, E) be a finite, weighted tree. If T admits an ε-good coloring, then it also admits an O(ε)-reasonable coloring with only λ(T)^{(1/ε)^{O(1/ε)}} colors.

Proof. We will say that a monotone coloring χ : E → ℤ is regular if the following holds: For every maximal monochromatic segment s = {e_{1}, e_{2}, …, e_{k}} ⊆ E (with edges ordered down the tree), and for every 1 ≤ i ≤ k, we have ℓ(e_{i+1}) ≤ 2 ∑_{j=1}^{i} ℓ(e_{i}).

Lemma 2.15. If a finite tree T admits an ε-good coloring, then T admits an O(ε)-good regular coloring.

Proof. Let T = (V, E) be a rooted tree, and let χ_{0} : E → ℤ be an ε-good coloring of T. Suppose that some monochromatic segment s = {e_{1}, e_{2}, …, e_{k}} ⊆ E violates the regularity condition. Let i ∈ [k] be the smallest index for which ℓ(e_{i+1}) > 2 ∑_{j=1}^{i} ℓ(e_{i}). We derive a new coloring χ_{1} : E → ℤ by coloring the edges e_{1}, …, e_{i} with a new unused color c ∈ ℤ, i.e. χ_{1}(e) = c if e = e_{j} for some 1 ≤ j ≤ i and χ_{1}(e) = χ_{0}(e) otherwise. Continue this process inductively until the resulting coloring χ′ : E → ℤ is regular. This process terminates because T is finite. It remains to show that χ′ is O(ε)-good.

To this end, let s = {e_{1}, …, e_{k}} ⊆ E be a maximal monochromatic segment according to χ_{0}, and let s_{1}, s_{2}, …, s_{m} ⊆ s be the maximal monochromatic segments of s according to χ′, ordered down the tree. By construction, we have

ℓ(s_{m}) ≥ 2ℓ(s_{m−1}) ≥ ℓ(s_{m−1}) + 2ℓ(s_{m−2}) ≥ ⋯ ≥ ℓ(s_{1}) + ⋯ + ℓ(s_{m−1}),

hence ℓ(s_{m}) ≥ \frac{1}{2}ℓ(s). It follows that χ′ is a regular ε/2-good coloring of T.

Let T be a rooted tree, and let χ : E → ℤ be an ε-good coloring of T. Using the preceding lemma, we may assume that χ is regular. Let C be the set of color classes. We will think of segments s ∈ C sometimes as a subset of edges and sometimes a subset of vertices (the endpoints and internal vertices of the segments), depending on the context. In everything that follows, we will assume that for s ≠ s′ ∈ C, we have diam(s) ≠ diam(s′). This is without loss of generality by applying arbitrarily small perturbations to T. (Alternatively, we could fix a total order on segments of equal diameter, but this would add unnecessary notation to the proof.)

For every segment s ∈ C, we define p(s) as the vertex of s which is closest to the root. For every s_{0} ∈ C and K > 0 we define a relative length function

length_{s_{0}}(s; K) = max {diam (P (p(s), x)) : x ∈ s ∩ B_{T} (p(s_{0}), K · diam(s_{0}))} ,  (19)

where we take s ∈ C, and we set length_{s_{0}}(s; K) = 0 in case the maximum is empty. In words, this is how long the segment s ∈ C “looks” from p(s_{0}), where the “view” is restricted to a ball of radius K · diam(s_{0}). It is important to note that even when s ⊈ B_{T} (p(s_{0}), K · diam(s_{0})), one might have 0 < length_{s_{0}}(s; K) ≪ K · diam(s_{0}) since T is not necessarily an ℝ-tree.

Now we define carefully a directed graph G_{C} = (C, E_{C}). The adjacency relationship on G_{C} will be the key in producing an O(ε)-reasonable coloring. We put

(s, s′) ∈ E_{C} ⟺ length_{s}(s′; K) > diam(s),  (20)

for some constant K ≥ 6 to be chosen later. Observe, in particular, that (s, s′) ∈ E_{C} ⟹ diam(s′) > diam(s). We will argue that the undirected graph Ĝ_{C} which results from ignoring the edge directions in G_{C} has its chromatic number bounded solely by a function of λ(T). We accomplish this with the following sequence of lemmas. (This step is non-trivial since Ĝ_{C} does not have bounded degree.)

Lemma 2.16. For every s ∈ C, the out-degree is bounded, i.e.

|{s′ ∈ C : (s, s′) ∈ E_{C}}| ≤ λ(T)^{O(K)}.

Proof. Fix s ∈ C. For every s′ ∈ C with (s, s′) ∈ E_{C}, let x_{s′} ∈ s′ be the node achieving the maximum in (19). If the maximum does not exist then length_{s}(s′; K) = 0, hence (s, s′) ∉ E_{C}. By definition, d_{T} (p(s), x_{s′}) ≤ K · diam(s). Furthermore, d_{T} (p(s′), x_{s′}) = length_{s}(s′; K) > diam(s). It follows that the set X_{s} = {x_{s′} : (s, s′) ∈ E_{C}} is diam(s)-separated. Since X_{s} ⊆ B_{T} (p(s), K · diam(s)), the doubling property implies that

|{s′ ∈ C : (s, s′) ∈ E_{C}}| = |X_{s}| ≤ λ(T)^{O(K)}.

For any undirected graph G = (V_{G}, E_{G}) and v ∈ V_{G}, we define N(v) to be the set of neighbors of v in G, we let deg(v) = |N(v)| and deg_{S}(v) = |N(v)∩S| for S ⊆ V_{G}. The next result is well-known.

Lemma 2.17. Let G = (V_{G}, E_{G}) be any finite, undirected graph. Let k ∈ ℕ and let π : V_{G} → {1, 2, …, n} be a permutation. We denote π_{j} = {v ∈ V_{G} : π(v) ≤ j}. If, for every j = 1, 2, …, n, we have

deg_{π_{j−1}}(π^{−1}(j)) ≤ k,

then the chromatic number of G is at most k + 1.

Proof. The proof follows by inductively coloring the elements π^{−1}(1), π^{−1}(2), …, π^{−1}(n) in order. If we have a palette of k + 1 colors, then since deg_{π_{j−1}}(π^{−1}(j)) ≤ k, we can always choose a new color for π^{−1}(j) that doesn’t conflict with any already colored vertex in π_{j−1}.

Corollary 2.18. If Ĝ_{C} is the undirected version of G_{C}, then the chromatic number of Ĝ_{C} is bounded by λ(T)^{O(K)}.

Proof. Let π : C → {1, 2, …, |C|} be any permutation for which diam(π(j)) ≥ diam(π(j + 1)) for 1 ≤ j ≤ |C| − 1 (i.e. the diameters of the segments decrease monotonically). Then combining Lemmas 2.16 and the fact that (s, s′) ∈ E_{C} ⟹ diam(s′) > diam(s) shows that for j = 1, 2, …, n,

deg_{π_{j−1}}(π^{−1}(j)) ≤ λ(T)^{O(K)}.

Applying Lemma 2.17 completes the proof.

Now let χ_{C} : C → [k] be a proper coloring of Ĝ_{C} using only k = λ(T)^{O(K)} colors. We are done as soon as we show that χ_{C} is an O(ε)-reasonable edge-coloring of T (where we consider χ_{C} as a coloring of E in the obvious way) for some choice of K ≤ (1/ε)^{O(1/ε)}.

Lemma 2.19. Suppose that for s ≠ s′ ∈ C, we have

diam(s ∩ P (u, v)), diam(s′ ∩ P (u, v)) ≥ \frac{d_{T} (u, v)}{K/2 − 1},

where u, v ∈ T. Then χ_{C}(s) ≠ χ_{C}(s′).

Proof. Assume that diam(s′) > diam(s), and let x be the bottom-most point of s′ ∩ P (u, v). Then

d_{T} (p(s), x) ≤ diam(s) + d_{T} (u, v) ≤ (1 + (K/2 − 1)) diam(s) ≤ \frac{K}{2} · diam(s).  (21)

In this case, length_{s}(s′; K) ≥ diam(P (p(s′), x)), hence if diam(P (p(s′), x)) > diam(s), we have (s, s′) ∈ E_{C}, which finishes the proof of the lemma.

So we may assume that diam(P (p(s′), x)) ≤ diam(s). We claim that in this case, length_{s}(s′; K) > diam(s) using the regularity of χ. Let y ∈ s′ be such that d_{T} (x, y) ≤ \frac{K}{2} diam(s), and for which d_{T} (p(s′), y) is maximal. If d_{T} (p(s′), y) > diam(s), then we are done since by (21), we have d_{T} (p(s), y) ≤ K · diam(s), implying length_{s}(s′; K) ≥ d_{T} (p(s′), y) > diam(s). Hence we may assume that d_{T} (p(s′), y) ≤ diam(s). In this case, since diam(s′) > diam(s), there exists an edge (y, y′) with y′ ∈ s′ and d_{T} (p(s′), y′) > \frac{K}{2} · diam(s) > 3 · diam(s). But this implies that ℓ(y, y′) > 2 · d_{T} (p(s′), y), which contradicts the regularity of χ.

It follows that length_{s}(s′; K) > diam(s), which again implies (s, s′) ∈ E_{C}.

Now fix u, v ∈ V and w = lca(u, v), and suppose that d_{T} (w, u) ≥ d_{T} (w, v). Since χ is an ε-good coloring, there exists a maximal monochromatic segment (with respect to χ) s ⊆ E for which diam(s ∩ P (w, u)) ≥ εd_{T} (w, u) ≥ (ε/2)d_{T} (u, v). Now set K = 4 (\frac{2}{ε})^{1+2/ε}. Applying Lemma 2.19, we see that for any s′ ⊆ E with χ_{C}(s) = χ_{C}(s′), we have diam(s′ ∩ P (w, v)) ≤ (\frac{ε}{2})^{1+2/ε}. But now line (5) of Lemma 2.5 implies that segments of this length can cover at most an ε/2-fraction of P (w, v) (since χ is an ε-good coloring), which is at most an ε/4-fraction of P (u, v). It follows that χ_{C} is a δ-reasonable coloring for δ = \frac{ε}{2} − \frac{ε}{4} ≥ \frac{ε}{4}, completing the proof.

3 Markov convexity and distortion lower bounds

In this section we study Markov convexity, and show how it can be used to prove several distortion lower bounds. In particular, we will discuss the connection between Markov convexity and uniform convexity in Banach spaces, and we will prove that Theorem 2.1 is optimal.

3.1 Markov convexity in Banach spaces

We start by showing that Hilbert space is Markov 2-convex. This has essentially been proved by Bourgain in [6]. We give the following proof here because the argument is extendable to the case of p ≠ 2. We refer also to [25] for another variant of Bourgain’s proof.

Lemma 3.1. For every x_{0}, …, x_{2^{m}} ∈ L_{2},

∑_{i=1}^{2^{m}} ∥x_{i} − x_{i−1}∥_{2}^{2} = \frac{∥x_{2^{m}} − x_{0}∥_{2}^{2}}{2^{m}} + ∑_{k=1}^{m} \frac{1}{2^{k}} ∑_{j=1}^{2^{m−k}} ∥x_{j2^{k}} − 2x_{(2j−1)2^{k−1}} + x_{(j−1)2^{k}}∥_{2}^{2} .  (22)

Proof. Let F_{n} be the σ-algebra of subsets of [0, 1] generated by the intervals \{I_{j}^{n} := [\frac{j−1}{2^{n}}, \frac{j}{2^{n}} ]\}_{j=1}^{2^{n}}.

Define φ : [0, 1] → L_{2} by φ ≡ x_{j} − x_{j−1} on I_{j}^{m}. Set φ_{j} = 𝔼(φ|F_{j}), where the expectation is with respect to the Lebesgue measure on [0, 1]. In other words, for every j ∈ {1, …, 2^{k}} and t ∈ I_{j}^{k}

φ_{k}(t) = \frac{1}{2^{m−k}} ∑_{ℓ=2^{m−k}(j−1)+1}^{j2^{m−k}}(x_{ℓ} − x_{ℓ−1}) = \frac{x_{j2^{m−k}} − x_{(j−1)2^{m−k}}}{2^{m−k}} .

Since the sequence {φ_{k} − φ_{k−1}}_{k=1}^{m} is a martingale difference sequence, and φ_{0} is constant, the functions φ_{0}, φ_{1} − φ_{0}, φ_{2} − φ_{1}, …, φ_{m} − φ_{m−1} are orthogonal (in the Hilbert space L_{2}(L_{2})). Thus

𝔼∥φ_{m}∥_{2}^{2} = 𝔼∥φ_{0}∥_{2}^{2} + ∑_{k=1}^{m} 𝔼∥φ_{k} − φ_{k−1}∥_{2}^{2}.

This is precisely the required identity.

We can remove the dyadic bias from (22) by averaging over shifts.

Corollary 3.2. For every x_{0}, …, x_{2^{m}} ∈ L_{2},

∑_{i=1}^{2^{m}} ∥x_{i} − x_{i−1}∥_{2}^{2} ≥ \frac{1}{2} \frac{∥x_{2^{m}} − x_{0}∥_{2}^{2}}{2^{2m}} + \frac{1}{2} ∑_{k=1}^{m} 2^{−2k} ∑_{t=1}^{2^{m}} ∥x_{t} − 2x_{t−2^{k−1}} + x_{t−2^{k}}∥_{2}^{2},

where, by convention, x_{j} = x_{0} for j ≤ 0.

Proof. First, consider the sequence of length 3 · 2^{m} − 2,

x_{0}, x_{0}, …, x_{0}, x_{0}, x_{1}, …, x_{2^{m}}, x_{2^{m}}, x_{2^{m}}, …, x_{2^{m}},

which is the original sequence with 2^{m} − 1 copies of x_{0} and x_{2^{m}} appended to the front and back, respectively. Call this sequence {y_{j}}_{j=1}^{3·2^{m}−2}. Now average the equality (22) over all 2^{m+1} contiguous subsequences of length 2^{m} + 1, i.e. {y_{i}, y_{i+1}, …, y_{i+2^{m}}} for i = 1, …, 2^{m+1}. By counting terms, this yields the desired result.

Theorem 3.3. Hilbert space is Markov 2-convex. In fact, Π_{2}(L_{2}) ≤ 4.

Proof. Let {X_{t}}_{t=0}^{∞} be a Markov chain on a state space Ω, and take f : Ω → L_{2}. By Corollary 3.2,

∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − f(X_{t−1})∥_{2}^{2} ≥ \frac{1}{2} ∑_{k=1}^{m} 2^{−2k} ∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − 2f(X_{t−2^{k−1}}) + f(X_{t−2^{k}})∥_{2}^{2}

+ \frac{1}{2} \frac{𝔼∥f(X_{0}) − f(X_{2^{m}})∥_{2}^{2}}{2^{2m}} ,

where by convention we set X_{t} = X_{0} for t ≤ 0.

Observe that for every two i.i.d. random vectors Z, Z′ ∈ L_{2}, and every constant a ∈ L_{2}, 𝔼∥Z − Z′∥_{2}^{2} ≤ 2𝔼∥Z − a∥_{2}^{2}. Thus, using the fact that conditioned on X = (X_{0}, …, X_{t−2^{k−1}}) the random vectors f(X_{t}) and f(X̃_{t}(t − 2^{k−1})) are i.i.d., we see that

𝔼∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥_{2}^{2} = 𝔼 (𝔼 (∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥_{2}^{2}|X ))
≤ 2 𝔼∥f(X_{t}) − 2f(X_{t−2^{k−1}}) + f(X_{t−2^{k}})∥_{2}^{2}.

Likewise, 𝔼∥f(X_{0}) − f(X̃_{2^{m}}(0))∥_{2}^{2} ≤ 2 𝔼∥f(X_{0}) − f(X_{2^{m}})∥_{2}^{2}. It follows that

∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − f(X_{t−1})∥_{2}^{2} ≥ \frac{1}{4} ∑_{k=1}^{m+1} 2^{−2k} ∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥_{2}^{2},

= \frac{1}{16} ∑_{k=0}^{m} 2^{−2k} ∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − f(X̃_{t}(t − 2^{k}))∥_{2}^{2},

completing the proof.

Remark 3.1. The above argument can be generalized to prove that p-convex Banach spaces are Markov p-convex. Recall that a Banach space X is said to be p-convex with constant K (see [3]) if for every x, y ∈ X,

2∥x∥^{p} + \frac{2}{K^{p}} ∥y∥^{p} ≤ ∥x + y∥^{p} + ∥x − y∥^{p}.

The least such constant K is denoted K_{p}(X).

We claim that for every Banach space X,

Π_{p}(X) ≤ 2^{(p−1)/p} (2^{p−1} − 1)^{1/p} · K_{p}(X) ≤ 4K_{p}(X).

Indeed, repeating the argument of Lemma 3.1, we replace the use of orthogonality by Pisier’s inequality [33] to get that (see the argument in [2] for the constant used below),

(2^{p−1} − 1)[K_{p}(X)]^{p}𝔼∥φ_{m}∥_{X}^{p} ≥ 𝔼∥φ_{0}∥_{X}^{p} + ∑_{k=1}^{m} 𝔼∥φ_{k} − φ_{k−1}∥_{X}^{p}.

As in the proof of Theorem 3.3 (and using the notation there) this shows that

(2^{p−1} − 1)[K_{p}(X)^{p}] ∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − f(X_{t−1})∥_{X}^{p} ≥

\frac{1}{2} ∑_{k=1}^{m} 2^{−pk} ∑_{t=1}^{2^{m}} 𝔼∥f(X_{t}) − 2f(X_{t−2^{k−1}}) + f(X_{t−2^{k}})∥_{X}^{p} + \frac{1}{2} \frac{𝔼∥f(X_{0}) − f(X_{2^{m}})∥_{X}^{p}}{2^{pm}} .

Since for every two i.i.d. random vectors Z, Z′ ∈ X, and every constant a ∈ X, we have that 𝔼∥Z − Z′∥_{X}^{p} ≤ 2^{p−1}𝔼∥Z − a∥_{X}^{p} (this fact follows from a straightforward interpolation argument), we conclude exactly as in the proof of Theorem 3.3.

We mention some partial converses to Remark 3.1.

Corollary 3.4. Let X be an infinite dimensional Banach space. Then Π_{p}(X) < ∞ implies that X is superreflexive and has cotype q for every q > p.

Proof. Let q_{X} = inf{q : X has cotype q}. By the Maurey-Pisier [29] theorem, X contains copies of ℓ_{q_{X}}^{n} with distortion uniformly bounded in n. By Bourgain’s embedding of trees into ℓ_{q_{X}} [6], this implies that c_{X}(B_{m}) = O ((log m)^{1/q_{X}} ). From Bourgain’s lower bound [6], or alternatively Claim 3.7 below, we deduce that q_{X} ≤ p, as required. The fact that X is superreflexive follows from Bourgain’s characterization of superreflexivity [6].

Corollary 3.5. Let X be a Banach lattice with Π_{p}(X) < ∞. Then for every q > p, X admits a q-convex equivalent norm.

Proof. This is a direct consequence of a theorem of Figiel [13] (see [22], page 100) which says that a Banach lattice with cotype q and non-trivial type can be renormed to be q-convex (X has non-trivial type since it is superreflexive).

3.2 Distortion lower bounds

We can now use the discrepancy between Π_{p}(X) and Π_{p}(Y) to prove distortion lower bounds for embeddings between the two spaces.

Lemma 3.6. Let (X, d_{X}), (Y, d_{Y}) be metric spaces, then for every p < ∞, we have

c_{Y} (X) ≥ \frac{Π_{p}(X)}{Π_{p}(Y)}.

Proof. Fix Π > Π_{p}(Y). Let g : X → Y be a bi-Lipschitz map, let {X_{t}}_{t=0}^{∞} be a Markov chain with state space Ω, and let f : Ω → X. Then

∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [d_{X} (f (X_{t}) , f(X̃_{t}(t − 2^{k})))^{p}]}{2^{kp}}

≤ ∥g^{−1}∥_{Lip}^{p} · ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [d_{Y} (g(f (X_{t})), g(f(X̃_{t}(t − 2^{k}))))^{p}]}{2^{kp}}

≤ ∥g^{−1}∥_{Lip}^{p} · Π^{p} · ∑_{t=1}^{2^{m}} 𝔼[d_{Y} (g(f(X_{t})), g(f(X_{t−1})))^{p}]

≤ ∥g∥_{Lip}^{p} · ∥g^{−1}∥_{Lip}^{p} · Π^{p} · ∑_{t=1}^{2^{m}} 𝔼[d_{Y} (f(X_{t}), f(X_{t−1}))^{p}].

It follows that Π_{p}(X) ≤ c_{Y} (X) · Π_{p}(Y), as required.

As a warm up to the more involved lower bounds that will follow, we show how Markov convexity can be used to prove Bourgain’s theorem for complete binary trees.

Claim 3.7. For every m ∈ ℕ, we have Π_{p}(B_{2^{m}}) ≥ 2^{1− \frac{2}{p}} · m^{\frac{1}{p}} .

Proof. Let \{X_{t}\}_{t=0}^{∞} be the forward random walk on B_{2^{m}} (which goes left/right with probability \frac{1}{2}), starting from the root, with the leaves as absorbing states. Then

∑_{t=1}^{2^{m}} 𝔼 [d_{B_{2^{m}}} (X_{t}, X_{t−1})^{p}] ≤ 2^{m}.

Moreover, in the forward random walk, after splitting at time r ≤ 2^{m} with probability at least \frac{1}{2} two independent walks will accumulate distance which is at least twice the number of steps (until a leaf is encountered). Thus

∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [d_{B_{2^{m}}} (X_{t}, X̃_{t} (t − 2^{k}))^{p}]}{2^{kp}} ≥ ∑_{k=0}^{m} ∑_{t=1}^{2^{m}−2^{k}} \frac{1}{2^{kp}} · \frac{1}{2} · 2^{(k+1)p} ≥ 2^{p−2} · m · 2^{m}.

The claim follows.

Since L_{p} is Markov max{2, p}-convex for every p > 1, combining Claim 3.7 with Lemma 3.6 recovers Bourgain’s result [6], i.e. for every p > 1, we have c_{p}(B_{k}) ≥ Ω ((log k)^{min\{ \frac{1}{2} , \frac{1}{p} \}}).

Simple random walks with positive speed. In fact, the proof of Claim 3.7 applies in more general situations where a random walk has positive speed. We consider some examples.

Let G = (V, E) be an infinite, vertex-transitive graph of bounded degree. Let {X_{t}}_{t=0}^{∞} be a simple random walk on G starting from an arbitrary vertex. Denote by d_{G} the shortest path metric on G. One defines the speed of the random walk as the limit

lim_{t→∞} \frac{𝔼 d_{G}(X_{0}, X_{t})}{t}.

Subadditivity implies that the limit above always exists.

Lemma 3.8. If the speed of the simple random walk on a vertex-transitive graph G is at least s > 0, then Π_{p}(B_{G}(R)) = Ω ((log R)^{1/p}), where B_{G}(R) denotes the ball of radius R in G. In particular for every p > 1,

c_{p}(B_{G}(R)) = Ω ((log R)^{min\{ \frac{1}{2} , \frac{1}{p} \}}) .

Proof. The proof is similar to that of Claim 3.7. One simply observes that for two independent simple random walks X_{t}, X̃_{t} started at the same point, we have

lim_{t→∞} \frac{𝔼 d_{G}(X_{t}, X̃_{t})}{t} = lim_{t→∞} \frac{𝔼 d_{G}(X_{0}, X_{2t})}{t} ≥ 2s > 0.

In particular, for t large enough, with constant probability we have d_{G}(X_{t}, X̃_{t}) = Ω(t).

As an application, consider the lamplighter group over ℤ^{d}. This is a group with elements (f, x), where x ∈ ℤ^{d}, and f : ℤ^{d} → {0, 1} with f(y) = 0 for all but finitely many y ∈ ℤ^{d}. Traditionally, one imagines a lamp placed at every element of ℤ^{d}, where each lamp can either be on or off. In the pair (f, x), f denotes the settings of all the lamps, and x denotes the position of the lamplighter. Accordingly, the generating set consists of two types of moves.

1. The lamplighter can move to an adjacent vertex in ℤ^{d}, i.e. (f, x) ↦ (f, x′) where x′ is adjacent to x in the standard Cayley graph of ℤ^{d} or

2. The lamplighter can turn on/off the lamp at x, i.e. (f, x) ↦ (f′, x) where f′(y) = f(y) for y ≠ x and f′(x) = 1 − f(x).

We will use L(ℤ^{d}) to denote the associated group as well as the Cayley graph with the described generators. A result of Kaĭmanovich and Vershik [19] shows that the simple random walk on L(ℤ^{d}) has positive speed for d > 2. Using Remark 3.1 and Lemma 3.8, we conclude:

Corollary 3.9. For d > 2, the word metric on L(ℤ^{d}) does not embed into any p-convex Banach space. In particular, if B_{L(ℤ^{d})}(R) denotes a ball of radius R, then for p > 1,

c_{p} (B_{L(ℤ^{d})}(R)) ≥ Ω ((log R)^{min\{ \frac{1}{2} , \frac{1}{p} \}}) .

We remark that, by a theorem of Varopoulos [36], the simple random walk on the Cayley graph of a finitely-generated group has positive speed if and only if there exists a bounded, non-constant, harmonic function on the graph.

Finally, we consider the finite lamplighter groups over ℤ_{N} = ℤ/(Nℤ), which we denote by L(ℤ_{N}). In this case, the simple random walk on L(ℤ_{N}) does not have positive speed, but it is still possible to prove a distortion lower bound because the Markov chains in the definition of Markov convexity need not be reversible. In particular, consider the chain {X_{t}}_{t=0}^{∞} defined as follows. X_{0} = (f, 0) where f ≡ 0, i.e. all lamps are turned off. If X_{t} = (f, i), then with probability \frac{1}{2}, we put X_{t+1} = (f, i+1), and with probability \frac{1}{2} we put X_{t+1} = (f′, i+1) where f′(i+1) = 1−f(i+1). Arguing essentially exactly as in Claim 3.7 for times t ≤ N, we have the following.

Proposition 3.10. For every p < ∞, we have Π_{p}(L(ℤ_{N})) ≥ Ω ((log N)^{\frac{1}{p}} ). In particular,

c_{p}(L(ℤ_{N})) ≥ Ω ((log N)^{min\{ \frac{1}{2} , \frac{1}{p} \}}).

Proposition 3.10 can also be proved by exhibiting an embedding of a complete binary tree of depth Θ(N) into L(ℤ_{N})—see [26].

3.3 Weak prototypes and Markov convexity

In this section we study the Markov convexity properties of a special class of trees called weak prototypes. These trees will play a central role in Section 4, where Theorem 1.4 is proved. We begin with some definitions (we continue using here the notation of Section 2.1).

In what follows, by a path metric P = (u_{1}, …, u_{m}) we simply mean a graph theoretical path from u_{1} to u_{m} with edges (u_{1}, u_{2}), (u_{2}, u_{3}), …, (u_{m−1}, u_{m}) and edge weights {ℓ(u_{j}, u_{j+1})}_{j=1}^{m−1} ⊆ [0, ∞). The length of P, denoted ℓ(P), is given by ℓ(P) = ∑_{j=1}^{m−1} ℓ(u_{j}, u_{j+1}). Given a monotone path P in T, and a set of vertices (v_{1}, …, v_{m}) on P, ordered down the tree and not necessarily containing all the vertices of T lying on P, we will call the path metric on (v_{1}, …, v_{m}) with the edge weights {d_{T} (v_{j}, v_{j+1})}_{j=1}^{m−1}, the path metric induced by T on (v_{1}, …, v_{m}).

Given a path metric P = (u_{1}, …, u_{m}) and ε, δ ∈ (0, 1) we shall say the path P is (ε, δ)-weak if at least an ε-fraction of the length of P is composed of edges of length at most δℓ(P), i.e.

∑_{\begin{matrix}j∈\{1,...,m−1\} \\ ℓ(u_{j},u_{j+1})≤δℓ(P) \end{matrix}} ℓ(u_{j}, u_{j+1}) ≥ εℓ(P) = ε ∑_{j=1}^{m−1} ℓ(u_{j}, u_{j+1}).

A monotone path P (u, v) in T will be called degree-2 (ε, δ)-weak if the following condition holds true. Let (u_{1}, …, u_{m}) be the vertices of T on P, ordered down the tree, who have at least two children in T. Then we require that the path metric induced by T on (u, u_{1}, …, u_{m}, v) is (ε, δ)-weak. In other words, call a monotone path P in T a strait if every vertex on P has exactly one child, except possibly for the initial and final vertices. Then P (u, v) is degree-2 (ε, δ)-weak if at least an ε-fraction of the length of P (u, v) is composed of maximal straits of length at most δd_{T} (u, v).

Definition 3.11. Fix ε, δ, R > 0. A tree T = (V, E) with edge lengths ℓ : E → (0, ∞) is called an (ε, δ)-weak prototype with height ratio R if the following conditions are satisfied.

• Every non-leaf vertex of T has exactly one or two children.

• Every root-leaf path of T is degree-2 (ε, δ)-weak.

• If h is the length of the shortest root-leaf path in T and h′ is the length of the longest root-leaf path in T, then h′/h ≤ R.

3.3.1 Markov convexity for unweighted weak prototypes

First, we will prove a lower bound on the Markov convexity constants of a special class of unweighted weak prototypes. Later, we will show that every weak prototype can be approximated by a weak prototype satisfying these conditions.

Theorem 3.12. Let (T, d_{T}) be an unweighted (ε, δ)-weak prototype with height ratio 1 and height 2^{m} for some m ∈ ℕ. Then for every p ≥ 1, we have

Π_{p}(T) ≥ (\frac{ε}{4} [log_{2}(ε/δ) − 4])^{1/p} .

Proof. Let r be the root of T. Let {X_{t}}_{t=0}^{∞} be the Markov chain on T defined as follows. Initially, X_{0} = r. If X_{t} is a leaf node, then X_{t+1} = X_{t}, and otherwise X_{t+1} is a uniformly random child of X_{t}.

First, we have d_{T} (X_{t−1}, X_{t}) ≤ 1 for every t ≥ 1. Thus it suffices to show that

\frac{1}{2^{m}} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [d_{T} (X_{t}, X̃_{t}(t − 2^{k}))]^{p}}{2^{kp}} ≥ \frac{ε}{4} [log_{2} (\frac{ε}{δ}) − 4] .

Recall that a monotone path P in T is a strait if every node of P has exactly one child, except possibly for the initial and final nodes. Additionally, say that a node v ∈ T is a branch point if v has at least two children. Clearly the edges of every root-leaf path partition into maximal straights with branch points at the ends (except for the root and leaves). Let B_{k}(t) be the event that the set {X_{t}, X_{t+1}, …, X_{t+2^{k−1}}} contains a branch point. Observe that whenever 2^{k−1} ≥ δ2^{m}, we have

∑_{t=0}^{2^{m}−1} Pr[B_{k}(t)] ≥ ∑_{t=0}^{2^{m}−1} Pr [X_{t} falls in a maximal strait of length at most 2^{k−1}] ≥ ε2^{m}, (23)

since every root-leaf path of T is degree-2 (ε, δ)-weak. Furthermore, if k ≤ m, and t ≤ 2^{m} − 2^{k}, then

B_{k}(t) occurs ⟹ Pr [d_{T} (X_{t+2^{k}}, X̃_{t+2^{k}}(t)) ≥ 2^{k}] ≥ \frac{1}{2},  (24)

since upon hitting a branch point, the two chains will diverge with probability at least \frac{1}{2} for at least 2^{k−1} additional steps.

We conclude that when 2^{k−1} ≥ δ2^{m} and k ≤ m,

∑_{t=1}^{2^{m}} 𝔼 [d (X_{t}, X̃_{t}(t − 2^{k}))]^{p} ≥ ∑_{t=0}^{2^{m}−2^{k}} 𝔼 [d (X_{t+2^{k}}, X̃_{t+2^{k}}(t))]^{p}

≥ ∑_{t=0}^{2^{m}−2^{k}} \frac{1}{2} · 2^{kp} · Pr[B_{k}(t)]  (25)
≥ 2^{kp−1} · (ε2^{m} − 2^{k}) ,  (26)

where in (25) we used (24), and in (26) we used (23) along with a correction term for boundary values of k. Therefore,

\frac{1}{2^{m}} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [d_{T} (X_{t}, X̃_{t}(t − 2^{k}))]^{p}}{2^{kp}} ≥ 2^{−(m+1)} ∑_{k≥1+log_{2}(δ2^{m})}^{m} max \{0, ε2^{m} − 2^{k}\}
≥ \frac{ε}{4} [log (\frac{ε}{δ}) − 4] .

The proof of Theorem 3.12 is complete.

3.3.2 Distortion bounds for weak prototypes

In this section, we show how pass from a finite tree T to a more well-behaved tree T̃ such that c_{p}(T̃) = O(1) · c_{p}(T) for every p ∈ [1, ∞). We use this transformation to prove distortion lower bounds for arbitrary weak prototypes.

Lemma 3.13. Let (T, d_{T}) be a finite, graph-theoretic metric tree, and let T_{ℝ} be the ℝ-tree that results from replacing every edge of e ∈ E(T) by a closed interval whose length is length(e). Then for every p ∈ [1, ∞), we have c_{p}(T_{ℝ}) ≤ 5c_{p}(T).

Proof. Fix a root r of T (and, in particular, an orientation of the edges). Let f : T → L_{p} be an embedding of T. Let {β_{uv}}_{uv∈E(T)} ⊆ L_{p} be a system of disjointly supported unit vectors each of whose support is also disjoint from the support of Im(f). Denote a point x ∈ T_{ℝ} by x = (u, v, η), where uv ∈ E(T), we have d_{T} (r, u) ≤ d_{T} (r, x) ≤ d_{T} (r, v), and d_{T} (x, u) = η · d_{T} (u, v) for η ∈ [0, 1]. Assume that ∥f∥_{Lip} = 1. We define an embedding g : T_{ℝ} → L_{p} by

g (u, v, η) = (1 − η)f(u) + ηf(v) + η d_{T} (u, v)β_{uv}.

Fix (u, v, η), (u′, v′, η′) ∈ T_{ℝ}. If u′ is not a descendant of u or vice-versa then

d_{T_{ℝ}} ((u, v, η), (u′, v′, η′)) = ηd_{T} (u, v) + η′d_{T} (u′, v′) + d_{T} (u, u′).

Thus

∥g(u, v, η) − g(u′, v′, η′)∥_{p}
≤ ∥g(u, v, η) − g(u, v, 0)∥_{p} + ∥g(u, v, 0) − g(u′, v′, 0)∥_{p} + ∥g(u′, v′, 0) − g(u′, v′, η′)∥_{p}
= ∥η(f(v) − f(u)) + ηd_{T} (u, v)β_{uv}∥_{p} + ∥(1 − η)(f(u) − f(u′))∥_{p}
+ ∥η′(f(v′) − f(u′)) + η′d_{T} (u′, v′)β_{u′v′} ∥_{p}
= η (∥f(u) − f(v)∥_{p}^{p} + d_{T} (u, v)^{p})^{1/p} + (1 − η)∥f(u) − f(u′)∥_{p}
+η′ (∥f(u′) − f(v′)∥_{p}^{p} + d_{T} (u′, v′)^{p})^{1/p}
≤ 2^{1/p}ηd_{T} (u, v) + 2^{1/p}η′d_{T} (u′, v′) + (1 − η)d_{T} (u, u′)
≤ 2^{1/p} · d_{T_{ℝ}} ((u, v, η), (u′, v′, η′)) .

If u′ is a strict descendant of u then

d_{T_{ℝ}} ((u, v, η), (u′, v′, η′)) = (1 − η)d_{T} (u, v) + η′d_{T} (u′, v′) + d_{T} (v, u′),  (27)

and a similar reasoning shows that ∥g(u, v, η) − g(u′, v′, η′)∥_{p} ≤ 2^{1/p} · d_{T_{ℝ}} ((u, v, η), (u′, v′, η′)). The case of u = u′ is even simpler, so we have shown that ∥g∥_{Lip} ≤ 2^{1/p}∥f∥_{Lip}.

On the other hand, we will now show that ∥g^{−1}∥_{Lip} ≤ \frac{5}{2^{1/p}}. Assume first of all that u′ is not a descendant of u or vice-versa. Then

∥g(u, v, η) − g(u′, v′, η′)∥_{p}^{p}
≥ [η d_{T} (u, v)]^{p} + [η′d_{T} (u′, v′)]^{p} + |∥f(u) − f(u′)∥_{p} − η∥f(u) − f(v)∥_{p} − η′∥f(u′) − f(v′)∥_{p}|^{p}
≥ [η d_{T} (u, v)]^{p} + [η′d_{T} (u′, v′)]^{p} + |\frac{d_{T} (u, u′)}{∥f^{−1}∥_{Lip}} − η d_{T} (u, v) − η′d_{T} (u′, v′)|^{p}
≥ \frac{5}{2} [\frac{1}{5} (\frac{d_{T} (u, u′)}{∥f^{−1}∥_{Lip}} + η d_{T} (u, v) + η′d_{T} (u′, v′))]^{p}  (28)
≥ 2 [\frac{1}{5} (\frac{d_{T_{ℝ}} ((u, v, η), (u′, v′, η′))}{∥f^{−1}∥_{Lip}})]^{p} ,

Where in (28) we used the convexity of the function a ↦ |a|^{p}, which implies that for all a, b, c ∈ ℝ we have |a|^{p} + |b|^{p} + |c|^{p} ≥ \frac{5}{2} |\frac{2}{5}a + \frac{2}{5}b + \frac{1}{5}c|^{p}.

If u′ is a strict descendant of u then d_{T_{ℝ}} ((u, v, η), (u′, v′, η′)) is given by (27). Denote this distance by D, and for the sake of simplicity write L = ∥f^{−1}∥_{Lip}. Since

∥g(u, v, η) − g(u′, v′, η′)∥_{p}^{p} ≥ [η d_{T} (u, v)]^{p} + [η′d_{T} (u′, v′)]^{p} ≥ 2^{1−p} [η d_{T} (u, v) + η′d_{T} (u′, v′)]^{p} ,

we may assume that η d_{T} (u, v) + η′d_{T} (u′, v′) < \frac{2D}{5L}. In this case

∥g(u, v, η) − g(u′, v′, η′)∥_{p} ≥ ∥(1 − η)f(u) + ηf(v) − (1 − η′)f(u′) − η′f(v′)∥_{p}
≥ ∥f(u) − f(u′)∥_{p} − η∥f(u) − f(v)∥_{p} − η′∥f(u′) − f(v′)∥_{p}
≥ \frac{d_{T} (u, u′)}{L} − ηd_{T} (u, v) − η′d_{T} (u′, v′)
≥ \frac{D − η′d_{T} (u′, v′)}{L} − \frac{2D}{5L}
≥ \frac{D}{L} − \frac{D}{5L^{2}} − \frac{2D}{5L}
≥ \frac{D}{5L}.

The remaining case is when u = u′ and v = v′. But then ∥g(u, v, η) − g(u′, v′, η′)∥_{p} = |η − η′| · ∥f(u) − f(v)∥_{p}, and the required lower bound is trivial.

We have thus proved that ∥g∥_{Lip} · ∥g^{−1}∥_{Lip} ≤ 5∥f∥_{Lip} · ∥f^{−1}∥_{Lip}, as required.

Remark 3.2. The above lemma does not hold if we allow “Steiner” nodes in the tree T. To observe this, consider the subset L ⊆ B_{m} of leaves of a complete binary tree of height m, and let r be the root of B_{m}. Then it is not difficult to see that c_{2}(L ∪ {r}) ≤ O(1) (independent of m), while c_{2}(B_{m}) → ∞ by Bourgain’s theorem for B_{m} [6].

We now replace any weak prototype by an “equivalent” prototype with height ratio 1.

Lemma 3.14. Let (T, d_{T}) be any finite metric tree. Then there exists a finite, unweighted metric tree (T̃, dT̃) with height 2^{m} for some m ∈ ℕ such that c_{p}(T̃) ≤ O(1) · c_{p}(T) for any p ∈ [1, ∞). Furthermore, if T is an (ε, δ)-weak prototype with height ratio R, then T̃ is an unweighted (\frac{ε}{2R}, δ)- weak prototype with height ratio 1.

Proof. Fix a root r of T. Since T is finite, by rescaling and paying an arbitrarily small distortion, we may assume that all edge lengths are integral. For every node x ∈ T, Let m = ⌈log_{2} max_{x∈T} d_{T} (x, r)⌉. We now define a tree T′ as follows. For every leaf ℓ ∈ T, define a new node ℓ̃, and create a new edge (ℓ, ℓ̃) of length 2^{m} − d_{T} (r, ℓ). Thus the length of every root-leaf path in T′ is exactly 2^{m}. To see that c_{p}(T′) = Θ(1) · c_{p}(T), let f : T → L_{p} be an embedding of T, and let {β_{ℓ}} ⊆ L_{p} be a system of disjointly supported vectors each of whose support is disjoint to Im(f). One can extend the embedding by defining f(ℓ̃) = f(ℓ) + d_{T′}(ℓ, ℓ̃) · β_{ℓ} so that c_{p}(T′) ≤ O(1) · c_{p}(T). Observe that if T had height ratio R, then the length of any root-leaf path in T′ has increased by at most a factor 2R over its previous length in T.

We pass from T′ to T′_{ℝ} using Lemma 3.13, and then to T̃ by simply taking the vertex set of T̃ to be V (T̃) = {v ∈ T′ : d_{T′}(v, r) ∈ ℕ}. We define dT̃ as the unweighted shortest path metric on T. then (T̃, dT̃) embeds isometrically into T′_{ℝ}. Hence c_{p}(T̃) = Θ(1) · c_{p}(T′_{ℝ}) = Θ(1) · c_{p}(T′) = Θ(1) · c_{p}(T). Furthermore, every root-leaf path in T̃ has length precisely 2^{m}. Finally, observe that if T was (ε, δ)-weak with height ratio R, then T̃ is an unweighted (ε/(2R), δ)-weak prototype (because some root-leaf path from T might have increased by a factor of at most 2R) with height ratio 1.

The following corollary follows from Theorem 3.12 and Lemma 3.14.

Corollary 3.15. Let (T, d_{T}) be an (ε, δ)-weak prototype with height ratio R, then for any p > 1,

c_{p}(T, d_{T}) ≥ Ω(1) · c_{p}(T̃, dT̃) ≥ Ω(1) · Π_{q}(T̃, dT̃) ≥ Ω(1) · (\frac{ε}{R} log (\frac{ε}{δR}))^{1/q} ,

where q = max{2, p} and T̃ is the associated unweighted prototype from Lemma 3.14.

The corollary follows by applying Theorem 3.12 to T̃ and using the relationship between Markov convexity and distortion from Lemma 3.6, along with the known Markov convexity of L_{p} spaces (Remark 3.1).

3.3.3 The Cantor trees

Recall that in Theorem 2.1, we showed that for any tree T and p ≥ 1, we have, for every c > 1,

c_{p}(T) ≤ O(1) (\frac{c}{c − 1} · ℬ_{T} (c)) ^{min\{ \frac{1}{p} , \frac{1}{2} \}} .

Here, we will show that this dependence on ℬ_{T} (c) cannot be improved by exhibiting a family {C_{i}}_{i=0}^{∞} of metric trees with |C_{i}| → ∞ and such that for any fixed c > 1,

c_{p}(C_{i}) ≥ Ω(1) · Π_{max\{2,p\}}(C_{i}) ≥ Ω(1) · ℬ_{C_{i}}(c)^{min\{ \frac{1}{p} , \frac{1}{2} \}}  (29)

Let T be a rooted (unweighted) graph-theoretic tree. For any root leaf path P = {v_{0}, v_{1}, …, v_{m}}, we define the downward degree sequence d_{↓}(P) = {d_{↓}(v_{0}), d_{↓}(v_{1}), …, d_{↓}(v_{m})} where d_{↓}(v) is the number of children of v in T. We will say that T is a spherically symmetric tree (SST) if for any pair of root-leaf paths P, P′ we have d_{↓}(P) = d_{↓}(P′). Clearly any such tree can be completely specified by giving the degree sequence of a root-leaf path (see Figure 4).

Figure 4: A downward degree sequence and the corresponding SST.

Definition of the Cantor trees. We now describe a family of downward degree sequences inductively. For two sequences S, S′ we define S ⊗ S′ as their concatenation. For every i ∈ ℕ, we use ones(i) = ⊗^{i}{1} to denote a sequence of i ones. Now define S_{0} = {2} and inductively

S_{i+1} = S_{i} ⊗ ones(2^{i} − 1) ⊗ S_{i}.

Hence the first few sequences are {{2}, {22}, {22 1 22}, {22122 111 22122}, …}. To make these proper downward degree sequences, we define S̃_{i} to be S_{i} except with the last element changed from 2 to 0. Finally, we let C_{i} be the unique SST with downward degree sequence S̃_{i}. We call these Cantor trees because the patterns of 2’s resemble finite approximations to the middle-thirds Cantor set. It is clear that length(S_{i}) = 2·length(S_{i−1})+2^{i−1} −1 = i·2^{i−1} +1, and that log log |C_{i}| = Θ(i). The next two lemmas are somewhat less obvious.

Lemma 3.16. For every i ≥ 1, the tree C_{i} is a (\frac{1}{2}, 2^{−i/3})-weak prototype.

Proof. We need to show that every root-leaf path in C_{i} is degree-2 (\frac{1}{2}, 2^{−i/3})-weak. Fix any such path P. It is easy to see that the maximal straits in P are given by consecutive sequences of 1’s in the downward degree sequence of C_{i}: A sequence of k consecutive 1’s refers to a strait of length k + 1. Therefore for every j ≤ i − 1, there are 2^{i−1−j} disjoint maximal straits of length 2^{j} in P. The question becomes how small we need to choose m before

\frac{1}{2} height(C_{i}) = \frac{1}{2} (i · 2^{i−1} + 2) ≤ ∑_{j=m}^{i−1} 2^{i−1−j} · 2^{j} = 2^{i−1}(i − m).

Clearly we must have m < i/2, hence C_{i} is a (\frac{1}{2}, δ)-weak prototype for

δ = \frac{2^{i/2}}{i · 2^{i−1} + 1} ≤ 2^{−i/3}.

Combining this with Theorem 3.12 yields the following.

Corollary 3.17. For every p < ∞, Π_{p}(C_{i}) ≥ Ω (i^{1/p}).

The following claim completes the proof of (29).

Claim 3.18. For every fixed c > 1, ℬ_{C_{i}}(c) ≤ O(i) as i → ∞.

Proof. The idea of the proof is simple: If the edges of B_{m} are mapped far apart in C_{i}, then we can use the diameter of C_{i} to upper bound the size of m. Otherwise, if the edges are mapped close together, then essentially the entire image of B_{m} must lie inside some copy of C_{i−1} in C_{i}. This is because there is a “buffer” of length 2^{i−1} between copies of C_{i−1} in C_{i} which contains no branch points. An edge of B_{m} must stretch over this buffer if the image of B_{m} spans multiple copies of C_{i−1}.

For our induction, it will be easier to bound ℬC̃_{i}(c) for a slightly different family of trees C̃_{i}. Let C̃_{i} be the tree C_{i} with the following two additions:

1. We append a path H_{i} of length 2^{i−2} to the root of C_{i}.

2. We append a path of length 2^{i−2} to every leaf of C_{i}. We will use L = {L_{i}} to refer to this family of paths.

Clearly ℬ_{C_{i}}(c) ≤ ℬC̃_{i}(c).

We may assume that i ≥ 1 is sufficiently large with respect to c. Let f : B_{m} → C̃_{i} be a bi-Lipschitz embedding of B_{m} into C̃_{i} with distortion c = ∥f∥_{Lip} · ∥f^{−1}∥_{Lip}. Assume, for the sake of contradiction, that m ≥ 256 i · c log(c + 1).

Clearly

diam(C̃_{i}) ≥ max_{u,v∈B_{m}} dC̃_{i}(f(u), f(v)) ≥ \frac{2m}{∥f^{−1}∥_{Lip}} ≥ \frac{2m∥f∥_{Lip}}{c} .

Since diam(C̃_{i}) ≤ i · 2^{i+2}, we conclude that

max_{uv∈E(B_{m})} dC̃_{i}(f(u), f(v)) = ∥f∥_{Lip} ≤ \frac{i · 2^{i+2} · c}{m} ≤ \frac{2^{i−6}}{log(c + 1)},  (30)

where E(B_{m}) is the set of edges in B_{m}.

We will now show that (30) implies that f(B_{m}) is contained completely inside an isometric copy of C̃_{i−1}. By induction, this will be a contradiction and finish the proof. Let us consider a “top-down” decomposition of C̃_{i} into disjoint pieces. From the root downward, we see H_{i}, then a copy of C_{i}, then the family of paths L. If we also break C_{i} into constituent pieces, we see:

1. H_{i},

2. a copy C_{i−1},

3. a family of paths P of length 2^{i−1} connected to the leaves of (2),

4. copies of C_{i−1} connected to every endpoint of the paths from (3),

5. the family of paths L connected to the leaves of the copies of C_{i} from (4).

We now define a family of disjoint sub-trees of C̃_{i} each of which is an isometric copy of C̃_{i−1}. The first copy C̃_{i−1}^{(0)} consists of the bottom 2^{i−3} nodes of H_{i}, the copy of C_{i−1} from (2) above, and the top 2^{i−3} nodes of each path p ∈ P (from (3)). The other copies are indexed by paths p ∈ P. For each such path, we construct C̃_{i−1}^{(p)} using the bottom 2^{i−3} nodes of p, the copy of C_{i−1} from (4) connected to the bottom of p, and the top 2^{i−3} nodes of each path from L connected to this copy of C_{i−1}.

We claim that there exists some j ∈ {0} ∪ P for which f(B_{m}) ⊆ C̃_{i−1}^{(j)}. We now prove the most difficult case; the other cases are similar. Suppose, for the sake of contradiction, there exist x, y ∈ B_{m} for which f(x) ∈ C̃_{i−1}^{(0)} and f(y) ∈ C̃_{i−1}^{(p)} for some p ∈ P. By (30), every edge of B_{m} has length at most 2^{i−6}, hence there must be some node z ∈ B_{m} for which f(z) lies in the middle 2^{i−3} nodes of p. In particular, |BC̃_{i}(f(z), r)| ≤ 2r + 1 for every r ≤ 2^{i−3}, since BC̃_{i}(f(z), 2^{i−3}) ⊆ p. Furthermore, |f(B_{m}) ∩ BC̃_{i}(f(z), r)| ≤ (2r + 1)∥f^{−1}∥_{Lip}. On the other hand, |B_{B_{m}}(z, r′)| ≥ 2^{r′/2} for r′ ≤ m.

But we have

f (B_{B_{m}} (z, \frac{r}{∥f∥_{Lip}} )) ⊆ BC̃_{i}(f(z), r).

Let r = min{2ic ∥f∥_{Lip}, 2^{i−3}}. Since, in particular r ≤ m∥f∥_{Lip}, the above considerations yield

2^{\frac{r}{2∥f∥_{Lip}}} ≤ (2r + 1)∥f^{−1}∥_{Lip} = \frac{(2r + 1)c}{∥f∥_{Lip}} ≤ \frac{4rc}{∥f∥_{Lip}} .  (31)

Observe that the inequality 2^{B} ≥ 8Bc hold as long as B ≥ 10 log(c + 1) and c ≥ 1, but it is easy to check that for i ≥ 10, we have \frac{r}{2∥f∥_{Lip}} ≥ 10 log(c + 1) (using (30)), yielding a contradiction. This completes the proof.

Remark 3.3. Observe that the two point space A = {x, y} with, say, d(x, y) = 1 is a tree metric for which Π_{p}(A) = O(1) for every p < ∞. On the other hand, it is easy to see that Π_{p}([0, 1]) = ∞ for every p < 2, thus in general Π_{p}(T_{ℝ}) ≉ Π_{p}(T) for p < 2. For p ≥ 2, the relationship is less clear, though we suspect that a similar phenomenon holds in this case. A possible example for which Π_{2}(T_{ℝ}^{(i)}) ≉ Π_{2}(T^{(i)}) is when T^{(i)} is the Cantor tree C_{i} with every maximal strait replaced by a single long edge. Using techniques similar to Lemma 3.18, one might show that Π_{2}(T^{(i)}) = O(1) as i → ∞ while Π_{2}(T_{ℝ}^{(i)}) ≈ Π_{2}(C_{i}) → ∞. We do not pursue this line of reasoning further in the present work.

4 Characterizing the distortion: strong colorings and Markov convexity

In this section we will continue to use the notation of Section 2.1. Moreover, unless explicitly stated otherwise, all paths will be assumed to be monotone. Many of the concepts and definitions used in this section were introduced in Section 3.3, so we suggest that the reader will be familiar with Section 3.3 before reading the present section.

The following result, which contains Theorem 1.4, is the main theorem of this section:

Theorem 4.1 (The L_{p} distortion of trees). For 1 < p < ∞ and every metric tree T = (V, E),

c_{p}(T) = Θ (Π_{max\{p,2\}}(T_{ℝ})) = Θ ([log (\frac{2}{δ^{∗}(T)})]^{min\{ \frac{1}{p} , \frac{1}{2} \}}) ,

where the implied constants may depend only on p.

Before proving Theorem 4.1 we make some observations. By Lemma 3.6 for every q > 0 and every two metric spaces (X, d_{X}) and (Y, d_{Y}), c_{Y} (X) ≥ \frac{Π_{q}(X)}{Π_{q}(Y)}. Since L_{p} is max\{p, 2\} uniformly convex, Remark 3.1 implies that Π_{max{p,2}}(L_{p}) < ∞. This observation, together with Theorem 2.6 and Lemma 3.13, implies that

Ω (Π_{max\{p,2\}}(T_{ℝ})) ≤ \frac{1}{5}c_{p}(T_{ℝ}) ≤ c_{p}(T) ≤ O ([log (\frac{2}{δ^{∗}(T)})]^{min\{ \frac{1}{p} , \frac{1}{2} \}}) .

Thus, using Corollary 3.15, the proof of Theorem 4.1 will be complete if show that if a metric tree T = (V, E) does not admit any δ-strong coloring then there exists a subtree of T which is (Ω(1), 2 · δ^{Ω(1)})-weak prototype with height ratio O(1). It is clearly enough to prove this for small enough δ, so we assume in what follows that δ < (140)^{−2880} (the proof below yields much better constants, but we chose this rough bound to simplify the ensuing exposition). The proof of this assertion is analogous to the proof of Theorem 2.10, where “strong” colorings replace “good” colorings, and weak prototypes take the place of complete binary trees. Since the structure of a weak prototype is not as cleanly recursive as that of a complete binary tree, there are some inevitable added complications. The argument will be broken down into several steps.

4.1 Preliminary results on paths in trees

In what follows, given u, v ∈ V we shall say that a set of consecutive edges C ⊆ P (u, v) is a δ-cluster if ℓ(e) ≤ δd_{T} (u, v) for every e ∈ C.

Lemma 4.2. Fix α ∈ (0, \frac{1}{2}), δ ∈ (0, 1), and denote τ = \frac{1}{2−4α}. Assume that u, v ∈ V are such that the path P (u, v) is (\frac{1}{2} + α, δ)-weak. Then at least an α-fraction of the length of P (u, v) is covered by δ-clusters of length at least τδd_{T} (u, v). Moreover, at least an α-fraction of the length of P (u, v) is covered by edge-disjoint δ-clusters of length between τδd_{T} (u, v) and (2τ + 1)δd_{T} (u, v).

Proof. Fix u, v ∈ V and denote P = P (u, v) and d = d_{T} (u, v) = ℓ(P). Let M be the set of maximal δ-clusters (with respect to inclusion) contained in P. In what follows, for a δ-cluster C ⊆ P we write ℓ(C) = ∑_{e∈C} ℓ(e). Define S = {C ∈ M : ℓ(C) < τδd}. For every C ∈ S, since C is a maximal δ-cluster, there is an edge e_{C} ∈ P \ C which is incident with an edge in C, such that ℓ(e_{C}) > δd ≥ \frac{ℓ(C)}{τ}. Note that for every edge e ∈ P, |\{C ∈ S : e_{C} = e\}| ≤ 2. Now,

∑_{C∈S} \frac{ℓ(C)}{τ} ≤ ∑_{C∈S} ℓ(e_{C}) ≤ 2 ∑_{\begin{matrix}e∈P \\ ℓ(e)>δd \end{matrix}} ℓ(e) ≤ 2 (d − ∑_{\begin{matrix}e∈P \\ ℓ(e)≤δd \end{matrix}} ℓ(e)) ≤ 2 (1 − \frac{1}{2} − α) d = (1 − 2α) d.

Using the fact that the path P is (\frac{1}{2} + α, δ)-weak, we see that

(\frac{1}{2} + α) d ≤ ∑_{\begin{matrix}e∈P \\ ℓ(e)≤δd \end{matrix}} ℓ(e) = ∑_{\begin{matrix}C∈M \\ ℓ(C)≥τδd \end{matrix}} ℓ(C) + ∑_{C∈S} ℓ(C) ≤ ∑_{\begin{matrix}C∈M \\ ℓ(C)≥τδd \end{matrix}} ℓ(C) + (1 − 2α) τd.

Recalling that τ = \frac{1}{2−4α}, we see that ∑\begin{matrix}C∈M \\ ℓ(C)≥τδd \end{matrix} ℓ(C) ≥ αd, as required.

The final assertion of Lemma 4.2 is simply the fact that for any weighted path P = (u_{1}, …, u_{m}) such that for each j ∈ {1, …, m − 1} we have ℓ(u_{j}, u_{j+1}) ≤ a, but ∑_{j=1}^{m−1} ℓ(u_{j}, u_{j+1}) ≥ A, there are indices 1 = p_{1} < p_{2} < ⋯ < p_{k} = m such that for all j ∈ {1, …, k − 1} we have ∑_{i=p_{j}}^{p_{j+1}} ℓ(u_{i}, u_{i+1}) ∈ [A, 2A + a]. Indeed, let p_{2} > p_{1} be the first index such that ∑_{i=p_{1}}^{p_{2}} ℓ(u_{i}, u_{i+1}) ≥ A. Then ∑_{i=p_{1}}^{p_{2}} ℓ(u_{i}, u_{i+1}) ≤ A + a. Continuing inductively as long as the length of the remaining path is at least A we find 1 = p_{1} < p_{2} < ⋯ < p_{k} such that for j ∈ {1, …, k − 1} we have ∑_{i=p_{j}}^{p_{j+1}} ℓ(u_{i}, u_{i+1}) ∈ [A, A + a], and ∑_{i=p_{k}}^{m} ℓ(u_{i}, u_{i+1}) < A. The required result follows by replacing p_{k} with m, which increases the length of the final segment by at most A.

In order to proceed we need to generalize the notions of ε-good and δ-strong colorings. A coloring χ : E → ℤ will be called (ε, δ)-strong if it is monotone, and for every u, v ∈ V

∑_{k∈ℤ}ℓ_{k}^{χ}(u, v) · 1_{{ℓ_{k}^{χ}(u,v)≥δd_{T} (u,v)}} ≥ εd_{T} (u, v).

Note that we can always assume that ε ≥ δ. Using the terminology of Section 2.1, an ε-good coloring is the same as an (ε, ε)-strong coloring, and a δ-strong coloring is the same as a (\frac{1}{2}, δ)- strong coloring. Thus the following lemma is a generalization of Lemma 2.5.

Lemma 4.3. Fix ε ∈ (0, \frac{1}{2}] and δ ∈ (0, ε). Then any (ε, δ)-strong coloring is is also a (\frac{δ}{4ε})^{3/ε}-strong coloring.

Proof. The proof is a slight modification of the proof of Lemma 2.5. Let χ : E → ℤ be an (ε, δ)- strong coloring, and denote θ = _{\frac{ε}{2 log(\frac{4ε}{δ})}}. We shall show that for every α ∈ (0, 1] and u, v ∈ V,

the total length of the monochromatic segments of length at least αd_{T} (u, v) on the path P (u, v) satisfies

∑_{k∈ℤ}ℓ_{k}^{χ}(u, v) · 1_{\{ℓ_{k}^{χ}(u,v)≥αd_{T} (u,v)\}} ≥ (1 − (\frac{α}{δ})^{θ}) d_{T} (u, v).  (32)

There are points a_{1}, b_{1}, a_{2}, b_{2}, …, a_{m}, b_{m} ∈ V, ordered consecutively (from u to v) on the path P (u, v), such that the color classes of length at least δd_{T} (u, v) on the path P (u, v) are precisely the intervals {[a_{j}, b_{j}]}_{j=1}^{m}. Denote for the sake of simplicity b_{0} = u and a_{m+1} = v, and define β > 0 by βd_{T} (u, v) = ∑_{j=1}^{m} d_{T} (a_{j}, b_{j}). Since the coloring is (ε, δ)-strong, we know that β ≥ ε. By the definition of β we are also assured that m ≤ β/δ. If α > δ then inequality (32) holds vacuously, so we assume that α ≤ δ. Arguing inductively as in the proof of Lemma 2.5 we see that

∑_{k∈ℤ}ℓ_{k}^{χ}(u, v) · 1_{\{ℓ_{k}^{χ}(u,v)≥αd_{T} (u,v)\}} ≥ ∑_{j=1}^{m} d_{T} (a_{j}, b_{j}) + ∑_{j=0}^{m} (1 − (\frac{αd_{T} (u, v)}{δd_{T} (b_{j}, a_{j+1})})^{θ}) d_{T} (b_{j}, a_{j+1})

= d_{T} (u, v) − ∑_{j=0}^{m} (\frac{α}{δ})^{θ} [d_{T} (u, v)]^{θ} · [d_{T} (b_{j}, a_{j+1})]^{1−θ}

≥ d_{T} (u, v) − (m + 1) (\frac{α}{δ})^{θ} [d_{T} (u, v)]^{θ} (\frac{1}{m + 1} ∑_{j=0}^{m} d_{T} (b_{j}, a_{j+1}))^{1−θ}  (33)

= d_{T} (u, v) − (m + 1) (\frac{α}{δ})^{θ} [d_{T} (u, v)]^{θ} (\frac{(1 − β)d_{T} (u, v)}{m + 1})^{1−θ}
= (1 − (\frac{α}{δ})^{θ} (m + 1)^{θ}(1 − β)^{1−θ}) d_{T} (u, v)
≥ (1 − (\frac{α}{δ})^{θ} (\frac{β}{δ} + 1)^{θ} (1 − β)^{1−θ}) d_{T} (u, v)  (34)

≥ (1 − (\frac{α}{δ})^{θ} (\frac{2}{δ})^{θ} β^{θ}(1 − β)^{1−θ}) d_{T} (u, v)

≥ (1 − (\frac{α}{δ})^{θ} (\frac{2}{δ})^{θ} ε^{θ}(1 − ε)^{1−θ}) d_{T} (u, v)  (35)
≥ (1 − (\frac{α}{δ})^{θ}) d_{T} (u, v),  (36)

where in (33) we used the concavity of the function t ↦ t^{1−θ}, in (34) we used the fact that m ≤ β/δ, in (35) we used the fact that the function s ↦ s^{θ}(1−s)^{1−θ} is decreasing on [θ, 1] and that β ≥ ε ≥ θ (which follows from the definition of θ and the fact that ε ≥ δ), and in (36) we used the elementary inequality (\frac{2}{δ})^{θ} ε^{θ}(1 − ε)^{1−θ} ≤ 1, which is equivalent to θ ≤ \frac{log(1−ε)}{log[(1−ε)δ/(2ε)]}, and this follows from the definition of θ since ε ≤ \frac{1}{2}.

Recall that for R > 0 a subset N of a metric space X is an R-net if for every distinct x, y ∈ N we have d(x, y) ≥ R and for every z ∈ X there is x ∈ N with d(x, z) < R. In what follows we shall use the following variant of this notion.

Definition 4.4. Let T = (V, E) be a tree rooted at r with edge weights ℓ : E → (0, ∞). For R > 0 we shall call a set N ⊆ V an upward R-net of T if for every x, y ∈ N such that x is an ancestor of y we have d_{T} (x, y) ≥ R and for every v ∈ V there is x ∈ P (v) ∩ N such that d_{T} (v, x) < R. In other words, N is an upward R-net of T if and only if for every v ∈ V, N ∩ P (v) is an R-net in P (v).

Observe that an upward R-net in T need not be an R-net in T. However, the following easy lemma shows that upward R-nets always exist.

Lemma 4.5. T admits an upward R-net for every R > 0.

Proof. The proof is an easy induction on V. For |V | = 1 the result is trivial. Assume that |V | > 1 and let v ∈ V be a leaf of T. Let u ∈ V be the father of v. By the inductive hypothesis the tree T′ = (V \ {v}, E \ {(u, v)}) admits an upward R-net N′. Thus there exists x ∈ N ∩ P (u) such that d_{T′}(x, u) = d_{T} (x, u) < R. If ℓ(u, v) ≥ R − d_{T} (x, u) define N = N′ ∪ {v}, which is clearly an upward R-net in T. Otherwise d_{T} (v, x) < R, and since x ∈ P (v), it follows that N′ is also an upward R-net in T.

4.2 Construction of a special coloring and the proof of Theorem 4.1

Our basic strategy is similar to the proof of Theorem 2.10. To emphasize the similarities between the two proofs, we will use the same notation for the weight functions and the coloring that we construct (this will not cause any confusion since Section 2.2 can be read independently of the present section). As in the proof of Theorem 2.10 we will define a weight function μ_{j} on subtrees of T, and a “scale selector” g : V → ℤ ∪ {∞}, which will be used to construct a coloring χ of T. The fact that χ is not δ-strong will be used to find an appropriate copy of a weak prototype in T.

We begin with some notation. Let Q be a (weighted) path with initial vertex x and final vertex y, and let F be an arbitrary tree with root y (but otherwise disjoint from Q). For ε, δ ∈ (0, 1) and L > 0 we define ρ(ε, δ, L; Q, F) to be the least minimum distance from the root to a leaf in a subtree F′ ⊆ F which satisfies the following three conditions:

1. Every non-leaf vertex of F′ has exactly one or two children.

2. Let P be a root-leaf path in F′, and let P̃ be the vertices on P which are either one of the endpoints of P or have 2 children in F′. Then the path Q ∪ P̃ is (ε, δ)-weak.

3. Every path from x to a leaf of F′ has length at most 3L.

Next, we construct a monotone coloring χ : E → ℤ and a “scale selector” g : V → ℤ ∪ {∞} in a similar way to what was done in Section 2.2. Along the way we will also construct weight functions {μ_{s}}_{s∈ℤ} on subtrees of T. As in Section 2.2 we start by setting g(r) = ∞ and we assume inductively that the construction is done so that whenever v ∈ V is such that g(v) is defined, if u is a vertex on the path P (v) then g(u) has already been defined, and for every edge e ∈ E incident to v, χ(e) has been defined.

For every t ∈ ℤ let N_{t} be an upward 4^{t}-net of T. Since N_{t} is an upward 4^{t}-net, for all w ∈ V we are assured that N_{t}∩P (w)∩B_{T} (w, 4^{t}) ≠ ∅. We define λ_{t}(w) to be the point in N_{t}∩P (w)∩B_{T} (w, 2·4^{t}) which is furthest away from w. Now let t(s) ∈ ℤ be such that

240 · δ^{− \frac{1}{2880}} · 4^{s} ≤ 4^{t(s)} < 960 · δ^{− \frac{1}{2880}} · 4^{s}.

Take v ∈ V which is the vertex closest to the root r for which g(v) hasn’t yet been defined, and as in Section 2.2 we set

g(v) = max {j ∈ ℤ : ∀ u ∈ β_{χ}(v), d_{T} (u, v) ≥ 4^{min{g(u),j}}} .  (37)

Recall that β_{χ}(v) denotes the set of breakpoints of χ along the path P (v), and that by the inductive hypothesis the path P (v) has been entirely colored. Let F be a subtree of T rooted at v. We shall now define μ_{s}(F). To this end define a subset of the path P (v) by

Q_{s}(v) = {λ_{t(s)}(v)} ⋃ {w ∈ β_{χ}(v) : g(w) = g(v) and λ_{t(s)}(w) = λ_{t(s)}(v)} .  (38)

With this notation we can define

μ_{s}(F) = ρ (\frac{1}{2500}, δ^{\frac{1}{2880}} , 4^{t(s)}; Q_{s}(v), F ) .  (39)

In (39) we extended the definition of μ_{s} to all subtrees of T rooted at v. We next choose one of the children of v, w ∈ 𝒞 (v), for which

μ_{g(v)}(F_{w}) = max_{z∈𝒞 (v)} μ_{g(v)}(F_{z}).

Observe that μ_{g(v)}(F_{z}) is defined for all the children of v, since F_{z} is a subtree of T rooted at v (it is the subtree rooted at z ∈ 𝒞 (v) together with the incoming edge {v, z}). Letting u be the father of v on the path P (v), we set χ(v, w) = χ(u, v), and we assign arbitrary new (i.e. which haven’t been used before) distinct colors to each of the edges {(v, z)}_{z∈𝒞 (v)\{w}}.

This construction yields a monotone coloring χ, a function g : V → ℤ ∪ {∞}, and weight function {μ_{s}}_{s∈ℤ} defined on subtrees of T. In particular, we note here that Claim 2.11 still holds true, since its proof only used the fact that g was defined as in (37), and this formula is identical to the one used in Section 2.2. The following lemma contains the crucial properties of the coloring χ.

Lemma 4.6. Assume that the above coloring χ is not δ-strong. Then there exists a sequence of vertices Q = (x, w_{1}, …, w_{N}), ordered down the tree, and a number L > 0, such that if we define s, t ∈ ℤ by 4^{s−1} < \frac{1}{240}δ^{\frac{1}{2880}} L ≤ 4^{s} and 240δ^{− \frac{1}{2880}} 4^{s} ≤ 4^{t} < 960δ^{− \frac{1}{2880}} 4^{s}, then the path metric induced by T on Q has the following properties:

1. For every j ∈ {1, …, N} the vertex w_{j} is a breakpoint of χ.

2. For every j ∈ {1, …, N} we have g(w_{j}) = s and λ_{t}(w_{j}) = x.

3. The path Q is (\frac{1}{2500}, δ^{\frac{1}{2880}} )-weak.

4. The length of Q satisfies ℓ(Q) = d_{T} (x, w_{N}) ∈ [\frac{L}{850}, 3L].

Before passing to the proof of Lemma 4.6 we show how it can be used to complete the proof of Theorem 4.1.

Proof of Theorem 4.1. With Lemma 4.6 at hand, the proof of Theorem 4.1 is similar to the final step of the proof of Theorem 2.10. Assume that δ > δ^{∗}(T). Let Q = (x, w_{1}, …, w_{N}) be the path constructed in Lemma 4.6, and we shall also use the same s, t, L obtained there. Observe that using the notation in (38) we may assume that Q = Q_{s}(w_{N}). Indeed, by adding to Q any additional breakpoint w of χ along P (w_{N}) with g(w) = g(w_{N}) = s and λ_{t}(w) = λ_{t}(w_{N}) = x we do not change the conclusion Lemma 4.6.

For i ∈ {1, …, N − 1} let z_{i} be the child of w_{i} along the path P (x, w_{N}), and denote for the sake of simplicity z_{N} = w_{N}. We shall prove by induction on i ≥ 0 that the subtree of T rooted at z_{N−i} (i.e. the tree T_{z_{N−i}}) has a further sub-tree W_{i} satisfying the following properties.

1. Every path from x to a leaf of W_{i} has length at most 3 · 4^{t}.

2. Every non-leaf vertex of W_{i} has exactly one or two children.

3. Let P be a path from z_{N−i} to a leaf of W_{i}, and let P̃ be the vertices on P which are either one of the endpoints of P or have 2 children in W_{i}. Then the path (x, w_{1}, …, w_{N−i}) ∪ P̃ is (\frac{1}{2500}, δ^{\frac{1}{2880}} )-weak.

4. Every root-leaf path in W_{i} has length at least d_{T} (z_{N−i}, w_{N}).

For i = 0 we just take W_{0} to be the singleton w_{N}, and the fact that the required properties are satisfied is asserted in Lemma 4.6. Similarly, for i = 1 we let W_{1} be the tree consisting of the single edge (z_{N−1}, w_{N}) which satisfies the required properties due to Lemma 4.6. Assuming the existence of W_{i} we proceed inductively as follows. Since w_{N−i} is a breakpoint of χ, the construction of χ in the proof of Theorem 2.10, and the fact that g(w_{N−i}) = s, implies that there is a child z′_{N−i} of w_{N−i} for which μ_{s}(F_{z′_{N−i}}) > μ_{s}(F_{z_{N−i}}) (recall that for u ∈ V the tree F_{u} is the subtree rooted at u plus the edge joining u and its parent in T). Now, since Q_{s}(w_{N}) = Q we also know that (since λ_{t}(w_{N−i}) = x) Q_{s}(w_{N−i}) = {x, w_{1}, …, w_{N−i}}. Thus by the definition on μ_{s} in (39)

μ_{s}(F_{z_{N−i}}) = ρ (\frac{1}{2500}, δ^{\frac{1}{2880}} , 4^{t}; Q_{s}(w_{N−i}), F_{z_{N−i}}) = ρ (\frac{1}{2500}, δ^{\frac{1}{2880}} , 4^{t}; \{x, w_{1}, …, w_{N−i}\} , F_{z_{N−i}}) .

But, W_{i} is a subtree of F_{z_{N−i}} in which every non-leaf vertex has two children, for every path from x to a leaf of W_{i} the path metric induced by T on the vertices which are either x, or one of the w_{j}, or a leaf in W_{i}, or have 2 children in W_{i}, is (\frac{1}{2500}, δ^{\frac{1}{2880}} )-weak, every path from x to a leaf of W_{i} has length at most 3L ≤ 3 · 4^{t}, and the minimal distance from a root to a leaf of W_{i} is at least d_{T} (z_{N−i}, w_{N}). Thus the definition of ρ implies that μ_{s}(F_{z_{N−i}}) ≥ d_{T} (z_{N−i}, w_{N}). It follows that μ_{s}(F_{z′_{N−i}}) > d_{T} (z_{N−i}, w_{N}), implying the existence of a subtree W′_{i} of F_{z′_{N−i}}, which has the same properties as those stated above for W_{i}. Joining these two subtrees at w_{N−i}, and adding an edge from z_{N−i+1} to w_{N−i} we obtain a subtree W_{N−i+1} rooted at z_{N−i+1} with the desired properties. We recommend that the reader will follow the above construction using a drawing analogous to Figure 3.

The tree T′ obtained by joining the edges (x, w_{1}), (w_{1}, z_{1}) to W_{N−1} is a subtree of T which is a (\frac{1}{2500}, δ^{\frac{1}{2880}} )-weak prototype with height ratio at most \frac{3·4^{t}}{d(x,w_{N})} ≤ \frac{8L}{L/850} = 6800. As explained in the discussion following Theorem 4.1, this completes the proof.

Thus, all that remains is to prove Lemma 4.6.

Proof of Lemma 4.6. Since we are assuming that the coloring χ is not δ-strong, Lemma 4.3 implies that χ is also not (\frac{1}{960}, \frac{1}{240}δ^{\frac{1}{2880}} )-strong. Thus there exist two vertices u, v ∈ V such that more

than a \frac{959}{960}-fraction of the length of the path joining u and v is covered by color classes of length less than \frac{1}{240}δ^{\frac{1}{2880}} · d_{T} (u, v). Let (b_{1}, …, b_{m}) be the breakpoints of the coloring χ along the path P (u, v), ordered from u to v. We also denote b_{0} = u and b_{m+1} = v. Thus

∑_{j=1}^{m+1} d_{T} (b_{j−1}, b_{j}) · 1_{\{d_{T} (b_{j−1},b_{j})< \frac{1}{240} δ^{\frac{1}{2880}} ·d_{T} (u,v)\}} ≥ \frac{959}{960}d_{T} (u, v) = (\frac{1}{2} + \frac{479}{960}) d_{T} (u, v).

Lemma 4.2 (with α = \frac{479}{960} and τ = \frac{1}{2−4α} = 240) implies that there exists a sequence of indices 0 ≤ p_{1} < q_{1} ≤ p_{2} < q_{2} ≤ ⋯ ≤ p_{k−1} < q_{k−1} ≤ p_{k} < q_{k} ≤ m + 1 such that for every 1 ≤ i ≤ k we have d_{T} (b_{p_{i}}, b_{q_{i}}) ∈ [δ^{\frac{1}{2880}} d_{T} (u, v), 3δ^{\frac{1}{2880}} d_{T} (u, v)] and every p_{i} < j ≤ q_{i} satisfies d_{T} (b_{j−1}, b_{j}) ≤

\frac{1}{240}δ^{\frac{1}{2880}} d_{T} (u, v). Moreover, the total length of these “long \frac{1}{240}δ^{\frac{1}{2880}} -clusters” is

∑_{i=1}^{k} d_{T} (b_{p_{i}}, b_{q_{i}}) ≥ \frac{479}{960}d_{T} (u, v).  (40)

It follows in particular from (40) that k ≥ \frac{479}{3·960} · δ^{− \frac{1}{2880}} ≥ 20 (since δ < (140)^{−2880}).

Denote L = d_{T} (u, v) and recall that s ∈ ℤ is defined by 4^{s−1} < \frac{1}{240}δ^{\frac{1}{2880}} L ≤ 4^{s}. Fix 1 ≤ i ≤ k and apply Claim 2.11 to the path P (b_{p_{i}}, b_{q_{i}}) with c = 2 (which we are allowed to do by the definition of s). It follows that there exist at least two indices p_{i} ≤ j_{1}(i) < j_{2}(i) ≤ q_{i} such that g(b_{j_{1}(i)}) = g(b_{j_{2}(i)}) = s and 9 · 4^{s} ≤ d_{T} (b_{j_{1}(i)}, b_{j_{2}(i)}) ≤ 18 · 4^{s}.

Now t ∈ ℤ is given by by 240δ^{− \frac{1}{2880}} 4^{s} ≤ 4^{t} < 960δ^{− \frac{1}{2880}} 4^{s}. Note that by the definition of s this implies that L ≤ 4^{t} < 16L. For each point w ∈ {b_{j_{1}(1)}, b_{j_{2}(1)}, …, b_{j_{1}(k)}, b_{j_{1}(k)}} the vertex λ_{s}(w) is in B_{T} (w, 2 · 4^{t}) ∩ N_{t} ∩ P (w) ⊆ B_{T} (v, 2 · 4^{t} + L) ∩ N_{t} ∩ P (v) ⊆ B_{T} (v, 3 · 4^{t}) ∩ N_{t} ∩ P (v). Since N_{t} ∩ P (v) is 4^{t}-separated, it follows that there are at most 4 possible vertices which could equal λ_{t}(w). Thus there is a vertex x ∈ V and a subinterval J ⊆ \{1, …, k\} of size at least \frac{k}{4} − 1 ≥ \frac{k}{5} (since k ≥ 20) such that for all i ∈ J we have λ_{t}(b_{j_{1}(i)}) = λ_{t}(b_{j_{2}(i)}) = x. Note that since x = λ_{t}(w) for some w ∈ {b_{j_{1}(1)}, b_{j_{2}(1)}, …, b_{j_{1}(k)}, b_{j_{1}(k)}}, we know that x is the point in N_{t} ∩ P (w) ∩ B_{T} (w, 2 · 4^{t}) which is furthest from w. Since N_{t} is an upward 4^{t}-net, there is a point y ∈ N_{t} ∩ P (u) ∩ B_{T} (u, 4^{t}). So, using d_{T} (w, u) ≤ L ≤ 4^{t}, we see that y ∈ N_{t} ∩ P (w) ∩ B_{T} (w, 2 · 4^{t}). Thus x ∈ P (y) ⊆ P (u), i.e. x is closer to the root than u.

Consider the path metric induced on the vertices Q = {x}∪{b_{j_{1}(i)}}_{i∈J}∪{b_{j_{2}(i)}}_{i∈J}. For simplicity of notation we enumerate it down the tree by Q = (x, w_{1}, …, w_{N}). We bound the length of Q as follows. First, ℓ(Q) = d_{T} (x, w_{N}) = d_{T} (x, w_{1}) + d_{T} (w_{1}, w_{N}) ≤ 2 · 4^{t} + L ≤ 3L. On the other hand, using (40) we see that

ℓ(Q) ≥ ∑_{i∈J} d_{T} (b_{j_{1}(i)}, b_{j_{2}(i)}) ≥ ∑_{i∈J} 9 · 4^{s} ≥ \frac{k}{5} · 9 · 4^{s}

≥ \frac{9}{5} ∑_{i=1}^{k} \frac{1}{240}δ^{\frac{1}{2880}} L ≥ \frac{3}{400} ∑_{i=1}^{k} \frac{1}{3}d_{T} (b_{p_{i}}, b_{q_{i}}) ≥ \frac{479}{400 · 960}L ≥ \frac{ℓ(Q)}{2500}.

This also shows that the path Q is (\frac{1}{2500}, δ^{\frac{1}{2880}} )-weak, completing the proof of Lemma 4.6.

References

[1] M. Bădoiu, J. Chuzhoy, P. Indyk, and A. Sidiropoulos. Low-distortion embeddings of general metrics into the line. In STOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 225–233, New York, 2005. ACM.

[2] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137– 172, 1992.

[3] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[4] Y. Bartal. On approximating arbitrary metrices by tree metrics. In STOC ’98 (Dallas, TX), pages 161–168. ACM, New York, 1999.

[5] I. Benjamini and O. Schramm. Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant. Geom. Funct. Anal., 7(3):403–419, 1997.

[6] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222–230, 1986.

[7] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986.

[8] S. Buyalo and V. Schroeder. Embedding of hyperbolic spaces in the product of trees. Geom. Dedicata, 113:75–93, 2005.

[9] A. N. Dranishnikov. On hypersphericity of manifolds with finite asymptotic dimension. Trans. Amer. Math. Soc., 355(1):155–167 (electronic), 2003.

[10] A. W. M. Dress. Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. in Math., 53(3):321– 402, 1984.

[11] P. Enflo. On infinite-dimensional topological groups. In Séminaire sur la Géométrie des Espaces de Banach (1977–1978), pages Exp. No. 10–11, 11. École Polytech., Palaiseau, 1978.

[12] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 448–455, 2003.

[13] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56(2):121–155, 1976.

[14] H. Furstenberg and B. Weiss. Markov processes and Ramsey theory for trees. Combin. Probab. Comput., 12(5-6):547–563, 2003. Special issue on Ramsey theory.

[15] M. Gromov. Filling Riemannian manifolds. J. Differential Geom., 18(1):1–147, 1983.

[16] A. Gupta. Steiner points in tree metrics don’t (really) help. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pages 220– 227, Philadelphia, PA, 2001. SIAM.

[17] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, pages 534–543, 2003.

[18] W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Lipschitz quotients from metric trees and from Banach spaces containing l_{1}. J. Funct. Anal., 194(2):332–346, 2002.

[19] V. A. Kaĭmanovich and A. M. Vershik. Random walks on discrete groups: boundary and entropy. Ann. Probab., 11(3):457–490, 1983.

[20] U. Lang and T. Schlichenmaier. Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions. Internat. Math. Research Notices, 58:3625–3655, 2005.

[21] E. Leuzinger. Bi-Lipschitz embeddings of trees into Euclidean buildings. Geom. Dedicata, 102:109–125, 2003.

[22] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin, 1979. Function spaces.

[23] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[24] N. Linial, A. Magen, and M. E. Saks. Low distortion Euclidean embeddings of trees. Israel J. Math., 106:339–348, 1998.

[25] N. Linial and M. Saks. The Euclidean distortion of complete binary trees. Discrete Comput. Geom., 29(1):19–21, 2003.

[26] R. Lyons, R. Pemantle, and Y. Peres. Random walks on the lamplighter group. Ann. Probab., 24(4):1993–2006, 1996.

[27] J. Matoušek. Extension of Lipschitz mappings on metric trees. Comment. Math. Univ. Carolin., 31(1):99–104, 1990.

[28] J. Matoušek. On embedding trees into uniformly convex Banach spaces. Israel J. Math., 114:221–237, 1999.

[29] B. Maurey and G. Pisier. Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach. Studia Math., 58(1):45–90, 1976.

[30] M. Mendel and A. Naor. Metric cotype. To appear in the Annals of Mathematics, 2005.

[31] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[32] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552:213–236, 2002.

[33] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4):326–350, 1975.

[34] G. Pisier. Probabilistic methods in the geometry of Banach spaces. In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167–241. Springer, Berlin, 1986.

[35] C. Thomassen. Isoperimetric inequalities and transient random walks on graphs. Ann. Probab., 20(3):1592–1600, 1992.

[36] N. T. Varopoulos. Long range estimates for Markov chains. Bull. Sci. Math. (2), 109(3):225– 252, 1985.