Markov convexity and local rigidity of distorted metrics

Manor Mendel^{∗} Open University of Israel

                 manorme@openu.ac.il

Assaf Naor^{†} Courant Institute

                                          naor@cims.nyu.edu

Abstract

It is shown that a Banach space admits an equivalent norm whose modulus of uniform convexity has power-type p if and only if it is Markov p-convex. Counterexamples are constructed to natural questions related to isomorphic uniform convexity of metric spaces, showing in particular that tree metrics fail to have the dichotomy property.

Contents

1 Introduction 2

1.1 The nonexistence of a metric dichotomy for trees . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Overview of the proofs of Theorem 1.10 and Theorem 1.12 . . . . . . . . . . 7

2 Markov p-convexity and p-convexity coincide 9

3 A doubling space which is not Markov p-convex for any p ∈ (0, ∞) 15

4 Lipschitz quotients 17

5 A dichotomy theorem for vertically faithful embeddings of trees 18

6 Tree metrics do not have the dichotomy property 21 6.1 Horizontally contracted trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6.2 Geometry of H-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

6.2.1 Classification of approximate midpoints . . . . . . . . . . . . . . . . . . . . . 23 6.2.2 Classification of approximate forks . . . . . . . . . . . . . . . . . . . . . . . . 30 6.2.3 Classification of approximate 3-paths . . . . . . . . . . . . . . . . . . . . . . . 36

6.3 Nonembeddability of vertically faithful B_{4} . . . . . . . . . . . . . . . . . . . . . . . . 42 6.4 Nonembeddability of binary trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7 Discussion and open problems 45

∗Supported by ISF grant 221/07, BSF grant 2006009, and a gift from Cisco research center.

†Supported by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation.

1 Introduction

A Banach space (X, ∥ · ∥_{X}) is said to be finitely representable in a Banach space (Y, ∥ · ∥_{Y}) if there exists a constant D < ∞ such that for every finite dimensional linear subspace F ⊆ X there is a linear operator T : F → Y satisfying ∥x∥_{X} ⩽ ∥T x∥_{Y} ⩽ D∥x∥_{X} for all x ∈ F. In 1976 Ribe [31] proved that if two Banach spaces X and Y are uniformly homeomorphic, i.e., there is a bijection f : X → Y such that f and f^{−1} are uniformly continuous, then X is finitely representable in Y and vice versa. This remarkable theorem motivated what is known today as the “Ribe program”: the search for purely metric reformulations of basic linear concepts and invariants from the local theory of Banach spaces. This research program was put forth by Bourgain in 1986 [5].

Since its inception, the Ribe program attracted the work of many mathematicians, and led to the development of several satisfactory metric theories that extend important concepts and results of Banach space theory; see the introduction of [24] for a historical discussion. So far, progress on the Ribe program has come hand-in-hand with applications to metric geometry, group theory, functional analysis, and computer science. The present paper contains further progress in this direction: we obtain a metric characterization of p-convexity in Banach spaces, derive some of its metric consequences, and construct unexpected counter-examples which indicate that further progress on the Ribe program can uncover nonlinear phenomena that are markedly different from their Banach space counterparts. In doing so, we answer questions posed by Lee-Naor-Peres and Fefferman, and improve a theorem of Bates, Johnson, Lindenstrauss, Preiss and Schechtman. These results, which will be explained in detail below, were announced in [23].

For p ⩾ 2, a Banach space (X, ∥ · ∥_{X}) is said to be p-convex if there exists a norm ||| · ||| which is equivalent to ∥ · ∥_{X} (i.e., for some a, b > 0, a∥x∥_{X} ⩽ |||x||| ⩽ b∥x∥_{X} for all x ∈ X), and a constant K > 0 satisfying:

|||x||| = |||y||| = 1 ⟹ |||\frac{x + y}{2} ||| ⩽ 1 − K|||x − y|||^{p}.  (1)

X is called superreflexive if it is p-convex for some p ⩾ 2 (historically, this is not the original definition of superreflexivity^{1}, but it is equivalent to it due to a deep theorem of Pisier [29], which builds on important work of James [10] and Enflo [7]). For concreteness, we recall (see, e.g., [2]) that L_{p} is 2-convex for p ∈ (1, 2] and p-convex for p ∈ [2, ∞).

Ribe’s theorem implies that p-convexity, and hence also superreflexivity, is preserved under uniform homeomorphisms. The first major success of the Ribe program is a famous theorem of Bourgain [5] which obtains a metrical characterization of superreflexivity as follows.

Theorem 1.1 (Bourgain’s metrical characterization of superreflexivity [5]). Let B_{n} be the complete unweighted binary tree of depth n, equipped with the natural graph-theoretical metric. Then a Banach space X is superreflexive if and only if

lim_{n→∞} c_{X}(B_{n}) = ∞.  (2)

Here, and in what follows, given two metric spaces (ℳ , d_{ℳ} ), (𝒩 , d_{𝒩} ), the parameter c_{ℳ} (𝒩 ) denotes the smallest bi-Lipschitz distortion with which 𝒩 embeds into ℳ, i.e., the infimum of those D > 0 such that there exists a scaling factor r > 0 and a mapping f : 𝒩 → ℳ satisfying rd_{𝒩} (x, y) ⩽ d_{ℳ} (x, y) ⩽ Drd_{𝒩} (x, y) for all x, y ∈ 𝒩 (if no such f exists then set c_{ℳ} (𝒩 ) = ∞).

1James’ original definition of superreflexivity is that a Banach space X is superreflexive if “its local structure forces reflexivity”, i.e., if every Banach space Y that is finitely representable in X must be reflexive. Enflo’s renorming theorem states that superreflexivity is equivalent to having an equivalent norm ||| · ||| that is uniformly convex, i.e., for every ε ∈ (0, 1) there exists δ > 0 such that if |||x||| = |||y||| = 1 and |||x − y||| = ε then |||x + y||| ⩽ 2 − δ.

Bourgain’s theorem characterizes superreflexivity of Banach spaces in terms of their metric structure, but it leaves open the characterization of p-convexity. The notion of p-convexity is crucial for many applications in Banach space theory and metric geometry, and it turns out that the completion of the Ribe program for p-convexity requires significant additional work beyond Bourgain’s superreflexivity theorem. As a first step in this direction, Lee, Naor and Peres [16] defined a bi-Lipschitz invariant of metric spaces called Markov convexity, which is motivated by Ball’s notion of Markov type [1] and Bourgain’s argument in [5].

Definition 1.2 ([16]). Let {X_{t}}_{t∈ℤ} be a Markov chain on a state space Ω. Given an integer k ⩾ 0, we denote by {X̃_{t}(k)}_{t∈ℤ} the process which equals X_{t} for time t ⩽ k, and evolves independently (with respect to the same transition probabilities) for time t > k. Fix p > 0. A metric space (X, d_{X}) is called Markov p-convex with constant Π if for every Markov chain {X_{t}}_{t∈ℤ} on a state space Ω, and every f : Ω → X,

∑_{k=0}^{∞} ∑_{t∈ℤ} \frac{𝔼 [d_{X} (f(X_{t}), f (X̃_{t} (t − 2^{k})))^{p}]}{2^{kp}} ⩽ Π^{p} · ∑_{t∈ℤ} 𝔼[d_{X}(f(X_{t}), f(X_{t−1}))^{p}].  (3)

The least constant Π for which (3) holds for all Markov chains is called the Markov p-convexity constant of X, and is denoted Π_{p}(X). We shall say that (X, d_{X}) is Markov p-convex if Π_{p}(X) < ∞.

To gain intuition for Definition 1.2, consider the standard downward random walk starting from the root of the binary tree B_{n} (with absorbing states at the leaves). For an arbitrary mapping f from B_{n} to a metric space (X, d_{X}), the triangle inequality implies that for each k ∈ ℕ we have

∑_{t∈ℤ} \frac{𝔼 [d_{X} (f(X_{t}), f (X̃_{t} (t − 2^{k})))^{p}]}{2^{kp}} ≲_{p} ∑_{t∈ℤ} 𝔼[d_{X}(f(X_{t}), f(X_{t−1}))^{p}],  (4)

with asymptotic equality (up to constants depending only on p) for k ⩽ \frac{log n}{2} when X = B_{n} and f is the identity mapping. On the other hand, if X is a Markov p-convex space then the sum over k of the left-hand side of (4) is uniformly bounded by the right-hand side of (4), and therefore Markov p-convex spaces cannot contain B_{n} with distortion uniformly bounded in n.

We refer to [16] for more information on the notion of Markov p-convexity. In particular, it is shown in [16] that the Markov 2-convexity constant of an arbitrary weighted tree T is, up to constant factors, the Euclidean distortion of T. We refer to [16] for L_{p} versions of this statement and their algorithmic applications. It was also shown in [16], via a modification of an argument of Bourgain [5], that if a Banach space X is p-convex then it is also Markov p-convex. It was asked in [16] if the converse is also true. Here we answer this question positively:

Theorem 1.3. A Banach space is p-convex if and only if it is Markov p-convex.

Thus Markov p-convexity is equivalent to p-convexity in Banach spaces, completing the Ribe program in this case. Our proof of Theorem 1.3 is based on a renorming method of Pisier [29]. It can be viewed as a nonlinear variant of Pisier’s argument, and several subtle changes are required in order to adapt it to a nonlinear condition such as (3).

Results similar to Theorem 1.3 have been obtained for the notions of type and cotype of Banach spaces (see [6, 30, 1, 25, 24, 22]), and have been used to transfer some of the linear theory to the setting of general metric spaces. This led to several applications to problems in metric geometry. Apart from the applications of Markov p-convexity that were obtained in [16], here we show that this invariant is preserved under Lipschitz quotients. The notion of Lipschitz quotient was introduced by Gromov [8, Sec. 1.25]. Given two metric spaces (X, d_{X}) and (Y, d_{Y}), a surjective mapping f : X → Y is called a Lipschitz quotient if it is Lipschitz, and it is also “Lipschitzly open” in the sense that there exists a constant c > 0 such that for every x ∈ X and r > 0,

f (B_{X}(x, r)) ⊇ B_{Y} (f(x), \frac{r}{c} ) .  (5)

Here we show the following result:

Theorem 1.4. If (X, d_{X}) is Markov p-convex and (Y, d_{Y}) is a Lipschitz quotient of X, then Y is also Markov p-convex.

In [3] Bates, Johnson, Lindenstrauss, Preiss and Schechtman investigated in detail Lipschitz quotients of Banach spaces. Their results imply that if 2 ⩽ p < q then L_{q} is not a Lipschitz quotient of L_{p}. Since L_{p} is p-convex, it is also Markov p-convex. Hence also all of its subsets are Markov p convex. But, L_{q} is not p-convex, so we deduce that L_{q} is not a Lipschitz quotient of any subset of L_{p}. Thus our new “invariant approach” to the above result of [3] significantly extends it. Note that the method of [3] is based on a differentiation argument, and hence it crucially relies on the fact that the Lipschitz quotient mapping is defined on all of L_{p} and not just on an arbitrary subset of L_{p}.

In light of Theorem 1.3 it is natural to ask if Bourgain’s characterization of superreflexivity holds for general metric spaces. Namely, is it true that for any metric space X, if lim_{n→∞} c_{X}(B_{n}) = ∞ then X is Markov p-convex for some p < ∞? This question was asked in [16], where it was shown that the answer is positive if (X, d_{X}) is a metric tree. Here we show that in general the answer is negative:

Theorem 1.5. There exists a metric space (X, d_{X}) which is not Markov p-convex for any p ∈ (0, ∞), yet lim_{n→∞} c_{X}(B_{n}) = ∞. In fact, (X, d_{X}) can be a doubling metric space, and hence c_{X}(B_{n}) ⩾ 2^{κn} for some constant κ > 0.

Theorem 1.5 is in sharp contrast to the previously established metric characterizations of the linear notions of type and cotype. Specifically, it was shown by Bourgain, Milman and Wolfson [6] that any metric space with no nontrivial metric type must contain the Hamming cubes ({0, 1}^{n}, ∥·∥_{1}) with distortion independent of n. An analogous result was obtained in [24] for metric spaces with no nontrivial metric cotype, with the Hamming cube replaced by the ℓ_{∞} grid ({1, …, m}^{n}, ∥ · ∥_{∞}).

Our proof of Theorem 1.5 is based on an analysis of the behavior of a certain Markov chain on the Laakso graphs: a sequence of combinatorial graphs whose definition is recalled in Section 3. As a consequence of this analysis, we obtain the following distortion lower bound:

Theorem 1.6. For any p ⩾ 2, the Laakso graph of cardinality n incurs distortion Ω((log n)^{1/p}) in any embedding into a p-convex Banach space.

Thus, in particular, for p > 2 the n-point Laakso graph incurs distortion Ω((log n)^{1/p}) in any embedding into L_{p}. The case of L_{p} embeddings of the Laakso graphs when 1 < p ⩽ 2 was already solved in [26, 12, 15, 14] using the uniform 2-convexity property of L_{p}. But, these proofs rely crucially on 2-convexity and do not extend to the case of p-convexity when p > 2. Subsequent to the publication of our proof of Theorem 1.6 in the announcement [23], an alternative proof of this fact was recently discovered by Johnson and Schechtman in [11].

1.1 The nonexistence of a metric dichotomy for trees

Bourgain’s metrical characterization of superreflexivity yields the following statement:

Theorem 1.7 (Bourgain’s tree dichotomy [5]). For any Banach space (X, ∥·∥_{X}) one of the following two dichotomic possibilities must hold true:

• either for all n ∈ ℕ we have c_{X}(B_{n}) = 1,

• or there exists α = α_{X} > 0 such that for all n ∈ ℕ we have c_{X}(B_{n}) ⩾ (log n)^{α}.

Thus, there is a gap in the possible rates of growth of the sequence {c_{X}(B_{n})}_{n=1}^{∞} when X is a Banach space; consequently, if we were told that, say, c_{X}(B_{n}) = O(log log n), then we would immediately deduce that actually c_{X}(B_{n}) = 1 for all n. Additional gap results of this type are known due to the theory of nonlinear type and cotype:

Theorem 1.8 (Bourgain-Milman-Wolfson cube dichotomy [6]). For any metric space (X, d_{X}) one of the following two dichotomic possibilities must hold true:

• either for all n ∈ ℕ we have c_{X} ({0, 1}^{n}, ∥ · ∥_{1}) = 1,

• or there exists α = α_{X} > 0 such that for all n ∈ ℕ we have c_{X} ({0, 1}^{n}, ∥ · ∥_{1}) ⩾ n^{α}.

Theorem 1.8 is a metric analogue of Pisier’s characterization [28] of Banach spaces with trivial Rademacher type. A metric analogue of the Maurey-Pisier characterization [20] of Banach spaces with finite Rademacher cotype yields the following dichotomy result for ℓ_{∞} grids:

Theorem 1.9 (Grid dichotomy [24]). For any metric space (X, d_{X}) one of the following two dichotomic possibilities must hold true:

• either for all n ∈ ℕ we have c_{X} ({0, …, n}^{n}, ∥ · ∥_{∞}) = 1,

• or there exists α = α_{X} > 0 such that for all n ∈ ℕ we have c_{X} ({0, …, n}^{n}, ∥ · ∥_{∞}) ⩾ n^{α}.

We refer to the survey article [21] for more information on the theory of metric dichotomies. Note that Theorem 1.7 is stated for Banach spaces, while Theorem 1.8 and Theorem 1.9 hold

for general metric spaces. One might expect that as in the case of previous progress on Ribe’s program, a metric theory of p-convexity would result in a proof that Theorem 1.7 holds when X is a general metric space. Surprisingly, we show here that this is not true:

Theorem 1.10. There exists a universal constant C > 0 with the following property. Assume that {s(n)}_{n=0}^{∞} ⊆ [4, ∞) is a nondecreasing sequence such that {n/s(n)}_{n=0}^{∞} is also nondecreasing. Then there exists a metric space (X, d_{X}) satisfying for all n ⩾ 2,

s (⌊\frac{n}{40s(n)}⌋) (1 − \frac{Cs(n) log s(n)}{log n}) ⩽ c_{X}(B_{n}) ⩽ s(n).  (6)

Thus, assuming that s(n) = o (\frac{log n}{log log n}), there exists a subsequence \{n_{k}\}_{k=1}^{∞} for which

(1 − o(1))s(n_{k}) ⩽ c_{X}(B_{n_{k}}) ⩽ s(n_{k}).  (7)

Theorem 1.10 shows that unlike the case of Banach spaces, for general metric spaces, c_{X}(B_{n}) can have an arbitrarily slow growth rate.

Bourgain, Milman and Wolfson also obtained in [6] the following finitary version of Theorem 1.8:

Theorem 1.11 (Local rigidity of Hamming cubes [6]). For every ε > 0, D > 1 and n ∈ ℕ there exists m = m(ε, D, n) ∈ ℕ such that

lim_{n→∞} m(ε, D, n) = ∞,

and for every metric d on {0, 1}^{n} which is bi-Lipschitz with distortion ⩽ D to the ℓ_{1} (Hamming) metric,

c_{({0,1}^{n},d)} ({0, 1}^{m}, ∥ · ∥_{1}) ⩽ 1 + ε.

We refer to [6] (see also [30]) for bounds on m(ε, D, n). Informally, Theorem 1.11 says that the Hamming cube ({0, 1}^{n}, ∥ · ∥_{1}) is locally rigid in the following sense: it is impossible to distort the Hamming metric on a sufficiently large hypercube without the resulting metric space containing a hardly distorted copy of an arbitrarily large Hamming cube. Stated in this way, Theorem 1.11 is a metric version of James’ theorem [9] that ℓ_{1} is not a distortable space. The analogue of Theorem 1.11 with the Hamming cube replaced by the ℓ_{∞} grid ({0, …, n}^{n}, ∥ · ∥_{∞}) is Matoušek’s BD-Ramsey theorem [19]; see [24] for quantitative results of this type in the ℓ_{∞} case. The following variant of Theorem 1.10 shows that a local rigidity statement as above fails to hold true for binary trees; it can also be viewed as a negative solution of the distortion problem for the infinite binary tree (see [27] and [4, Ch. 13, 14] for more information on the distortion problem for Banach spaces).

Theorem 1.12. Let B_{∞} be the complete unweighted infinite binary tree. For every D ⩾ 4 there exists a metric d on B_{∞} that is D-equivalent to the original shortest-path metric on B_{∞}, yet for every ε ∈ (0, 1) and m ∈ ℕ,

c_{(B_{∞},d)}(B_{m}) ⩽ D − ε ⟹ m ⩽ D^{CD^{2}/ε}.

The local rigidity problem for binary trees was studied by several mathematicians. In particular, C. Fefferman asked (private communication, 2005) whether {B_{n}}_{n=1}^{∞} have the local rigidity property, and Theorem 1.12 answers this question negatively. Fefferman also proved a partial local rigidity result which is a non-quantitative variant of Theorem 1.14 below (see also Section 5). We are very grateful to C. Fefferman for asking us the question that led to the counter-examples of Theorem 1.10 and Theorem 1.12, for sharing with us his partial positive results, and for encouraging us to work on these questions. M. Gromov also investigated the local rigidity problem for binary trees, and proved (via different methods) non-quantitative partial positive results in the spirit of Theorem 1.14. We thank M. Gromov for sharing with us his unpublished work on this topic.

The results of Theorem 1.10 and Theorem 1.12 are quite unexpected. Unfortunately, their proofs are delicate and lengthy, and as such constitute the most involved part of this article. In order to facilitate the understanding of these constructions, we end the introduction with an overview of the main geometric ideas that are used in their proofs. This is done in Section 1.1.1 below—we recommend reading this section first before delving into the technical details presented in Section 6.

1.1.1 Overview of the proofs of Theorem 1.10 and Theorem 1.12

For x ∈ B_{∞} let h(x) be its depth, i.e., its distance from the root. Also, for x, y ∈ B_{∞} let lca(x, y) denote their least common ancestor. The tree metric on B_{∞} is then given by:

d_{B_{∞}}(x, y) = h(x) + h(y) − 2h(lca(x, y)).

The metric space X of Theorem 1.10 will be B_{∞} as a set, with a new metric defined as follows. Given a sequence ε = {ε_{n}}_{n=0}^{∞} ⊆ (0, 1] we define d_{ε} : B_{∞} × B_{∞} → [0, ∞) by

d_{ε}(x, y) = |h(y) − h(x)| + 2ε_{min{h(x),h(y)}} · [min{h(x), h(y)} − h(lca(x, y))] .

d_{ε} does not necessarily satisfy the triangle inequality, but under some simple conditions on the sequence {ε_{n}}_{n=0}^{∞} it does become a metric on B_{∞}; see Lemma 6.1. A pictorial description of the metric d_{ε} is contained in Figure 1. Note that when ε_{n} = 1 for all n, we have d_{ε} = d_{B_{∞}}. Below we call the metric spaces (B_{∞}, d_{ε}) horizontally distorted trees, or H-trees, in short.

Figure 1: The metric d_{ε} defined on B_{∞}. The arrows indicate horizontal contraction by ε_{h(x)}.

The metric space (X, d_{X}) of Theorem 1.10 will be (B_{∞}, d_{ε}), where ε_{n} = 1/s(n) for all n. The identity mapping of B_{n} into the top n-levels of B_{∞} has distortion at most s(n), and therefore c_{X}(B_{n}) ⩽ s(n). The challenge is to prove the lower bound on c_{X}(B_{n}) in (6). Our initial approach to lower-bounding c_{X}(B_{n}) was Matoušek’s metric differentiation proof [18] of asymptotically sharp distortion lower bounds for embeddings of B_{n} into uniformly convex Banach spaces.

Following Matoušek’s terminology [18], for δ > 0 a quadruple of points (x, y, z, w) in a metric space (X, d_{X}) is called a δ-fork if y ∈ Mid(x, z, δ) ∩ Mid(x, w, δ), where for a, b ∈ X the set of δ-approximate midpoints Mid(a, b, δ) ⊆ X is defined as the set of all w ∈ X satisfying max\{d_{X}(x, y), d_{X}(y, z)\} ⩽ \frac{1+δ}{2} · d_{X}(x, z). The points z, w will be called below the prongs of the δ-fork (x, y, z, w). Matoušek starts with the observation that if X is a uniformly convex Banach space then in any δ-fork in X the distance between the prongs must be much smaller (as δ → 0) than d_{X}(x, y). Matoušek then shows that for all D > 0, any distortion D embedding of B_{n} into X must map some 0-fork in B_{n} to a δ-fork in X, provided n is large enough (as a function of D and δ). This reasoning immediately implies that c_{X}(B_{n}) must be large when X is a uniformly convex Banach space, and a clever argument of Matoušek in [18] turns this qualitative argument into sharp quantitative bounds.

Of course, we cannot hope to use the above argument of Matoušek in order to prove Theorem 1.10, since Bourgain’s tree dichotomy theorem (Theorem 1.7) does hold true for Banach spaces. But, perhaps we can mimic this uniform convexity argument for other target metric spaces? On the face of it, H-trees are ideally suited for this purpose, since the horizontal contractions that we introduced shrink distances between the prongs of canonical forks (call (x, y, z, w) ∈ B_{∞} a canonical fork if x is an ancestor of y and z, w are descendants of y at depth h(x) + 2(h(y) − h(x))). It is for this reason exactly that we defined H-trees.

Unfortunately, the situation isn’t so simple. It turns out that H-trees do not behave like uniformly convex Banach spaces in terms of the prong-contractions that they impose of δ-forks. H-trees can even contain larger problematic configurations that have several undistorted δ-forks; such an example is depicted in Figure 2.

Figure 2: The metric space on the right is the H-tree (B_{∞}, d_{ε}), where ε_{n} = δ for all n. The picture describes an embedding of the tree on the left (B_{3} minus 4 leaves) into (B_{∞}, d_{ε}) with distortion at most 6, yet all ancestor/descendant distances are distorted by at most 1 + O(δ).

Thus, in order to prove Theorem 1.10 it does not suffice to use Matoušek’s argument that a bi-Lipschitz embedding of a large enough B_{n} must send some 0-fork to a δ-fork. But, it turns out that this argument applies not only to forks, but also to larger configurations.

Definition 1.13. Let (T, d_{T}) be a tree with root r, and let (X, d_{X}) be a metric space. A mapping f : T → X is called a D-vertically faithful embedding if there exists a (scaling factor) λ > 0 satisfying for any x, y ∈ T such that x is an ancestor of y,

λd_{T} (x, y) ⩽ d_{X}(f(x), f(y)) ⩽ Dλd_{T} (x, y).  (8)

Recall that the distortion of a mapping ϕ : ℳ → 𝒩 between metric spaces (ℳ , d_{ℳ} ) and (𝒩 , d_{𝒩} ) is defined as

dist(ϕ) =^{def} ( sup_{\begin{matrix}x,y∈ℳ \\ x≠y \end{matrix}} \frac{d_{𝒩} (ϕ(x), ϕ(y))}{d_{ℳ} (x, y)}) · ( sup_{\begin{matrix}x,y∈ℳ \\ x≠y \end{matrix}} \frac{d_{ℳ} (x, y)}{d_{𝒩} (ϕ(x), ϕ(y))}) ∈ [1, ∞].

With this terminology, we can state the following crucial result.

Theorem 1.14. There exists a universal constant c > 0 with the following property. Fix an integer t ⩾ 2, δ, ξ ∈ (0, 1), and D ⩾ 2, and assume that n ∈ ℕ satisfies

n ⩾ \frac{1}{ξ}D^{c(t log t)/δ}.  (9)

Let (X, d_{X}) be a metric space and f : B_{n} → X a D-vertically faithful embedding. Then there exists a mapping ϕ : B_{t} → B_{n} with the following properties.

• If x, y ∈ B_{t} are such that x is an ancestor of y, then ϕ(x) is an ancestor of ϕ(y).

• dist(ϕ) ⩽ 1 + ξ.

• The mapping f ∘ ϕ : B_{t} → X is a (1 + δ)-vertically faithful embedding of B_{t} in X.

Theorem 1.14 is essentially due to Matoušek [18]. Matoušek actually proved this statement only for t = 2, since this is all that he needed in order to analyze forks. But, his proof extends in a straightforward way to any t ∈ ℕ. Since we will use this assertion with larger t, for the sake of completeness we reprove it, in a somewhat different way, in Section 5. Note that Theorem 1.14 says that {B_{n}}_{n=1}^{∞} do have a local rigidity property with respect to vertically faithfully embeddings.

We solve the problem created by the existence of configurations as those depicted in Figure 2 by studying (1 + δ)-vertically faithful embeddings of B_{4}, and arguing that they must contain a large contracted pair of points. This claim, formalized in Lemma 6.27, is proved in Sections 6.2, 6.3.

We begin in Section 6.2.1 with studying how the metric P_{2} (3-point path) can be approximately embedded in (B_{∞}, d_{ε}). We find that there are essentially only two ways to embed it in (B_{∞}, d_{ε}), as depicted in Figure 3. We then proceed in Section 6.2.2 to study δ-forks in (B_{∞}, d_{ε}). Since forks are formed by “stitching” two approximate P_{2} metrics along a common edge (the handle), we can limit the “search space” using the results of Section 6.2.1. We find that there are six possible types of different approximate forks in (B_{∞}, d_{ε}), only four of which (depicted in Figure 4) do not have highly contracted prongs. Complete binary trees, and in particular B_{4}, are composed of forks stitched together, handle to prong. In order to study handle-to-prong stitching, we investigate in Section 6.2.3 how the metric P_{3} (4-point path) can be approximately embedded in (B_{∞}, d_{ε}). This is again done by studying how two P_{2} metrics can be stitched together, this time bottom edge to top edge. We find that there are only three different approximate configurations of P_{4} in (B_{∞}, d_{ε}).

Using the machinery described above, we study in Section 6.3 how the different types of forks can be stitched together in embeddings of B_{4} into (B_{∞}, d_{ε}), reaching the conclusion that a large contraction is unavoidable, and thus completing the proof of Lemma 6.27. The proofs of Theorem 1.10 and Theorem 1.12 are concluded in Section 6.4.

2 Markov p-convexity and p-convexity coincide

In this section we prove Theorem 1.3, i.e., that for Banach spaces p-convexity and Markov pconvexity are the same properties. We first show that p-convexity implies Markov p-convexity, and in fact it implies a stronger inequality that is stated in Proposition 2.1 below. The slightly weaker assertion that p-convexity implies Markov p-convexity was first proved in [16], based on an argument from [5]. Our argument here is different and simpler.

It was proved in [29] that a Banach space X is p-convex if and only if it admits an equivalent norm ∥ · ∥ for which there exists K > 0 such that for every a, b ∈ X,

2∥a∥^{p} + \frac{2}{K^{p}} ∥b∥^{p} ⩽ ∥a + b∥^{p} + ∥a − b∥^{p}.  (10)

Proposition 2.1. Let {X_{t}}_{t∈ℤ} be random variables taking values in a set Ω. For every s ∈ ℤ let {X̃_{t}(s)}_{t∈ℤ} be random variables taking values in Ω, with the following property:

∀ r ⩽ s ⩽ t, (X_{r}, X_{t}) and (X_{r}, X̃_{t}(s)) have the same distribution.  (11)

Fix p ⩾ 2 and let (X, ∥ · ∥) be a Banach space whose norm satisfies (10). Then for every f : Ω → X we have

∑_{k=0}^{∞} ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t}) − f (X̃_{t}(t − 2^{k}))∥^{p}]}{2^{kp}} ⩽ (4K)^{p} ∑_{t∈ℤ} 𝔼[∥f(X_{t}) − f(X_{t−1})∥^{p}].  (12)

Remark 2.2. Observe that condition (11) holds when {X_{t}}_{t∈ℤ} is a Markov chain on a state space Ω, and {X̃_{t}(s)}_{t∈ℤ} is as in Definition 1.2.

We start by proving a useful inequality that is a simple consequence of (10).

Lemma 2.3. Let X be a Banach space whose norm satisfies (10). Then for every x, y, z, w ∈ X,

\frac{∥x − w∥^{p} + ∥x − z∥^{p}}{2^{p−1}} + \frac{∥z − w∥^{p}}{4^{p−1}K^{p}} ⩽ ∥y − w∥^{p} + ∥z − y∥^{p} + 2∥y − x∥^{p}.  (13)

Proof. For every x, y, z, w ∈ X, (10) implies that

\frac{∥x − w∥^{p}}{2^{p−1}} + \frac{2}{K^{p}} ∥y − \frac{x + w}{2} ∥^{p} ⩽ ∥y − x∥^{p} + ∥y − w∥^{p},

and

\frac{∥z − x∥^{p}}{2^{p−1}} + \frac{2}{K^{p}} ∥y − \frac{z + x}{2}∥^{p} ⩽ ∥z − y∥^{p} + ∥y − x∥^{p}.

Summing these two inequalities, and applying the convexity of the map u ↦ ∥u∥^{p}, we see that

∥y − w∥^{p} + ∥z − y∥^{p} + 2∥y − x∥^{p} ⩾ \frac{∥x − w∥^{p} + ∥z − x∥^{p}}{2^{p−1}} + \frac{4}{K^{p}} · \frac{∥y − \frac{x+w}{2} ∥^{p} + ∥y − \frac{z+x}{2} ∥^{p}}{2}

⩾ \frac{∥x − w∥^{p} + ∥z − x∥^{p}}{2^{p−1}} + \frac{4}{K^{p}} · ∥\frac{z − w}{4} ∥^{p} ,

implying (13).

Proof of Proposition 2.1. Using Lemma 2.3 we see that for every t ∈ ℤ and k ∈ ℕ,

\frac{∥f(X_{t}) − f(X_{t−2^{k}})∥^{p} + ∥f(X̃_{t}(t − 2^{k−1})) − f(X_{t−2^{k}})∥^{p}}{2^{p−1}} + \frac{∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥^{p}}{4^{p−1}K^{p}}

⩽ ∥f(X_{t−2^{k−1}}) − f(X_{t})∥^{p} + ∥f(X_{t−2^{k−1}}) − f(X̃_{t}(t − 2^{k−1}))∥^{p} + 2∥f(X_{t−2^{k−1}}) − f(X_{t−2^{k}})∥^{p}.

Taking expectation, and using the assumption (11), we get

\frac{𝔼 [∥f(X_{t}) − f(X_{t−2^{k}})∥^{p}]}{2^{p−2}} + \frac{𝔼 [∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥^{p}]}{4^{p−1}K^{p}}

⩽ 2𝔼 [∥f(X_{t−2^{k−1}}) − f(X_{t})∥^{p}] + 2𝔼 [∥f(X_{t−2^{k−1}}) − f(X_{t−2^{k}})∥^{p}] .

Dividing by 2^{(k−1)p+2} this becomes

\frac{𝔼 [∥f(X_{t}) − f(X_{t−2^{k}})∥^{p}]}{2^{kp}} + \frac{𝔼 [∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥^{p}]}{2^{(k+1)p}K^{p}}

⩽ \frac{𝔼 [∥f(X_{t−2^{k−1}}) − f(X_{t})∥^{p}]}{2^{(k−1)p+1}} + \frac{𝔼 [∥f(X_{t−2^{k−1}}) − f(X_{t−2^{k}})∥^{p}]}{2^{(k−1)p+1}}.

Summing this inequality over k = 1, …, m and t ∈ ℤ we get

∑_{k=1}^{m} ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t}) − f(X_{t−2^{k}})∥^{p}]}{2^{kp}} + ∑_{k=1}^{m} ∑_{t∈ℤ} \frac{[𝔼∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥^{p}]}{2^{(k+1)p}K^{p}}

⩽ ∑_{k=1}^{m} ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t−2^{k−1}}) − f(X_{t})∥^{p}]}{2^{(k−1)p+1}} + ∑_{k=1}^{m} ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t−2^{k−1}}) − f(X_{t−2^{k}})∥^{p}]}{2^{(k−1)p+1}}

= ∑_{j=0}^{m−1} ∑_{s∈ℤ} \frac{𝔼 [∥f(X_{s}) − f(X_{s−2^{j}})∥^{p}]}{2^{jp}}.  (14)

It is only of interest to prove (12) when ∑_{t∈ℤ} 𝔼[∥f(X_{t}) − f(X_{t−1})∥^{p}] < ∞. By the triangle inequality, this implies that for every k ∈ ℕ we have ∑_{t∈ℤ} 𝔼 [∥f(X_{t}) − f(X_{t−2^{k}})∥^{p}] < ∞. We may therefore cancel terms in (14), arriving at the following inequality:

∑_{k=1}^{m} ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t}) − f(X̃_{t}(t − 2^{k−1}))∥^{p}]}{2^{(k+1)p}K^{p}}

⩽ ∑_{t∈ℤ} 𝔼 [∥f(X_{t}) − f(X_{t−1})∥^{p}] − ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t}) − f(X_{t−2^{m}})∥^{p}]}{2^{mp}} ⩽ ∑_{t∈ℤ} 𝔼 [∥f(X_{t}) − f(X_{t−1})∥^{p}] .

Equivalently,

∑_{k=0}^{m−1} ∑_{t∈ℤ} \frac{𝔼 [∥f(X_{t}) − f(X̃_{t}(t − 2^{k}))∥^{p}]}{2^{kp}} ⩽ (4K)^{p} ∑_{t∈ℤ} 𝔼 [∥f(X_{t}) − f(X_{t−1})∥^{p}] .

Proposition 2.1 now follows by letting m → ∞.

We next prove the more interesting direction of the equivalence of p-convexity and Markov p-convexity: a Markov p-convex Banach space is also p-convex.

Theorem 2.4. Let (X, ∥ · ∥) be a Banach space which is Markov p-convex with constant Π. Then for every ε ∈ (0, 1) there exists a norm ||| · ||| on X such that for all x, y ∈ X,

(1 − ε)∥x∥ ⩽ |||x||| ⩽ ∥x∥,

and

|||\frac{x + y}{2} |||^{p} ⩽ \frac{|||x|||^{p} + |||y|||^{p}}{2} − \frac{1 − (1 − ε)^{p}}{4Π^{p}(p + 1)} · |||\frac{x − y}{2} |||^{p} .

Thus the norm ||| · ||| satisfies (10) with constant K = O (\frac{Π}{ε^{1/p}} ).

Proof. The fact that X is Markov p-convex with constant Π implies that for every Markov chain {X_{t}}_{t∈ℤ} with values in X, and for every m ∈ ℕ, we have

∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥X_{t} − X̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}} ⩽ Π^{p} ∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − X_{t−1}∥^{p}] .  (15)

For x ∈ X we shall say that a Markov chain {X_{t}}_{t=−∞}^{2^{m}} is an m-admissible representation of x if X_{t} = 0 for t ⩽ 0 and 𝔼 [X_{t}] = tx for t ∈ {1, …, 2^{m}}. Fix ε ∈ (0, 1), and denote η = 1 − (1 − ε)^{p}. For every m ∈ ℕ define

|||x|||_{m} = inf \{(\frac{1}{2^{m}} ∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − X_{t−1}∥^{p}] − \frac{η}{Π^{p}} · \frac{1}{2^{m}} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥X_{t} − X̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}} )^{1/p}\} , (16)

where the infimum in (16) is taken over all m-admissible representations of x. Observe that an m-admissible representation of x always exists, since we can define X_{t} = 0 for t ⩽ 0 and X_{t} = tx for t ∈ {1, …, 2^{m}}. This example shows that |||x|||_{m} ⩽ ∥x∥. On the other hand, if {X_{t}}_{t=−∞}^{2^{m}} is an m-admissible representation of x then

∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − X_{t−1}∥^{p}] − \frac{η}{Π^{p}} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥X_{t} − X̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}} ⩾^{(15)} (1 − η) ∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − X_{t−1}∥^{p}]

⩾ (1 − ε)^{p} ∑_{t=1}^{2^{m}} ∥𝔼 [X_{t}] − 𝔼 [X_{t−1}]∥^{p} = (1 − ε)^{p} ∑_{t=1}^{2^{m}} ∥tx − (t − 1)x∥^{p} = 2^{m}(1 − ε)^{p}∥x∥^{p}, (17)

where in the first inequality of (17) we used the convexity of the function z ↦ ∥z∥^{p}. In conclusion, we see that for all x ∈ X,

(1 − ε)∥x∥ ⩽ |||x|||_{m} ⩽ ∥x∥.  (18)

Now take x, y ∈ X and fix δ ∈ (0, 1). Let {X_{t}}_{t=−∞}^{2^{m}} be an admissible representation on x and {Y_{t}}_{t=−∞}^{2^{m}} be an admissible representation of y which is stochastically independent of {X_{t}}_{t=−∞}^{2^{m}}, such that

∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − X_{t−1}∥^{p}] − \frac{η}{Π^{p}} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥X_{t} − X̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}} ⩽ 2^{m}(|||x|||_{m}^{p} + δ),  (19)

and

∑_{t=1}^{2^{m}} 𝔼 [∥Y_{t} − Y_{t−1}∥^{p}] − \frac{η}{Π^{p}} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥Y_{t} − Ỹ_{t}(t − 2^{k})∥^{p}]}{2^{kp}} ⩽ 2^{m}(|||y|||_{m}^{p} + δ).  (20)

Define a Markov chain \{Z_{t}\}_{t=−∞}^{2^{m+1}} ⊆ X as follows. For t ⩽ −2^{m} set Z_{t} = 0. With probability \frac{1}{2} let (Z_{−2^{m}+1}, Z_{−2^{m}+2}, …, Z_{2^{m+1}}) equal

(\underbrace{0, …, 0}_{2^{m} times}, X_{1}, X_{2}, …, X_{2^{m}}, X_{2^{m}} + Y_{1}, X_{2^{m}} + Y_{2}, …, X_{2^{m}} + Y_{2^{m}}),

and with probability \frac{1}{2} let (Z_{−2^{m}+1}, Z_{−2^{m}}, …, Z_{2^{m+1}}) equal

(\underbrace{0, …, 0}_{2^{m} times}, Y_{1}, Y_{2}, …, Y_{2^{m}}, X_{1} + Y_{2^{m}}, X_{2} + Y_{2^{m}}, …, X_{2^{m}} + Y_{2^{m}}).

Hence, Z_{t} = 0 for t ⩽ 0, for t ∈ \{1, …, 2^{m}\} we have 𝔼 [Z_{t}] = \frac{𝔼[X_{t}]+𝔼[Y_{t}]}{2} = t · \frac{x+y}{2} , and for t ∈ {2^{m} + 1, …, 2^{m+1}} we have

𝔼 [Z_{t}] = \frac{𝔼 [X_{2^{m}} + Y_{t−2^{m}}] + 𝔼 [X_{t−2^{m}} + Y_{2^{m}}]}{2} = \frac{2^{m}x + (t − 2^{m})y + (t − 2^{m})x + 2^{m}y}{2} = t · \frac{x + y}{2} .

Thus \{Z_{t}\}_{t=−∞}^{2^{m+1}} is an (m + 1)-admissible representation of \frac{x+y}{2} . The definition (16) implies that

2^{m+1} |||\frac{x + y}{2} |||_{m+1}^{p} ⩽ ∑_{t=1}^{2^{m+1}} 𝔼 [∥Z_{t} − Z_{t−1}∥^{p}] − \frac{η}{Π^{p}} ∑_{k=0}^{m+1} ∑_{t=1}^{2^{m+1}} \frac{𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}}.  (21)

Note that by definition,

∑_{t=1}^{2^{m+1}} 𝔼 [∥Z_{t} − Z_{t−1}∥^{p}] = ∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − X_{t−1}∥^{p}] + ∑_{t=1}^{2^{m}} 𝔼 [∥Y_{t} − Y_{t−1}∥^{p}] .  (22)

Moreover,

∑_{k=0}^{m+1} ∑_{t=1}^{2^{m+1}} \frac{𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}}

= \frac{1}{2^{(m+1)p}} ∑_{t=1}^{2^{m+1}} 𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{m+1})∥^{p}] + ∑_{k=0}^{m} ∑_{t=1}^{2^{m+1}} \frac{𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}}. (23)

We bound each of the terms in (23) separately. Note that by construction we have for every t ∈ {1, …, 2^{m}},

Z_{t} − Z̃_{t} (t − 2^{m+1}) = Z_{t} − Z̃_{t} (1 − 2^{m+1}) = \begin{cases}X_{t} − Y_{t} & with probability 1/4, \\ Y_{t} − X_{t} & with probability 1/4, \\ X_{t} − X̃_{t}(1) & with probability 1/4, \\ Y_{t} − Ỹ_{t}(1) & with probability 1/4. \end{cases}

Thus, the first term in the right hand side of (23) can be bounded from below as follows:

\frac{1}{2^{(m+1)p}} ∑_{t=1}^{2^{m+1}} 𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{m+1})∥^{p}] ⩾ \frac{1}{2^{(m+1)p+1}} ∑_{t=1}^{2^{m}} 𝔼 [∥X_{t} − Y_{t}∥^{p}]

⩾ \frac{1}{2^{(m+1)p+1}} ∑_{t=1}^{2^{m}} ∥𝔼 [X_{t}] − 𝔼 [Y_{t}] ∥^{p} = \frac{∥x − y∥^{p}}{2^{(m+1)p+1}} ∑_{t=1}^{2^{m}} t^{p} ⩾ \frac{2^{m}∥x − y∥^{p}}{2^{p+1}(p + 1)} . (24)

We now proceed to bound from below the second term in the right hand side of (23). Note first that for every k ∈ {0, …, m} and every t ∈ {2^{m} + 1, …, 2^{m+1}} we have

Z_{t}−Z̃_{t}(t−2^{k}) = \{ \begin{matrix}(X_{2^{m}} + Y_{t−2^{m}}) − (X̃_{2^{m}}(t − 2^{k}) + Ỹ_{t−2^{m}}(t − 2^{m} − 2^{k})) & with probability 1/2, \\ (Y_{2^{m}} + X_{t−2^{m}}) − (Ỹ_{2^{m}}(t − 2^{k}) + X̃_{t−2^{m}}(t − 2^{m} − 2^{k})) & with probability 1/2. \end{matrix}

By Jensen’s inequality, if U, V are X-valued independent random variables with 𝔼[V] = 0, then 𝔼 [∥U + V ∥^{p}] ⩾ 𝔼 [∥U + 𝔼[V]∥^{p}] = 𝔼 [∥U∥^{p}]. Thus, since {X_{t}}_{t=−∞}^{2^{m}} and {Y_{t}}_{t=−∞}^{2^{m}} are independent,

𝔼 [∥Y_{t−2^{m}} − Ỹ_{t−2^{m}}(t − 2^{m} − 2^{k}) + X_{2^{m}} − X̃_{2^{m}}(t − 2^{k})∥^{p}]

⩾ 𝔼 [∥Y_{t−2^{m}} − Ỹ_{t−2^{m}}(t − 2^{m} − 2^{k})∥^{p}] ,

and

𝔼 [∥X_{t−2^{m}} − X̃_{t−2^{m}}(t − 2^{m} − 2^{k}) + Y_{2^{m}} − Ỹ_{2^{m}}(t − 2^{k})∥^{p}]

⩾ 𝔼 [∥X_{t−2^{m}} − X̃_{t−2^{m}}(t − 2^{m} − 2^{k})∥^{p}] .

It follows that for every k ∈ {0, …, m} and every t ∈ {2^{m} + 1, …, 2^{m+1}} we have

𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{k})∥^{p}]

⩾ \frac{1}{2}𝔼 [∥X_{t−2^{m}} − X̃_{t−2^{m}}(t − 2^{m} − 2^{k})∥^{p}] + \frac{1}{2}𝔼 [∥Y_{t−2^{m}} − Ỹ_{t−2^{m}}(t − 2^{m} − 2^{k})∥^{p}] . (25)

Hence,

∑_{k=0}^{m} ∑_{t=1}^{2^{m+1}} \frac{𝔼 [∥Z_{t} − Z̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}} ⩾^{(25)} ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{\frac{1}{2}𝔼 [∥X_{t} − X̃_{t}(t − 2^{k})∥^{p}] + \frac{1}{2}𝔼 [∥Y_{t} − Ỹ_{t}(t − 2^{k})∥^{p}]}{2^{kp}}

+ ∑_{k=0}^{m} ∑_{t=2^{m}+1}^{2^{m+1}} \frac{\frac{1}{2} [𝔼∥X_{t−2^{m}} − X̃_{t−2^{m}}(t − 2^{m} − 2^{k})∥^{p}] + \frac{1}{2}𝔼 [∥Y_{t−2^{m}} − Ỹ_{t−2^{m}}(t − 2^{m} − 2^{k})∥^{p}]}{2^{kp}}

= ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥X_{t} − X̃_{t}(t − 2^{k})∥^{p}]}{2^{kp}} + ∑_{k=0}^{m} ∑_{t=1}^{2^{m}} \frac{𝔼 [∥Y_{t} − Ỹ_{t}(t − 2^{k})∥^{p}]}{2^{kp}}.  (26)

Combining (19), (20), (21), (22), (23), (24) and (26), and letting δ tend to 0, we see that

2^{m+1} |||\frac{x + y}{2} |||_{m+1}^{p} ⩽ 2^{m}|||x|||_{m}^{p} + 2^{m}|||y|||_{m}^{p} − \frac{η}{Π^{p}} · \frac{2^{m}∥x − y∥^{p}}{2^{p+1}(p + 1)} ,

or,

|||\frac{x + y}{2} |||_{m+1}^{p} ⩽ \frac{|||x|||_{m}^{p} + |||y|||_{m}^{p}}{2} − \frac{η}{4Π^{p}(p + 1)} · ∥\frac{x − y}{2} ∥^{p} .  (27)

Define for w ∈ X,

|||w||| = lim sup_{m→∞} |||w|||_{m}.

Then a combination of (18) and (27) yields that

(1 − ε)∥x∥ ⩽ |||x||| ⩽ ∥x∥,

and

|||\frac{x + y}{2} |||^{p} ⩽ \frac{|||x|||^{p} + |||y|||^{p}}{2} − \frac{η}{4Π^{p}(p + 1)} · ∥\frac{x − y}{2} ∥^{p}

⩽ \frac{|||x|||^{p} + |||y|||^{p}}{2} − \frac{η}{4Π^{p}(p + 1)} · |||\frac{x − y}{2} |||^{p} . (28)

Note that (28) implies that the set {x ∈ X : |||x||| ⩽ 1} is convex, so that ||| · ||| is a norm on X. This concludes the proof of Theorem 2.4.

3 A doubling space which is not Markov p-convex for any p ∈ (0, ∞)

Consider the Laakso graphs [12], {G_{i}}_{i=0}^{∞}, which are defined as follows. G_{0} is the graph consisting of one edge of unit length. To construct G_{i}, take six copies of G_{i−1} and scale their metric by a factor of \frac{1}{4}. We glue four of them cyclicly by identifying pairs of endpoints, and attach at two opposite gluing points the remaining two copies. Note that each edge of G_{i} has length 4^{−i}; we denoted the resulting shortest path metric on G_{i} by d_{G_{i}}. As shown in [13, Thm. 2.3], the doubling constant of metric space (G_{i}, d_{G_{i}}) is at most 6.

We direct G_{m} as follows. Define the root of G_{m} to be (an arbitrarily chosen) one of the two vertices having only one adjacent edge. In the figure this could be the leftmost vertex r. Note that in no edge the two endpoints are at the same distance from the root. The edges of G_{m} are then directed from the endpoint closer to the root to the endpoint further away from the root. The resulting directed graph is acyclic. We now define {X_{t}}_{t=0}^{4^{m}} to be the standard random walk on the directed graph G_{m}, starting from the root. This random walk is extended to t ∈ ℤ by stipulating that X_{t} = X_{0} for t < 0, and X_{t} = X_{4^{m}} for t > 4^{m}.

Proposition 3.1. For the random walk defined above,

∑_{k=0}^{2m} ∑_{t∈ℤ} \frac{𝔼 [d_{G_{m}}(X_{t}, X̃_{t}(t − 2^{k}))^{p}]}{2^{kp}} ≳ \frac{m}{8^{p}} ∑_{t∈ℤ} 𝔼 [d_{G_{m}}(X_{t}, X_{t−1})^{p}] .  (29)

Proof. For every t ∈ ℤ we have,

𝔼 [d_{G_{m}}(X_{t}, X_{t−1})^{p}] = \{ \begin{matrix}4^{−mp} & t ∈ \{0, … 4^{m} − 1\}, \\ 0 & otherwise. \end{matrix}

Hence,

∑_{t∈ℤ} 𝔼 [d_{G_{m}}(X_{t}, X_{t−1})^{p}] = 4^{−m(p−1)}.  (30)

Fix k ∈ {0, …, 2m − 2} and write h = ⌈k/2⌉. View G_{m} as being built from A = G_{m−h}, where each edge of A has been replaced by a copy of G_{h}. Note that for every i ∈ {0, …, 4^{m−h−1} + 1}, at time t = (4i + 1)4^{h} the walk X_{t} is at a vertex of G_{m} which has two outgoing edges, corresponding to distinct copies of G_{h}. To see this it suffices to show that all vertices of G_{m−h} that are exactly (4i + 1) edges away from the root, have out-degree 2. This fact is true since G_{m−h} is obtained from G_{m−h−1} by replacing each edge by a copy of G_{1}, and each such copy of G_{1} contributes one vertex of out-degree 2, corresponding to the vertex labeled b in the figure describing G_{1}.

Consider the set of times

T_{k} =^{def} {0, …, 4^{m} − 1} ⋂ ( ⋃_{i=0}^{4^{m−h−1}+1}[(4i + 1)4^{h} + 4^{h−2}, (4i + 1)4^{h} + 2 · 4^{h−2}]) .

For t ∈ T_{k} find i ∈ {0, …, 4^{m−h−1} + 1} such that t ∈ [(4i + 1)4^{h} + 4^{h−2}, (4i + 1)4^{h} + 2 · 4^{h−2}]. Since, by the definition of h, we have t − 2^{k} ∈ [(4i + 1)4^{h} − 4^{h}, (4i + 1)4^{h}), the walks {X_{s}}_{s∈ℤ} and {X̃_{s}(t − 2^{k})}_{s∈ℤ} started evolving independently at some vertex lying in a copy of G_{h} preceding a vertex v of G_{m} which has two outgoing edges, corresponding to distinct copies of G_{h}. Thus, with probability at least \frac{1}{2}, the walks X_{t} and X̃_{t}(t − 2^{k}) lie on two distinct copies of G_{h} in G_{m}, immediately following the vertex v, and at distance at least 4^{h−2}·4^{−m} and at most 2·4^{h−2}·4^{−m} from v. Hence, with probability at least \frac{1}{2} we have d_{G_{m}} (X_{t}, X̃_{t}(t − 2^{k})) ⩾ 2 · 4^{h−2} · 4^{−m} = 2^{2h−3−2m}, and therefore,

\frac{𝔼 [d(X_{t}, X̃_{t}(t − 2^{k}))^{p}]}{2^{kp}} ⩾ \frac{\frac{1}{2}2^{(2h−3−2m)p}}{2^{kp}} ⩾ 2^{−(2m+3)p−1}.

We deduce that for all k ∈ {0, …, 2m − 2},

∑_{t∈ℤ} \frac{𝔼 [d(X_{t}, X̃_{t}(t − 2^{k}))^{p}]}{2^{kp}} ⩾ ∑_{t∈T_{k}} \frac{𝔼 [d(X_{t}, X̃_{t}(t − 2^{k}))^{p}]}{2^{kp}} ⩾ |T_{k}| · 2^{−(2m+3)p−1}

≳ 4^{h−2} · 4^{m−h−1} · 2^{−(2m+3)p−1} ≳ \frac{1}{8^{p}} 4^{−m(p−1)}. (31)

A combination of (30) and (31) implies (29).

Proof of Theorem 1.5. As explained in [12, 13], by passing to an appropriate Gromov-Hausdorff limit, there exists a doubling metric space (X, d_{X}) that contains an isometric copy of all the Laakso graphs {G_{m}}_{m=0}^{∞}. Proposition 3.1 therefore implies that X is not Markov p-convex for any p ∈ (0, ∞).

Proof of Theorem 1.6. Let (X, d_{X}) be a Markov p-convex metric space, i.e, Π_{p}(X) < ∞. Assume that f : G_{m} → X satisfies

x, y ∈ G_{m} ⟹ \frac{1}{A}d_{G_{m}}(x, y) ⩽ d_{X}(f(x), f(y)) ⩽ Bd_{G_{m}}(x, y).  (32)

Let {X_{t}}_{t∈ℤ} be the random walk from Proposition 3.1. Then

\frac{m}{8^{p}A^{p}} ∑_{t∈ℤ} 𝔼 [d_{G_{m}}(X_{t}, X_{t−1})^{p}] ≲^{(29)} \frac{1}{A^{p}} ∑_{k=0}^{2m} ∑_{t∈ℤ} \frac{𝔼 [d_{G_{m}}(X_{t}, X̃_{t}(t − 2^{k}))^{p}]}{2^{kp}}

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

⩽^{(3)} Π_{p}(X)^{p} ∑_{t∈ℤ} 𝔼 [d_{X}(f(X_{t}), f(X_{t−1}))^{p}]

⩽^{(32)} Π_{p}(X)^{p}B^{p} ∑_{t∈ℤ} 𝔼 [d_{G_{m}}(X_{t}, X_{t−1})^{p}] .

Thus AB ≳ m^{1/p} ≳ (log |G_{m}|)^{1/p}.

4 Lipschitz quotients

Say that a metric space (Y, d_{Y}) is a D-Lipschitz quotient of a metric space (X, d_{X}) if there exist a, b > 0 with ab ⩽ D and a mapping f : X → Y such that for all x ∈ X and r > 0,

B_{Y} (f(x), \frac{r}{a}) ⊆ f (B_{X}(x, r)) ⊆ B_{Y} (f(x), br).  (33)

Observe that the last inclusion in (33) is to equivalent to the fact that f is b-Lipschitz. The following proposition implies Theorem 1.4.

Proposition 4.1. If (Y, D_{Y}) is a D-Lipschitz quotient of (X, d_{X}) then Π_{p}(Y) ⩽ D · Π_{p}(X).

Proof. Fix f : X → Y satisfying (33). Also, fix a Markov chain {X_{t}}_{t∈ℤ} on a state space Ω, and a mapping g : Ω → Y.

Fix m ∈ ℤ and let Ω^{∗} be the set of finite sequences of elements of Ω starting at time m, i.e., the set of sequences of the form (ω_{i})_{i=m}^{t} ∈ Ω^{t−m+1} for all t ⩾ m. It will be convenient to consider the Markov chain {X_{t}^{∗}}_{t=m}^{∞} on Ω^{∗} which is given by:

Pr [X_{t}^{∗} = (ω_{m}, ω_{m+1}, …, ω_{t})] = Pr [X_{m} = ω_{m}, X_{m+1} = ω_{m+1}, …, X_{t} = ω_{t}] .

Also, define g^{∗} : Ω^{∗} → Y by g^{∗}(ω_{1}, …, ω_{t}) = g(ω_{t}). By definition, {g^{∗}(X_{t}^{∗})}_{t=m}^{∞} and {g(X_{t})}_{t=m}^{∞} are identically distributed.

We next define a mapping h^{∗} : Ω^{∗} → X such that f ∘ h^{∗} = g^{∗} and for all (ω_{m}, …, ω_{t}) ∈ Ω^{∗},

d_{X} (h^{∗}(ω_{m}, …, ω_{t−1}), h^{∗}(ω_{m}, …, ω_{t})) ⩽ ad_{Y} (g(ω_{t−1}), g(ω_{t})).  (34)

For ω^{∗} ∈ Ω^{∗}, we will define h^{∗}(ω^{∗}) by induction on the length of ω^{∗}. If ω^{∗} = (ω_{m}), then we fix h^{∗}(ω^{∗}) to be an arbitrary element in f^{−1}(g(ω_{m})). Assume that ω^{∗} = (ω_{m}, …, ω_{t−1}, ω_{t}) and that h^{∗}(ω_{m}, …, ω_{t−1}) has been defined. Set x = f(h^{∗}(ω_{m}, …, ω_{t−1})) = g^{∗}(ω_{m}, …, ω_{t−1}) = g(ω_{t−1}) and r = ad_{Y} (g(ω_{t−1}), g(ω_{t})). Since g(ω_{t}) ∈ B_{Y} (x, r/a), it follows from (33) there exists y ∈ X such that f(y) = g(ω_{t}), and d_{X}(x, y) ⩽ r. We then define h^{∗}((ω_{m}, …, ω_{t−1}, ω_{t})) =^{def} y.

Write X_{t}^{∗} = X_{m}^{∗} for t ⩽ m. By the Markov p-convexity of (X, d_{X}), we have

∑_{k=0}^{∞} ∑_{t∈ℤ} \frac{𝔼 [d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X̃_{t}^{∗}(t − 2^{k})))^{p}]}{2^{kp}} ⩽ Π_{p}(X)^{p} ∑_{t∈ℤ} 𝔼 [d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X_{t−1}^{∗}))^{p}] .  (35)

By (34) we have for every t ⩾ m + 1,

d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X_{t−1}^{∗})) ⩽ ad_{Y} (g(X_{t}), g(X_{t−1})),

while for t ⩽ m we have d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X_{t−1}^{∗})) = 0. Thus,

∑_{t∈ℤ} 𝔼 [d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X_{t−1}^{∗}))^{p}] ⩽ a^{p} ∑_{t∈ℤ} 𝔼 [d_{Y} (g(X_{t}), g(X_{t−1}))^{p}] .  (36)

At the same time, using the fact that f is b-Lipschitz and f ∘ h^{∗} = g^{∗}, we see that if t ⩾ m + 2^{k},

d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X̃_{t}^{∗}(t − 2^{k}))) ⩾ \frac{1}{b}d_{Y} (f(h^{∗}(X_{t}^{∗})), f(h^{∗}(X̃_{t}^{∗}(t − 2^{k}))))

= \frac{1}{b}d_{Y} (g^{∗}(X_{t}^{∗}), g^{∗}(X̃_{t}^{∗}(t − 2^{k}))) = \frac{1}{b}d_{Y} (g(X_{t}), g(˜ .X_{t}(t − 2^{k})))

Thus,

∑_{k=0}^{∞} ∑_{t∈ℤ} \frac{𝔼 [d_{X}(h^{∗}(X_{t}^{∗}), h^{∗}(X̃_{t}^{∗}(t − 2^{k})))^{p}]}{2^{kp}} ⩾ \frac{1}{b^{p}} ∑_{k=0}^{∞} ∑_{t=m+2^{k}}^{∞} \frac{𝔼 [d_{Y} (g(X_{t}), g(X̃_{t}(t − 2^{k})))^{p}]}{2^{kp}}. (37)

By combining (36) and (37) with (35), and letting m tend to −∞, we get the inequality:

∑_{k=0}^{∞} ∑_{t∈ℤ} \frac{𝔼 [d_{Y} (g(X_{t}), g(X̃_{t}(t − 2^{k})))^{p}]}{2^{kp}} ⩽ (abΠ_{p}(X))^{p} ∑_{t∈ℤ} 𝔼 [d_{Y} (g(X_{t}), g(X_{t−1}))^{p}] .

Since this inequality holds for every Markov chain {X_{t}}_{t∈ℤ} and every g : Ω → Y, and since ab ⩽ D, we have proved that Π_{p}(Y) ⩽ DΠ_{p}(X), as required.

5 A dichotomy theorem for vertically faithful embeddings of trees

In this section we prove Theorem 1.14. The proof naturally breaks into two parts. The first is the following BD Ramsey property of paths (which can be found non-quantitatively in [19], where also the BD Ramsey terminology is explained).

A mapping ϕ : ℳ → 𝒩 is called a rescaled isometry if dist(ϕ) = 1, or equivalently there exists λ > 0 such that d_{𝒩} (ϕ(x), ϕ(y)) = λd_{ℳ} (x, y) for all x, y ∈ ℳ. For n ∈ ℕ let P_{n} denote the n-path, i.e., the set {0, …, n} equipped with the metric inherited from the real line.

Proposition 5.1. Fix δ ∈ (0, 1), D ⩾ 2 and t, n ∈ ℕ satisfying n ⩾ D^{(4t log t)/δ}. If f : P_{n} → X satisfies dist(f) ⩽ D then there exists a rescaled isometry ϕ : P_{t} → P_{n} such that dist(f ∘ ϕ) ⩽ 1 + δ.

Given a metric space (X, d_{X}) and a nonconstant mapping f : P_{n} → X, define

T (X, f) =^{def} \frac{d_{X}(f(0), f(n)}{n max_{i∈\{1,...,n\}} d_{X}(f(i − 1), f(i))} = \frac{d_{X}(f(0), f(n))}{n∥f∥_{Lip}}.

If f is a constant mapping (equivalently max_{i∈{1,...,n}} d_{X}(f(i−1), f(i)) = 0) then we set T (X, f) = 0. Note that by the triangle inequality we always have T (X, f) ⩽ 1.

Lemma 5.2. For every m, n ∈ ℕ and f : P_{mn} → X, there exist rescaled isometries ϕ^{(n)} : P_{n} → P_{mn} and ϕ^{(m)} : P_{m} → P_{mn}, such that

T (X, f) ⩽ T (X, f ∘ ϕ^{(m)}) · T (X, f ∘ ϕ^{(n)}) .

Proof. Fix f : P_{mn} → X and define ϕ^{(m)} : P_{m} → P_{mn} by ϕ^{(m)}(i) = in. Then,

d_{X}(f(0), f(mn)) ⩽ T (X, f ∘ ϕ^{(m)}) m max_{i∈{1,...,m}} d_{X}(f((i − 1)n), f(in)).  (38)

Similarly, for every i ∈ {1, …, m} define ϕ_{i}^{(n)} : P_{n} → P_{mn} by ϕ_{i}^{(n)}(j) = (i − 1)n + j. Then

d_{X}(f((i − 1)n), f(in)) ⩽ T (X, f ∘ ϕ_{i}^{(n)}) n max_{j∈{1,...,n}} d_{X}(f((i − 1)n + j − 1), f((i − 1)n + j)). (39)

Letting i ∈ {1, …, m} be such that T (X, f ∘ ϕ_{i}^{(n)}) is maximal, and ϕ^{(n)} = ϕ_{i}^{(n)}, we conclude that

d_{X}(f(0), f(mn)) ⩽^{(38)∧(39)} T (X, f ∘ ϕ^{(m)}) T (X, f ∘ ϕ^{(n)}) mn max_{i∈{1,...,mn}} d_{X}(f(i − 1), f(i)).

Lemma 5.3. For every f : P_{m} → X we have dist(f) ⩾ 1/T (X, f).

Proof. Assuming a|i − j| ⩽ d_{X}(f(i), f(j)) ⩽ b|i − j| for all i, j ∈ P_{m}, the claim is bT (X, f) ⩾ a. Indeed, am ⩽ d_{X}(f(0), f(m)) ⩽ T (X, f)m max_{i=∈{1,...,m}} d_{X}(f(i − 1), f(i)) ⩽ T (X, f)bm.

Lemma 5.4. Fix f : P_{m} → X. If 0 < ε < 1/m and T (X, f) ⩾ 1 − ε, then dist(f) ⩽ 1/(1 − mε).

Proof. Denote b = max_{i∈{1,...,n}} d_{X}(f(i), f(i − 1)) > 0. For every 0 ⩽ i < j ⩽ m we have d_{X}(f(i), f(j)) ⩽ ∑_{ℓ=i+1}^{j} d_{X}(f(ℓ − 1), f(ℓ)) ⩽ b|j − i|, and

(1 − ε)mb ⩽ T (X, f)mb = d_{X}(f(0), f(m)) ⩽ d_{X}(f(0), f(i)) + d_{X}(f(i), f(j)) + d_{X}(f(j), f(m)) ⩽ d_{X}(f(i), f(j)) + b(m + i − j).

Thus d_{X}(f(i), f(j)) ⩾ b(j − i − mε) ⩾ (1 − mε)b|j − i|.

Proof of Proposition 5.1. Set k = ⌊log_{t} n⌋ and denote by I the identity mapping from P_{t^{k}} to P_{n}. By Lemma 5.3 we have T (X, f ∘ I) ⩾ 1/D. An iterative application of Lemma 5.2 implies that there exists a rescaled isometry ϕ : P_{t} → P_{t^{k}} such that

T (X, f ∘ I ∘ ϕ) ⩾ D^{−1/k} ⩾ e^{−2 log D/ log_{t} n} ⩾ e^{−δ/(2t)} ⩾ 1 − \frac{δ}{2t}.

By Lemma 5.4 we therefore have dist(f ∘ I ∘ ϕ) ⩽ 1/(1 − δ/2) ⩽ 1 + δ.

The second part of the proof of Theorem 1.14 uses the following combinatorial lemma due to Matoušek [18]. Denote by T_{k,m} the complete rooted tree of height m, in which every non-leaf vertex has k children. For a rooted tree T, denote by SP(T) the set of all unordered pairs {x, y} of distinct vertices of T such that x is an ancestor of y.

Lemma 5.5 ([18, Lem. 5]). Let m, r, k ∈ ℕ satisfy k ⩾ r^{(m+1)^{2}}. Suppose that each of the pairs from SP(T_{k,m}) is colored by one of r colors. Then there exists a copy T′ of B_{m} in this T_{k,m} such that the color of any pair {x, y} ∈ SP(T′) only depends on the levels of x and y.

Proof of Lemma 1.14. Let f : B_{n} → X be a D-vertically faithful embedding, i.e., for some λ > 0 it satisfies

λd_{B_{n}}(x, y) ⩽ d_{X}(f(x), f(y)) ⩽ Dλd_{B_{n}}(x, y)  (40)

whenever x, y ∈ B_{n} are such that x is an ancestor of y.

Let k, ℓ ∈ ℕ be auxiliary parameters to be determined later, and define m = ⌊n/(kℓ)⌋. We first construct a mapping g : T_{2^{k},m} → B_{n} in a top-down manner as follows. If r is the root of T_{2^{k},m} then g(r) is defined to be the root of B_{n}. Having defined g(u), let v_{1}, …, v_{2^{k}} ∈ T_{2^{k},m} be the children of u, and let w_{1}, …, w_{2^{k}} ∈ B_{n} be the descendants of g(u) at depth k below g(u). For each i ∈ {1, …, 2^{k}} let g(v_{i}) be an arbitrary descendant of w_{i} at depth h(g(u)) + ℓk. Note that for this construction to be possible we need to have mℓk ⩽ n, which is ensured by our choice of m.

By construction, if x, y ∈ T_{2^{k},m} and x is an ancestor of y, then g(x) is an ancestor of g(y) and d_{B_{n}}(g(x), g(y)) = ℓkd_{T_{2^{k},m}}(x, y). Also, if x, y ∈ T_{2^{k},m} and lca(x, y) = u, then we have h(lca(g(x), g(y))) ∈ {h(g(u)), h(g(u)) + 1, …, h(g(u)) + k − 1}. This implies that

((ℓ − 1)k + 1)d_{T_{2^{k},m}}(x, y) ⩽ d_{B_{n}}(x, y) ⩽ ℓkd_{T_{2^{k},m}}(x, y).

Thus, assuming ℓ ⩾ 2, we have dist(g) ⩽ 1 + 2/ℓ. Moreover, denoting F = f ∘ g and using (40), we see that if x, y ∈ T_{2^{k},m} are such that x is an ancestor of y then

kℓλd_{T_{2^{k},m}}(x, y) ⩽ d_{X}(F (x), F (y)) ⩽ Dℓkλd_{T_{2^{k},m}}(x, y).  (41)

Color every pair {x, y} ∈ SP(T_{2^{k},m}) with the color

χ(\{x, y\}) =^{def} ⌊log_{1+δ/4} (\frac{d_{X}(F (x), F (y))}{kℓλd_{T_{2^{k},m}}(x, y)})⌋ ∈ \{1, …, r\},

where r = ⌈log_{1+δ/4} D⌉. Assuming that

2^{k} ⩾ r^{(m+1)^{2}},  (42)

by Lemma 5.5 there exists a copy T′ of B_{m} in T_{2^{k},m} such that the colors of pairs {x, y} ∈ SP(T′) only depend on the levels of x and y.

Let P be a root-leaf path in T′ (isometric to P_{m}). The mapping F |_{P} : P → X has distortion at most D by (41). Assuming

m ⩾ D^{16(t log t)/δ},  (43)

by Proposition 5.1 there are {x_{i}}_{i=0}^{t} ⊆ P such that for some a, b ∈ ℕ with a, a + tb ∈ [0, m], for all i we have h(x_{i}) = a + ib, and for some θ > 0, for all i, j ∈ {0, …, t},

θb|i − j| ⩽ d_{X}(F (x_{i}), F (x_{j})) ⩽ (1 + \frac{δ}{4}) θb|i − j|.  (44)

Define a rescaled isometry φ : B_{t} → T′ in a top-down manner as follows: φ(r) = x_{0}, and having defined φ(u) ∈ T′, if v, w are the children of u in B_{t} and v′, w′ are the children of φ(u) in T′, the vertices φ(v), φ(w) are chosen as arbitrary descendants in T′ of v′, w′ (respectively) at depth h(φ(u)) + b. Consider the mapping G : B_{t} → X given by G = F ∘ φ = f ∘ g ∘ φ. Take x, y ∈ B_{t} such that x is an ancestor of y. Write h(x) = i and h(y) = j. Thus h(φ(x)) = a + ib and h(φ(y)) = a + jb. It follows that {φ(x), φ(y)} is colored by the same color as {x_{i}, x_{j}}, i.e.,

⌊log_{1+ \frac{δ}{4}} (\frac{d_{X}(G(x), G(y))}{kℓλbd_{B_{t}}(x, y)})⌋ = χ(\{φ(x), φ(y)\}) = χ(\{x_{i}, x_{j}\}) = ⌊log_{1+ \frac{δ}{4}} (\frac{d_{X}(F (x_{i}), F (y_{j}))}{kℓλbd_{B_{t}}(x, y)})⌋ .

Consequently, using (44) we deduce that

\frac{θb}{1 + δ/4}d_{B_{t}}(x, y) ⩽ d_{X}(G(x), G(y)) ⩽ (1 + \frac{δ}{4})^{2} θbd_{B_{t}}(x, y).

Thus G is a (1 + δ/4)^{3} ⩽ 1 + δ vertically faithful embedding of B_{t} into X.

It remains to determine the values of the auxiliary parameters ℓ, k, which will lead to the desired restriction on n given in (9). First of all, we want to have dist(g ∘ φ) ⩽ 1 + ξ. Since φ is a rescaled isometry and (for ℓ ⩾ 2) dist(g) ⩽ 1 + 2/ℓ, we choose ℓ = ⌈2/ξ⌉ ⩾ 2. We will choose k so that 4k ⩽ nξ, so that n/(kℓ) ⩾ 1. Since m = ⌊n/(kℓ)⌋, we have m + 1 ⩽ nξ/k and m ⩾ nξ/(4k). Recall that r = ⌈log_{1+δ/4} D⌉ ⩽ 2 log_{1+δ/4} D ⩽ 16D/δ. Hence the requirement (42) will be satisfied if

2^{k^{3}} ⩾ (\frac{16D}{δ} )^{n^{2}ξ^{2}} ,  (45)

and the requirement (43) will be satisfied if

\frac{nξ}{4k} ⩾ D^{16(t log t)/δ}.  (46)

There exists an integer k satisfying both (45) and (46) provided that

(n^{2}ξ^{2} log_{2} (\frac{16D}{δ} ))^{1/3} + 1 ⩽ \frac{nξ}{4D^{16(t log t)/δ}} ,

which holds true provided the constant c in (9) is large enough.

6 Tree metrics do not have the dichotomy property

This section is devoted to the proofs of Theorem 1.10 and Theorem 1.12. These proofs were outlined in Section 1.1.1, and we will use the notation introduced there.

6.1 Horizontally contracted trees

We start with the following lemma which supplies conditions on {ε_{n}}_{n=0}^{∞} ensuring that the H-tree (B_{∞}, d_{ε}) is a metric space.

Lemma 6.1. Assume that {ε_{n}}_{n=0}^{∞} ⊆ (0, 1] is non-increasing and {nε_{n}}_{n=0}^{∞} is non-decreasing. Then d_{ε} is a metric on B_{∞} Proof. Take x, y, z ∈ B_{∞} and without loss of generality assume that h(x) ⩽ h(y). We distinguish between the cases h(z) > h(y), h(x) ⩽ h(z) ⩽ h(y) and h(z) < h(x).

If h(z) > h(y) then

d_{ε}(x, z) + d_{ε}(z, y) − d_{ε}(x, y)

= 2[h(z) − h(y)] + 2ε_{h(x)} · [h(lca(x, y)) − h(lca(x, z))] + 2ε_{h(y)} · [h(y) − h(lca(z, y))]
⩾ 2ε_{h(x)} · [h(lca(x, y)) − h(lca(x, z))] + 2ε_{h(y)} · [h(y) − h(lca(z, y))] .  (47)

To show that (47) is non-negative observe that this is obvious if h(lca(x, y)) ⩾ h(lca(x, z)). So assume that h(lca(x, y)) < h(lca(x, z)). In this case necessarily h(lca(z, y)) = h(lca(x, y)), so we can bound (47) from below as follows

2ε_{h(x)} · [h(lca(x, y)) − h(lca(x, z))] + 2ε_{h(y)} · [h(y) − h(lca(z, y))]
⩾ 2ε_{h(x)} · [h(lca(x, y)) − h(x)] + 2\frac{h(x)}{h(y)}ε_{h(x)} · [h(y) − h(lca(x, y))]
= 2ε_{h(x)} · h(lca(x, y)) (1 − \frac{h(x)}{h(y)}) ⩾ 0.

If h(z) < h(x) then

d_{ε}(x, z) + d_{ε}(z, y) = h(x) + h(y) − 2h(z) + 2ε_{h(z)} · [2h(z) − h(lca(x, z)) − h(lca(z, y))]

⩾ h(y) − h(x) + 2ε_{h(x)} · [h(x) − h(z)] + 2ε_{h(x)} · [2h(z) − h(lca(x, z)) − h(lca(y, z))]
= h(y) − h(x) + 2ε_{h(x)} · [h(x) + h(z) − h(lca(x, z)) − h(lca(y, z))]
⩾ h(y) − h(x) + 2ε_{h(x)} · [h(x) − h(lca(x, y))]  (48)
= d_{ε}(x, y).

Where in (48) we used the fact that h(z) ⩾ h(lca(x, z)) + h(lca(y, z)) − h(lca(x, y)), which is true since h(lca(x, y)) ⩾ min {h(lca(x, z)), h(lca(y, z))}.

It remains to deal with the case h(x) ⩽ h(z) ⩽ h(y). In this case

d_{ε}(x, z) + d_{ε}(z, y) = h(y) − h(x) + 2ε_{h(x)} · [h(x) − h(lca(x, z))] + 2ε_{h(z)} · [h(z) − h(lca(y, z))]

⩾ h(y) − h(x) + 2ε_{h(x)} · [h(x) − h(lca(x, z))] + 2\frac{h(x)}{h(z)}ε_{h(x)} · [h(z) − h(lca(y, z))]
= h(y) − h(x) + 2ε_{h(x)} · [2h(x) − h(lca(x, z)) − \frac{h(x)}{h(z)}h(lca(y, z))]
⩾ h(y) − h(x) + 2ε_{h(x)} · [h(x) − h(lca(x, y))]  (49)
= d_{ε}(x, y),

where (49) is equivalent to the inequality

h(x) ⩾ h(lca(x, z)) + \frac{h(x)}{h(z)}h(lca(y, z)) − h(lca(x, y)).  (50)

To prove (50), note that it is true if h(lca(x, y)) ⩾ h(lca(x, z)), since clearly h(lca(y, z)) ⩽ h(z). If, on the other hand, h(lca(x, y)) < h(lca(x, z)) then using the assumption that h(z) ⩾ h(x) it is enough to show that h(x) ⩾ h(lca(x, z)) + h(lca(y, z)) − h(lca(x, y)). Necessarily h(lca(x, y)) = h(lca(y, z)), so that the required inequality follows from the fact that h(x) ⩾ h(lca(x, z)).

6.2 Geometry of H-trees

6.2.1 Classification of approximate midpoints

From now on we will always assume that ε = {ε_{n}}_{n=0}^{∞} satisfies for all n ∈ ℕ, ε_{n} ⩾ ε_{n+1} > 0 and (n + 1)ε_{n+1} ⩾ nε_{n}. We recall the important concept of approximate midpoints which is used frequently in nonlinear functional analysis (see [4] and the references therein).

Definition 6.2 (Approximate midpoints). Let (X, d_{X}) be a metric space and δ ∈ (0, 1). For x, y ∈ X the set of δ-approximate midpoints of x and z is defined as

Mid(x, z, δ) = \{y ∈ X : max\{d_{X}(x, y), d_{X}(y, z)\} ⩽ \frac{1 + δ}{2} · d_{X}(x, z)\} .

¿From now on, whenever we refer to the set Mid(x, z, δ), the underlying metric will always be understood to be d_{ε}. In what follows, given η > 0 we shall say that two sequences (u_{1}, …, u_{n}) and (v_{1}, …, v_{n}) of vertices in B_{∞} are η-near if for every j ∈ {1, …, n} we have d_{ε}(u_{j}, v_{j}) ⩽ η. We shall also require the following terminology:

Definition 6.3. An ordered triple (x, y, z) of vertices in B_{∞} will be called a path-type configuration if h(z) ⩽ h(y) ⩽ h(x), x is a descendant of y, and h(lca(z, y)) < h(y). The triple (x, y, z) will be called a tent-type configuration if h(y) ⩽ h(z), y is a descendant of x, and h(lca(x, z)) < h(x). These special configurations are described in Figure 3.

Figure 3: A schematic description of path-type and tent-type configurations.

The following useful theorem will be used extensively in the ensuing arguments. Its proof will be broken down into several elementary lemmas.

Theorem 6.4. Assume that δ ∈ (0, \frac{1}{16}), and the sequence ε = \{ε_{n}\}_{n=0}^{∞} satisfies ε_{n} < \frac{1}{4} for all n ∈ ℕ. Let x, y, z ∈ (B_{∞}, d_{ε}) be such that y ∈ Mid(x, z, δ). Then either (x, y, z) or (z, y, x) is 3δd_{ε}(x, z)-near a path-type or tent-type configuration.

In what follows, given a vertex v ∈ B_{∞} we denote the subtree rooted at v by T_{v}.

Lemma 6.5. Assume that ε_{n} ⩽ \frac{1}{2} for all n. Fix a ∈ B_{∞} and let u, v ∈ B_{∞} be its children. For every x, z ∈ T_{u} such that h(x) ⩾ h(z) consider the function D_{x,z} : {a} ∪ T_{v} → [0, ∞) defined by D_{x,z}(y) = d_{ε}(x, y)+d_{ε}(z, y). Fix an arbitrary vertex w ∈ T_{v} such that h(w) = h(z). Then for every y ∈ T_{v} we have D_{x,z}(y) ⩾ D_{x,z}(w).

Proof. By the definition of d_{ε} we have D_{x,z}(y) = Q(h(y)) where

Q(k) = max{h(x), k} + max{k, h(z)} − min{h(x), k} − min{k, h(z)} + 2ε_{min{h(x),k}} [min{h(x), k} − h(a)] + 2ε_{min{k,h(z)}} [min{k, h(z)} − h(a)] .

The required result will follow if we show that Q is non-increasing on {h(a), h(a) + 1, …, h(z)} and non-decreasing on {h(z), h(z) + 1, …}. If k ∈ {h(a), h(a) + 1, …, h(z) − 1} then

Q(k + 1) − Q(k) = −2 + 4ε_{k+1}[k + 1 − h(a)] − 4ε_{k}[k − h(a)] ⩽ −2 + 4ε_{k}[k + 1 − h(a)] − 4ε_{k}[k − h(a)] = −2(1 − 2ε_{k}) ⩽ 0.

If k ∈ {h(x), h(x) + 1, …} then Q(k + 1) − Q(k) = 2, and if k ∈ {h(z), …, h(x) − 1} then

Q(k + 1) − Q(k) = 2 [(k + 1)ε_{k+1} − kε_{k}] + 2h(a)[ε_{k} − ε_{k+1}] ⩾ 0.

This completes the proof of Lemma 6.5.

Lemma 6.6. Assume that ε_{n} < \frac{1}{2} for all n ∈ ℕ. Fix δ ∈ (0, \frac{1}{3}) and x, y, z ∈ B_{∞} such that h(x) ⩾ h(z), y ∈ Mid(x, z, δ) and h(lca(x, z)) > h(lca(x, y)). Then

h(z) + \frac{1 − 3δ}{2} d_{ε}(x, z) ⩽ h(y) < h(x) ⩽ h(y) + \frac{1 + 3δ}{1 − 3δ} [h(y) − h(z)].

Moreover, if y′ ∈ B_{∞} is the point on the segment joining x and lca(x, y) such that h(y′) = h(y) then d_{ε}(y, y′) ⩽ δd_{ε}(x, z). Thus (x, y′, z) is a path-type configuration which is δd_{ε}(x, z)-near (x, y, z)

Proof. Write a = lca(x, y). If u, v are the two children of a, then without loss of generality x, z ∈ T_{u} and y ∈ T_{v}. Let w ∈ T_{v} be such that h(w) = h(z).

By Lemma 6.5,

d_{ε}(x, y) + d_{ε}(z, y) ⩾ d_{ε}(x, w) + d_{ε}(z, w)

= h(x) − h(z) + 4ε_{h(z)}[h(z) − h(a)] ⩾ 2d_{ε}(x, z) − [h(x) − h(z)]. (51)

On the other hand, since y ∈ Mid(x, z, δ), we have that

d_{ε}(x, y) + d_{ε}(z, y) ⩽ (1 + δ)d_{ε}(x, z).

Additionally, by the definition of d_{ε} we know that if h(y) ⩽ h(z) then

\frac{1 + δ}{2} d_{ε}(x, z) ⩾ d_{ε}(x, y) ⩾ h(x) − h(y) ⩾ h(x) − h(z).

Combining these observations with (51) we get that

(1 + δ)d_{ε}(x, z) ⩾ 2d_{ε}(x, z) − \frac{1 + δ}{2} d_{ε}(x, z),  (52)

which is a contradiction since δ < \frac{1}{3}. Therefore h(y) > h(z). If h(y) ⩾ h(x) then

\frac{1 + δ}{2} d_{ε}(x, z) ⩾ d_{ε}(z, y) ⩾ h(y) − h(z) ⩾ h(x) − h(z),

so that we arrive at a contradiction as in (52). We have thus shown that h(z) < h(y) < h(x). Now, since y ∈ Mid(x, z, δ),

h(x) − h(z) + 2ε_{h(y)}[h(y) − h(a)] + 2ε_{h(z)}[h(z) − h(a)] = d_{ε}(x, y) + d_{ε}(z, y)

⩽ (1 + δ)d_{ε}(x, z) = (1 + δ) (h(x) − h(z) + 2ε_{h(z)}[h(z) − h(a)]) .

Thus, letting y′ be the point on the segment joining x and a such that h(y′) = h(y), we see that

d_{ε}(y, y′) = 2ε_{h(y)}[h(y) − h(a)] ⩽ δ (h(x) − h(z) + 2ε_{h(z)}[h(z) − h(a)]) = δd_{ε}(x, z),

Moreover

\frac{1 − δ}{2} d_{ε}(x, z) ⩽ d_{ε}(y, z) = h(y) − h(z) + 2ε_{h(z)}h(z) − 2ε_{h(z)}h(a)

⩽ h(y) − h(z) + 2ε_{h(y)}h(y) − 2ε_{h(y)}h(a) ⩽ h(y) − h(z) + δd_{ε}(x, z).

Thus

h(y) − h(z) ⩾ \frac{1 − 3δ}{2} d_{ε}(x, z).  (53)

Hence,

\frac{2}{1 − 3δ} [h(y) − h(z)] ⩾^{(53)} d_{ε}(x, z) = [h(x) − h(y)] + [h(y) − h(z)].

It follows that

h(x) − h(y) ⩽ \frac{1 + 3δ}{1 − 3δ} [h(y) − h(z)].

This completes the proof of Lemma 6.6.

Lemma 6.7. Assume that ε_{n} < \frac{1}{4} for all n ∈ ℕ. Fix δ ∈ (0, \frac{1}{16}) and assume that x, y, z ∈ B_{∞} are distinct vertices such that lca(x, y) = lca(x, z), and y ∈ Mid(x, z, δ). Then either (x, y, z) or (z, y, x) is 3δd_{ε}(x, z)-near a path-type or tent-type configuration.

Proof. Denote a = lca(x, y). Our assumption implies that h(lca(z, y)) ⩾ h(a). We perform a case analysis on the relative heights of x, y, z. Assume first that h(x) ⩽ h(y).

If h(x) ⩽ h(y) ⩽ h(z) then

(1 + δ)d_{ε}(x, z) ⩾ d_{ε}(x, y) + d_{ε}(y, z)
= h(y) − h(x) + 2ε_{h(x)}[h(x) − h(a)]
+ h(z) − h(y) + 2ε_{h(y)}[h(y) − h(lca(z, y))]
= d_{ε}(x, z) + 2ε_{h(y)}[h(y) − h(lca(z, y))].  (54)

Let y′ be the point on the path from lca(y, z) to z such that h(y′) = h(y). Then (54) implies that

d_{ε}(y, y′) = 2ε_{h(y)}[h(y) − h(lca(z, y))] ⩽ δd_{ε}(x, z).

Thus the triple (z, y′, x) is a configuration of path-type which is δd_{ε}(x, z)-near (z, y, x).

If h(x) ⩽ h(z) ⩽ h(y) then since

\frac{1 + δ}{2} d_{ε}(x, z) ⩾ d_{ε}(x, y) = h(y) − h(x) + 2ε_{h(x)}[h(x) − h(a)]

and d_{ε}(x, z) = h(z) − h(x) + 2ε_{h(x)}[h(x) − h(a)] we deduce that

−\frac{1 − δ}{2} d_{ε}(x, z) ⩾ d_{ε}(x, y) − d_{ε}(x, z) = h(y) − h(z) ⩾ 0.

It follows that x = z, in contradiction to our assumption.

If h(z) < h(x) then let z′ be the point on the segment joining a and y such that h(z′) = h(z). We thus have that

d_{ε}(z, z′) = 2ε_{h(z)}[h(z) − h(lca(y, z))] = d_{ε}(z, y) − [h(y) − h(z)].

Moreover,

2ε_{h(z)}[h(lca(z, y)) − h(a)] = d_{ε}(x, z) − [h(x) − h(z)] − 2ε_{h(z)}[h(z) − h(lca(z, y))]

⩾ \frac{2}{1 + δ} d_{ε}(z, y) − [h(x) − h(z)] − 2ε_{h(z)}[h(z) − h(lca(z, y))]

= \frac{2}{1 + δ} (h(y) − h(z) + 2ε_{h(z)}[h(z) − h(lca(y, z))])

− (h(y) − h(z) + 2ε_{h(z)}[h(z) − h(lca(y, z))]) + [h(y) − h(x)]

= \frac{1 − δ}{1 + δ} d_{ε}(y, z) + [h(y) − h(x)]

⩾ \frac{1 − δ}{1 + δ} · \frac{1 − δ}{2} d_{ε}(x, z) + [h(y) − h(x)]

⩾ (\frac{1 − δ}{1 + δ} )^{2} d_{ε}(x, y) + [h(y) − h(x)]

= d_{ε}(x, y) + [h(y) − h(x)] − \frac{4δ}{(1 + δ)^{2}} d_{ε}(x, y)

= 2[h(y) − h(x)] + 2ε_{h(x)}[h(x) − h(a)] − \frac{4δ}{(1 + δ)^{2}} d_{ε}(x, y)

⩾ 2[h(y) − h(x)] + 2ε_{h(z)}h(z) − 2ε_{h(z)}h(a) − \frac{2δ}{1 + δ} d_{ε}(x, z).

Thus

\frac{2δ}{1 + δ} d_{ε}(x, z) ⩾ 2[h(y) − h(x)] + 2ε_{h(z)}[h(z) − h(lca(y, z))] = 2[h(y) − h(x)] + d_{ε}(z, z′). (55)

Let y′ be the point on the path from a to y such that h(y′) = h(x). It follows from (55) that the triple (z′, y′, x) is a configuration of tent-type which is 2δd_{ε}(x, z)-near (z, y, x).

This completes the proof of Lemma 6.7 when h(x) ⩽ h(y). The case h(x) > h(y) is proved analogously. Here are the details.

Assume first of all that h(z) ⩾ h(x) > h(y). Then,

d_{ε}(x, z) ⩾ \frac{2}{1 + δ} d_{ε}(z, y) = 2d_{ε}(z, y) − \frac{2δ}{1 + δ} d_{ε}(z, y)

= 2 (h(z) − h(y) + 2ε_{h(y)}[h(y) − h(lca(z, y))]) − \frac{2δ}{1 + δ} d_{ε}(z, y)

⩾ 2 (h(z) − h(y) + 2ε_{h(y)}[h(y) − h(lca(z, y))]) − δd_{ε}(x, z). (56)

On the other hand, since h(x) > h(y),

d_{ε}(x, z) = h(z) − h(x) + 2ε_{h(x)}[h(x) − h(a)]
⩽ h(z) − h(x) + 2ε_{h(y)}[h(x) − h(a)]
= (h(x) − h(y) + 2ε_{h(y)}[h(y) − h(a)]) + h(y) + h(z) − 2h(x) + 2ε_{h(y)}[h(x) − h(y)]
= d_{ε}(x, y) + h(y) + h(z) − 2h(x) + 2ε_{h(y)}[h(x) − h(y)]
⩽ \frac{1 + δ}{1 − δ} d_{ε}(y, z) + h(y) + h(z) − 2h(x) + 2ε_{h(y)}[h(x) − h(y)]
= (h(z) − h(y) + 2ε_{h(y)}[h(y) − h(lca(z, y))]) + \frac{2δ}{1 − δ} d_{ε}(y, z)
+h(y) + h(z) − 2h(x) + 2ε_{h(y)}[h(x) − h(y)]
⩽ 2[h(z) − h(x)] + 2ε_{h(y)}[h(x) − h(lca(z, y))] + \frac{1+δ}{1−δ} δd_{ε}(x, z).

Combining this bound with (56), and canceling terms, gives

\frac{2δ}{1 − δ} d_{ε}(x, z) ⩾ 2[h(x) − h(y)] − 4ε_{h(y)}[h(x) − h(y)] + 2ε_{h(y)}[h(x) − h(lca(z, y))]
⩾ 2 (1 − 2ε_{h(y)}) [h(x) − h(y)] + 2ε_{h(y)}[h(x) − h(lca(z, y))]
> [h(x) − h(y)] + 2ε_{h(y)}[h(x) − h(lca(z, y))],  (57)

where we used the fact that ε_{h(y)} < \frac{1}{4}. Let x′ be the point on the path from x to a such that h(x′) = h(y), and let y′ be the point on the path from a to z such that h(y′) = h(y). Then by (57) d_{ε}(x, x′) = h(x) − h(y) ⩽ 3δd_{ε}(x, z) and

d_{ε}(y, y′) = 2ε_{h(y)}[h(y) − h(lca(z, y))] ⩽ 2ε_{h(y)}[h(x) − h(lca(z, y))] ⩽ 3δd_{ε}(x, z).

Thus the triple (z, y′, x′) is a configuration of path-type which is 3δd_{ε}(x, z)-near (z, y, x). If h(x) > h(z) ⩾ h(y) then

h(z) − h(y) + 2ε_{h(y)}[h(y) − h(lca(z, y))] = d_{ε}(z, y) ⩾ \frac{1 − δ}{1 + δ} d_{ε}(x, y)

= d_{ε}(x, y)−\frac{2δ}{1 + δ} d_{ε}(x, y) = h(x)−h(y)+2ε_{h(y)}[h(y)−h(a)]−\frac{2δ}{1 + δ} d_{ε}(x, y).

Canceling terms we see that

\frac{2δ}{1 + δ} d_{ε}(x, y) ⩾ h(x) − h(z) + 2ε_{h(y)}[h(lca(z, y)) − h(a)]
= h(x) − h(z) + 2ε_{h(y)}[h(z) − h(a)] − 2ε_{h(y)}[h(z) − h(lca(z, y))]
⩾ h(x) − h(z) + 2ε_{h(z)}[h(z) − h(a)] − 2ε_{h(y)}[h(z) − h(lca(z, y))]
= d_{ε}(x, z) − 2ε_{h(y)}[h(z) − h(lca(z, y))]

⩾ 2d_{ε}(z, y) − \frac{2δ}{1 + δ} d_{ε}(x, z) − 2ε_{h(y)}[h(z) − h(lca(z, y))]

= 2 (h(z) − h(y) + 2ε_{h(y)}[h(y) − h(lca(z, y))]) − \frac{2δ}{1 + δ} d_{ε}(x, z)

− 2ε_{h(y)}[h(z) − h(lca(z, y))]

= 2 (1 − 2ε_{h(y)}) [h(z) − h(y)] + 2ε_{h(y)}[h(z) − h(lca(z, y))] − \frac{2δ}{1 + δ} d_{ε}(x, z)

⩾ [h(z) − h(y)] + 2ε_{h(y)}[h(z) − h(lca(z, y))] − \frac{2δ}{1 + δ} d_{ε}(x, z)

= d_{ε}(z, y) − \frac{2δ}{1 + δ} d_{ε}(x, z)

⩾ (\frac{1 − δ}{2} − \frac{2δ}{1 + δ} ) d_{ε}(x, z),

which is a contradiction since δ < \frac{1}{16}.

The only remaining case is when h(x) > h(y) > h(z). In this case we proceed as follows.

d_{ε}(x, z) = h(x) − h(z) + 2ε_{h(z)}[h(z) − h(a)]

= d_{ε}(y, z) + [h(x) − h(y)] + 2ε_{h(z)}[h(lca(y, z)) − h(a)]

⩾ d_{ε}(x, y) − \frac{2δ}{1 + δ} d_{ε}(x, y) + [h(x) − h(y)] + 2ε_{h(z)}[h(lca(y, z)) − h(a)]

⩾ h(x) − h(y) + 2ε_{h(y)}[h(y) − h(a)] − δd_{ε}(x, z)

+ [h(x) − h(y)] + 2ε_{h(z)}[h(lca(y, z)) − h(a)]

⩾ 2[h(x) − h(y)] + 2ε_{h(z)}[h(z) − h(a)] + 2ε_{h(z)}[h(lca(y, z)) − h(a)] − δd_{ε}(x, z)

= 2[h(x) − h(y)] + 4ε_{h(z)}[h(z) − h(a)] − 2ε_{h(z)}[h(z) − h(lca(y, z))] − δd_{ε}(x, z)

= 2d_{ε}(x, z) − 2d_{ε}(z, y) + 2ε_{h(z)}[h(z) − h(lca(y, z))] − δd_{ε}(x, z)

⩾ (1 − 2δ) d_{ε}(x, z) + 2ε_{h(z)}[h(z) − h(lca(y, z))].  (58)

Let z′ be the point on the path from a to y such that h(z′) = h(z). Then

d_{ε}(z, z′) = 2ε_{h(z)}[h(z) − h(lca(y, z))] ⩽^{(58)} 2δd_{ε}(x, z).

Therefore the triple (z′, y, x) is of tent-type and is 2δd_{ε}(x, z)-near (z, y, x). The proof of Lemma 6.7 is complete.

Proof of Theorem 6.4. It remains to check that for every x, y, z ∈ B_{∞} such that y ∈ Mid(x, z, δ), at least one of the triples (x, y, z) or (z, y, x) satisfies the conditions of Lemma 6.6 or Lemma 6.7.

Indeed, if h(lca(x, y)) = h(lca(x, z)) then lca(x, y) = lca(x, z), so Lemma 6.7 applies. If h(lca(x, y)) < h(lca(x, z)) then lca(z, y) = lca(x, z), so Lemma 6.7 applies to the triple (z, y, x). If h(lca(x, y)) < h(lca(x, z)) then lca(x, y) = lca(z, y), and so h(lca(x, z)) > h(lca(z, y)). Hence Lemma 6.6 applies to either the triple (x, y, z) or the triple (z, y, x).

We end this subsection with a short discussion on the distance between tent-type and path-type configurations. It turns out that when ε_{h} ≪ δ, a δ-midpoint configuration (x, y, z) can be close to a path-type configuration, and at the same time the reversed triple (z, y, x) close to a tent-type configuration (or vice versa). However, it is easy to see that this is the only “closeness” possible.

Lemma 6.8. Fix x, y, z ∈ B_{∞} with x ≠ y. Then the following statements are impossible:

1. (x, y, z) is \frac{1}{5}d_{ε}(x, y)-near a path-type configuration and a tent-type configuration.

2. (x, y, z) is \frac{1}{11}d_{ε}(x, y)-near a path-type configuration and (z, y, x) is \frac{1}{11}d_{ε}(x, y)-near a path-type configuration.

3. (x, y, z) is \frac{1}{11}d_{ε}(x, y)-near a tent-type configuration and (z, y, x) is \frac{1}{11}d_{ε}(x, y)-near a tent-type configuration.

Proof. For case 1 of Lemma 6.8, assume for contradiction that (x, y, z) is \frac{1}{5}d_{ε}(x, y)-near a pathtype configuration (a_{1}, b_{1}, c_{1}), and also \frac{1}{5}d_{ε}(x, y)-near a tent-type configuration (α_{1}, β_{1}, γ_{1}). By the definitions of path-type and tent-type configurations, a_{1} is a descendant of b_{1} and β_{1} is a descendant of α_{1}. Hence,

h(a_{1}) − h(b_{1}) = d_{ε}(a_{1}, b_{1}) ⩾ d_{ε}(x, y) − d_{ε}(x, a_{1}) − d_{ε}(y, b_{1}) ⩾ \frac{3}{5}d_{ε}(x, y),  (59)

and

h(β_{1}) − h(α_{1}) = d_{ε}(α_{1}, β_{1}) ⩾ d_{ε}(x, y) − d_{ε}(x, α_{1}) − d_{ε}(y, β_{1}) ⩾ \frac{3}{5}d_{ε}(x, y).  (60)

By summing (59) and (60) we see that,

\frac{4}{5}d_{ε}(x, y) ⩾ d_{ε}(a_{1}, x) + d_{ε}(x, α_{1}) + d_{ε}(b_{1}, y) + d_{ε}(y, β_{1}) ⩾ d_{ε}(a_{1}, α_{1}) + d_{ε}(b_{1}, β_{1})

⩾ h(a_{1}) − h(α_{1}) + h(β_{1}) − h(b_{1}) ⩾^{(59)∧(60)} \frac{6}{5}d_{ε}(x, y),

a contradiction.

For case 2 of Lemma 6.8, assume for contradiction that (x, y, z) is \frac{1}{11}d_{ε}(x, y)-near a path-type configuration (a_{2}, b_{2}, c_{2}), and also (z, y, x) is \frac{1}{11}d_{ε}(x, y)-near a path-type configuration (α_{2}, β_{2}, γ_{2}). By the definitions of path-type and tent-type configurations, a_{2} is a descendant of b_{2} and h(β_{2}) > h(γ_{2}). Hence,

h(a_{2}) − h(b_{2}) = d_{ε}(a_{2}, b_{2}) ⩾ d_{ε}(x, y) − d_{ε}(x, a_{2}) − d_{ε}(y, b_{2}) ⩾ \frac{9}{11}d_{ε}(x, y),  (61)

and

h(β_{2}) − h(γ_{2}) + 2ε_{h(γ_{2})}[h(γ_{2}) − h(lca(β_{2}, γ_{2}))] = d_{ε}(β_{2}, γ_{2})

⩾ d_{ε}(x, y) − d_{ε}(x, γ_{2}) − d_{ε}(y, β_{2}) ⩾ \frac{9}{11}d_{ε}(x, y). (62)

By summing (61) and (62) we see that

\frac{17}{11}d_{ε}(x, y)  ⩾  d_{ε}(a_{2}, x) + d_{ε}(x, γ_{2}) + d_{ε}(b_{2}, y) + d_{ε}(y, β_{2}) + d_{ε}(β_{2}, y) + d_{ε}(x, y) + d_{ε}(x, γ_{2})
⩾  d_{ε}(a_{2}, γ_{2}) + d_{ε}(b_{2}, β_{2}) + d_{ε}(β_{2}, γ_{2})
⩾  (h(a_{2}) − h(γ_{2})) + (h(β_{2}) − h(b_{2})) + 2ε_{h(γ_{2})}[h(γ_{2}) − h(lca(β_{2}, γ_{2}))]
⩾^{(61)∧(62)} \frac{18}{11}d_{ε}(x, y),

a contradiction.

For case 3 of Lemma 6.8, assume for contradiction that (x, y, z) is \frac{1}{11}d_{ε}(x, y)-near a tent-type configuration (a_{3}, b_{3}, c_{3}), and also (z, y, x) is \frac{1}{11}d_{ε}(x, y)-near a tent-type configuration (α_{3}, β_{3}, γ_{3}). Then b_{3} is a descendant of a_{3} and h(γ_{3}) > h(β_{3}). Hence,

h(b_{3}) − h(a_{3}) = d_{ε}(a_{3}, b_{3}) ⩾ d_{ε}(x, y) − d_{ε}(x, a_{3}) − d_{ε}(y, b_{3}) ⩾ \frac{9}{11}d_{ε}(x, y),  (63)

and

h(γ_{3}) − h(β_{3}) + 2ε_{h(β_{3})}[h(β_{3}) − h(lca(β_{3}, γ_{3}))] = d_{ε}(β_{3}, γ_{3})

⩾ d_{ε}(x, y) − d_{ε}(x, γ_{3}) − d_{ε}(y, β_{3}) ⩾ \frac{9}{11}d_{ε}(x, y). (64)

Hence,

\frac{17}{11}d_{ε}(x, y)  ⩾  d_{ε}(b_{3}, y) + d_{ε}(y, β_{3}) + d_{ε}(x, α_{3}) + d_{ε}(x, γ_{3}) + d_{ε}(β_{3}, y) + d_{ε}(x, y) + d_{ε}(x, γ_{3})
⩾  d_{ε}(b_{3}, β_{3}) + d_{ε}(a_{3}, γ_{3}) + d_{ε}(β_{3}, γ_{3})
⩾  (h(b_{3}) − h(β_{3})) + (h(γ_{3}) − h(a_{3})) + 2ε_{h(β_{3})}[h(β_{3}) − h(lca(β_{3}, γ_{3}))]
⩾^{(63)∧(64)} \frac{18}{11}d_{ε}(x, y),

a contradiction.

6.2.2 Classification of approximate forks

We begin with three “stitching lemmas” that roughly say that given three points x, x′, y ∈ (B_{∞}, d_{ε}) such that x′ is near x, there exists y′ near y such that d_{ε}(x′, y′) is close to d_{ε}(x, y), and y′ relates to x′ in B_{∞} “in the same way” that y relates x in B_{∞}.

Lemma 6.9. Let x, x′, y, y′ ∈ B_{∞} be such that y is an ancestor of x, and y′ is an ancestor of x′ satisfying h(x) − h(y) = h(x′) − h(y′). Then d_{ε}(y, y′) ⩽ d_{ε}(x, x′).

Proof. Assume without loss of generality that h(x) ⩾ h(x′). So,

d_{ε}(x, x′) = h(x) − h(x′) + 2ε_{h(x′)}[h(x′) − h(lca(x, x′))].

Note that h(lca(y, y′)) = min{h(y′), h(lca(x, x′))}. Hence,

d_{ε}(y, y′) = h(y) − h(y′) + 2ε_{h(y′)}[h(y′) − h(lca(y, y′))]
= h(x) − h(x′) + 2ε_{h(y′)}[h(y′) − min{h(y′), h(lca(x, x′))}]
= h(x) − h(x′) + 2ε_{h(y′)} max{0, h(y′) − h(lca(x, x′))}.  (65)

If the maximum in (65) is 0, then

d_{ε}(y, y′) = h(x) − h(x′) ⩽ d_{ε}(x, x′).

If the maximum in (65) equals h(y′) − h(lca(x, x′)), then

d_{ε}(y, y′) = h(x) − h(x′) + 2ε_{h(y′)}[h(y′) − h(lca(x, x′))]

⩽ h(x) − h(x′) + 2ε_{h(x′)}[h(x′) − h(lca(x, x′))] = d_{ε}(x, x′), (66)

where in (66) we used the fact that the sequence {ε_{n}(n − a)}_{n=0}^{∞} is nondecreasing for all a ⩾ 0.

Lemma 6.10. Let x, x′, y ∈ B_{∞} be such that h(y) ⩽ h(x). Then there exists y′ ∈ B_{∞} which satisfies h(y′) − h(x′) = h(y) − h(x),

d_{ε}(y, y′) ⩽ d_{ε}(x, x′),  (67)

and

d_{ε}(x, y) − 2d_{ε}(x, x′) ⩽ d_{ε}(y′, x′) ⩽ d_{ε}(x, y) + 2d_{ε}(x, x′).  (68)

Proof. Note that (68) follows from (67) by the triangle inequality. Assume first that h(x) ⩾ h(x′). In this case choose y′ to be an ancestor of y satisfying h(y) − h(y′) = h(x) − h(x′). Then,

d_{ε}(y, y′) = h(y) − h(y′) = h(x) − h(x′) ⩽ d_{ε}(x, x′).

We next assume that h(x) < h(x′). If h(lca(x, x′)) ≠ h(lca(x, y)) then choose y′ to be an arbitrary descendant of y such that h(y′) − h(y) = h(x′) − h(x). As before, we conclude that d_{ε}(y, y′) = h(y′) − h(y) = h(x′) − h(x) ⩽ d_{ε}(x, x′).

It remains to deal with the case h(x′) > h(x) and h(lca(x, y)) = h(lca(x′, x)), which also implies that h(lca(x′, y)) > h(lca(x, y)). In this case, we choose y′ to be an arbitrary point on a branch containing both lca(x, y) and x, such that h(y′) − h(y) = h(x′) − h(x). Then lca(y′, y) = lca(x, x′), and therefore,

d_{ε}(y, y′) = h(y′) − h(y) + 2ε_{h(y)}[h(y) − h(lca(y, y′)]
= h(x′) − h(x) + 2ε_{h(y)}[h(y) − h(lca(x, x′))]
⩽ h(x′) − h(x) + 2ε_{h(x)}[h(x) − h(lca(x, x′))]
= d_{ε}(x, x′),

proving (67) in the last remaining case.

Lemma 6.11. Let x, x′, y ∈ B_{∞} be such that y is a descendant of x. Then for any y′ ∈ B_{∞} which is a descendant of x′ and satisfying h(y′) − h(x′) = h(y) − h(x), we have

d_{ε}(y, y′) ⩽ d_{ε}(x, x′) + 2ε_{min{h(y′),h(y)}}[h(y) − h(x)] ⩽ d_{ε}(x, x′) + 2ε_{h(y)}[h(y) − h(x) + d_{ε}(x, x′)].

Proof. Note that h(lca(y, y′)) ⩾ h(lca(x, x′)). Assume first that h(x′) ⩾ h(x). Then,

d_{ε}(y, y′) = h(y′) − h(y) + 2ε_{h(y)}[h(y) − h(lca(y, y′))]
= h(x′) − h(x) + 2ε_{h(y)}[h(x) − h(lca(y, y′))] + 2ε_{h(y)}[h(y) − h(x)]
⩽ h(x′) − h(x) + 2ε_{h(y)}[h(x) − h(lca(x, x′)] + 2ε_{h(y)}[h(y) − h(x)]
⩽ d_{ε}(x, x′) + 2ε_{h(y)}[h(y) − h(x)].

When h(x′) < h(x), we similarly obtain the bound:

d_{ε}(y, y′) = h(y) − h(y′) + 2ε_{h(y′)}[h(y′) − h(lca(y, y′))]
= h(x) − h(x′) + 2ε_{h(y′)}[h(x′) − h(lca(y, y′))] + 2ε_{h(y′)}[h(y′) − h(x′)]
⩽ d_{ε}(x, x′) + 2ε_{h(y′)}[h(y) − h(x)].

The last inequality in the statement of Lemma 6.11 is proved by observing that when h(y′) < h(y),

ε_{h(y′)}[h(y) − h(x)] = ε_{h(y′)}[h(y′) − h(x′)] ⩽ ε_{h(y)}[h(y) − h(x′)] ⩽ ε_{h(y)}[h(y) − h(x) + d_{ε}(x, x′)].

Definition 6.12. For δ ∈ (0, 1) and x, y, z, w ∈ B_{∞}, the quadruple (x, y, z, w) is called a δ-fork, if

y ∈ Mid(x, z, δ) ∩ Mid(x, w, δ).

δ-forks in H-trees can be approximately classified using the approximate classification of midpoint configurations of Section 6.2.1. We have four types of midpoint configurations (recall Figure 3):

• path-type; denoted (P) in what follows,

• reverse path-type; denoted (p)—(x, y, z) is of type (p) iff (z, y, x) is of type (P),

• tent-type; denoted (T),

• reverse tent-type; denoted (t)—(x, y, z) is of type (t) iff (z, y, x) is of type (T).

Thus, there are \binom{5}{2} = 10 possible δ-fork configurations in (B_{∞}, d_{ε}) (choose two out of the five symbols “P”,“p”,“T”,“t”,“X”, where “X” means “the same”). As we shall see, four of these possible configurations are impossible, two of them have large contraction of the prongs of the forks, i.e., d_{ε}(z, w) ≪ d_{ε}(x, y), which immediately implies large distortion, and the rest of the configurations are problematic in the sense that they are not much distorted from the star K_{1,3} (the metric d on four points p, q, r, s given by d(p, q) = d(q, r) = d(q, s) = 1 and d(p, s) = d(p, r) = d(r, s) = 2). The 10 possible δ-fork configurations are summarized in Table 1.

Midpoint configuration Type
(T∥T)  Type I
(P∥P)  Type II
(p∥T)  Type III
(p∥t)  Type IV
(p∥p)  prongs contracted
(t∥t)  prongs contracted
(P∥p)  impossible
(P∥t)  possible only as approximate type II
(P∥T)  impossible
(t∥T)  impossible

Table 1: The ten possible fork configurations.

For future reference, we give names to the four problematic configurations:

Definition 6.13. For η, δ ∈ (0, 1), a δ-fork (x, y, z, w) of (B_{∞}, d_{ε}) is called

• η-near Type I (configuration (T∥T)) in Table 1), if both (x, y, z) and (x, y, w) are η-near tent-type configurations;

• η-near Type II (configuration (P∥P) in Table 1), if both (x, y, z) and (x, y, w) are η-near path-type configurations;

• η-near Type III (configuration (p∥T) in Table 1), if (z, y, x) is η-near a path-type configuration and (x, y, w) is η-near a tent-type configuration, or vice versa;

• η-near Type IV (configuration (p∥t) in Table 1), if (z, y, x) is η-near a path-type configuration and (w, y, x) is η-near a tent-type configuration, or vice versa.

A schematic description of the four problematic configurations is contained in Figure 4.

Figure 4: The four “problematic” types of δ-forks.

The following lemma is the main result of this section.

Lemma 6.14. Fix δ ∈ (0, \frac{1}{70}) and assume that ε_{n} < \frac{1}{4} for all n ∈ ℕ. If (x, y, z, w) is a δfork of (B_{∞}, d_{ε}) then either it is 35δd_{ε}(x, y)-near one of the types I, II, III, IV, or we have d_{ε}(z, w) ⩽ 2(35δ + ε_{h_{0}})d_{ε}(x, y), where h_{0} = min{h(x), h(y), h(z), h(w)}.

Remark 6.15. One can strengthen the statement of Lemma 6.14 so that in the first case the fork (x, y, z, w) is O(δd_{ε}(x, y)) near another fork (x′, y′, z′, w′) which is of (i.e. 0-near) one of the types I, II, III, IV. This statement is more complicated to prove, and since we do not actually need it in what follows, we opted to use a weaker property which suffices for our purposes, yet simplifies (the already quite involved) proof.

The proof of Lemma 6.14 proceeds by checking that the cases marked in Table 1 as “impossible” or “prongs contracted” are indeed so—see Figure 5 for a schematic description of the latter case.

We begin with the (p∥p) configuration.

Lemma 6.16. Let (x, y, z, w) be a δ-fork of (B_{∞}, d_{ε}) and assume that both (z, y, x), and (w, y, x) are ηd_{ε}(x, y)-near path-type configurations. Then, assuming that max\{δ, η\} < 1/8 and ε_{n} < \frac{1}{4} for all n, we have

d_{ε}(z, w) ⩽ (9η + 6δ + 2ε_{h(y)}) d_{ε}(x, y).

Figure 5: The two configurations of δ-forks with large contraction of the prongs.

Proof. Let (z′, y′, x′) be a path-type configuration that is ηd_{ε}(x, y)-near (z, y, x), and let (w′′, y′′, x′′) be a path-type configuration that is ηd_{ε}(x, y)-near (w, y, x). Without loss of generality assume that h(y′′) ⩾ h(y′). Let w′ be the descendant of y′ satisfying h(w′) − h(y′) = h(w′′) − h(y′′) such that w′ is either an ancestor or an arbitrary descendant of z′. Note that h(w′) ⩾ h(y). Indeed,

h(w′) = h(y′) + h(w′′) − h(y′′) = h(y′) + d_{ε}(w′′, y′′) ⩾ h(y) − |h(y) − h(y′)| + d_{ε}(w, y) − 2ηd_{ε}(x, y)

⩾ h(y) − d_{ε}(y, y′) + \frac{1 − δ}{1 + δ} d_{ε}(x, y) − 2ηd_{ε}(x, y) ⩾ h(y) + (\frac{1 − δ}{1 + δ} − 3η) d_{ε}(x, y) ⩾ h(y).

By Lemma 6.11,

d_{ε}(w′, w′′) ⩽ d_{ε}(y′, y′′) + 2ε_{h(w′)} [h (w′′) − h (y′′)] ⩽ d_{ε}(y′, y′′) + 2ε_{h(w′)}d_{ε}(y′′, w′′)

⩽ 2ηd_{ε}(x, y) + 2ε_{h(y)} (2η + \frac{1 + δ}{1 − δ} ) d_{ε}(x, y). (69)

Observe that

(\frac{1 − δ}{1 + δ} − 2η) d_{ε}(x, y) ⩽ d_{ε}(z, y) − 2ηd_{ε}(x, y) ⩽ d_{ε}(z′, y′)

⩽ d_{ε}(z, y) + 2ηd_{ε}(x, y) ⩽ (\frac{1 + δ}{1 − δ} + 2η) d_{ε}(x, y), (70)

Since d_{ε}(w′, y′) = d_{ε}(w′′, y′′), we obtain similarly the bounds:

(\frac{1 − δ}{1 + δ} − 2η) d_{ε}(x, y) ⩽ d_{ε}(w′, y′) ⩽ d_{ε}(z, y) + 2ηd_{ε}(x, y) ⩽ (\frac{1 + δ}{1 − δ} + 2η) d_{ε}(x, y).  (71)

Hence

d_{ε}(z′, w′) = |d_{ε}(y′, z′) − d_{ε}(y′, w′)| ⩽^{(70)∧(71)} (\frac{4δ}{1 − δ^{2}} + 4η) d_{ε}(x, y).  (72)

So, in conclusion,

d_{ε}(z, w) ⩽ d_{ε}(z, z′) + d_{ε}(w, w′′) + d_{ε}(w′′, w′) + d_{ε}(z′, w′)

⩽^{(69)∧(72)} (8η + \frac{4δ}{1 − δ^{2}} + 2 (2η + \frac{1 + δ}{1 − δ} ) ε_{h(y)}) d_{ε}(x, y) ⩽ (9η + 6δ + 2ε_{h(y)}) d_{ε}(x, y).

We next consider the (t∥t) configuration.

Lemma 6.17. Let (x, y, z, w) be a δ-fork of (B_{∞}, d_{ε}). Assume that both (z, y, x) and (w, y, x) are ηd_{ε}(x, y)-near tent-type configurations. Then, assuming that max{δ, η} < 1/4, we have

d_{ε}(z, w) ⩽ (8η + 5δ)d_{ε}(x, y).

Proof. Let (z′, y′, x′) be a tent-type configuration that is ηd_{ε}(x, y)-near (z, y, x), and let (w′′, y′′, x′′) be a tent-type configuration that is ηd_{ε}(x, y)-near (w, y, x). Assume without loss of generality that h(y′′) − h(w′′) ⩾ h(y′) − h(z′). Let w̃ be a point on the path between w′′ and y′′ such that h(y′′) − h(w̃) = h(y′) − h(z′). Then,

d_{ε}(w′′, w̃) = h(y′′) − h(w′′) − (h(y′) − h(z′)) = d_{ε}(y′′, w′′) − d_{ε}(y′, z′)

⩽ d_{ε}(y, w) − d_{ε}(y, z) + 4ηd_{ε}(x, y) ⩽ (\frac{1 + δ}{1 − δ} − \frac{1 − δ}{1 + δ} + 4η) d_{ε}(x, y). (73)

By Lemma 6.9 we have d_{ε}(w̃, z′) ⩽ d_{ε}(y′, y′′) ⩽ 2ηd_{ε}(x, y). Hence we conclude that

d_{ε}(y, z) ⩽ d_{ε}(z, z′) + d_{ε}(w̃, z′) + d_{ε}(w̃, w′′) + d_{ε}(w′′, w) ⩽^{(73)} (\frac{4δ}{1 − δ^{2}} + 8η) d_{ε}(x, y).

Lemma 6.18. Let (x, y, z, w) be a δ-fork of B_{∞}. Assume that (x, y, z) is ηd_{ε}(x, y)-near a path-type configuration. Assume also that δ < 1/30, η < 1/10, and ε_{n} < 1/4 for all n. Then (x, y, w) is (2η + 21δ)d_{ε}(x, y)-near a path-type configuration, i.e., (x, y, z, w) is (2η + 21δ)d_{ε}(x, y)-near a type II configuration.

Proof. Let (x′, y′, z′) be a path-type configuration which is ηd_{ε}(x, y)-near (x, y, z). By Theorem 6.4, either (x, y, w) or (w, y, x) must be 3δd_{ε}(x, z) ⩽ \frac{6}{1−δ} d_{ε}(x, y) ⩽ 7δd_{ε}(x, y)-near either a path-type configuration or a tent-type configuration.

Suppose first that (x, y, w) is 7δd_{ε}(x, y)-near a tent-type configuration (x′′, y′′, w′′). In this case, x′′ is an ancestor of y′′ and h(y′′) − h(x′′) = d_{ε}(x′′, y′′) ⩾ (1 − 14δ)d_{ε}(x, y). At the same time, y′ is an ancestor of x′ and h(x′) − h(y′) = d_{ε}(x′, y′) ⩾ (1 − 2η)d_{ε}(x, y). So,

2(η + 7δ)d_{ε}(x, y) ⩾ d_{ε}(y′′, y′) + d_{ε}(x′, x′′) ⩾ h(y′′) − h(x′′) + h(x′) − h(y′) ⩾ 2(1 − η − 7δ)d_{ε}(x, y),

which is a contradiction since η + 7δ < 1/2.

Next suppose that (w, y, x) is 7δd_{ε}(x, y)-near a path-type configuration (w′′, y′′, x′′). Then |h(x′) − h(x′′)| ⩽ d_{ε}(x′, x′′) ⩽ (η + 7δ)d_{ε}(x, y). So,

(η + 7δ)d_{ε}(x, y) ⩾ d_{ε}(y′, y′′) ⩾ h(y′′) − h(y′)

= (h(y′′) − h(x′′)) + (h(x′′) − h(x′)) + h(x′) − h(y′) > 0 − (η + 7δ)d_{ε}(x, y) + (1 − 2η)d_{ε}(x, y),

which is a contradiction

Lastly, suppose that (w, y, x) is 7δd_{ε}(x, y)-near a tent-type configuration (w′′, y′′, x′′). Note that |h(y′) − h(y′′)| ⩽ d_{ε}(y′, y′′) ⩽ (η + 7δ)d_{ε}(x, y). So, h(y′) ⩾ h(y′′) − (η + 7δ)d_{ε}(x, y). Also,

h(y′′) − h(w′′) = d_{ε}(y′′, w′′) ⩾ d_{ε}(y, w) − 14δd_{ε}(x, y) ⩾ (\frac{1 − δ}{1 + δ} − 14δ) d_{ε}(x, y) ⩾ (η + 7δ)d_{ε}(x, y).

Consider the point w̄ defined as the ancestor of y′ at distance h(y′′) − h(w′′) − (η + 7δ)d_{ε}(x, y) from y′. Let also w′′′ be the ancestor of y′′ at distance h(y′′) − h(w′′) − (η + 7δ)d_{ε}(x, y) from y′′. By Lemma 6.9, we have d_{ε}(w̄, w′′′) ⩽ d_{ε}(y′, y′′) ⩽ (η + 7δ)d_{ε}(x, y). Therefore,

d_{ε}(w̄, w) ⩽ d_{ε}(w̄, w′′′) + d_{ε}(w′′′, w′′) + d_{ε}(w′′, w) ⩽ (2η + 21δ)d_{ε}(x, y).

Hence (x, y, w) is (2η + 21δ)d_{ε}(x, y)-near the path-type configuration (x′, y′, w̄).

Lemma 6.19. Let (x, y, z, w) be a δ-fork of B_{∞}. Assume that (x, y, z) is ηd_{ε}(x, y)-near a tenttype configuration. Assume also that η < 1/10 and ε_{n} < 1/4 for all n. Then (w, y, x) cannot be ηd_{ε}(x, y)-near a tent-type configuration.

Proof. Let (x′, y′, z′) be a tent type configuration that is ηd_{ε}(x, y)-near (x, y, z). Suppose for contradiction that there exists a tent type configuration (w′′, y′′, x′′) that is ηd_{ε}(x, y)-near (w, y, x). Note that h(y′′) ⩾ h(y′)−d_{ε}(y′, y′′) ⩾ h(y′)−2ηd_{ε}(x, y) and h(y′)−h(x′) ⩾ (1−2η)d_{ε}(x, y) > 2ηd_{ε}(x, y). Let x^{∗} be the ancestor of y′ at distance h(y′) − h(x′) − 2ηd_{ε}(x, y) from y′, and let x̃ be the ancestor of y′′ at distance h(y′) − h(x′) − 2ηd_{ε}(x, y) from y′′. An application of Lemma 6.9 yields the estimate d_{ε}(x̃, x^{∗}) ⩽ d_{ε}(y′, y′′) ⩽ 2ηd_{ε}(x, y). But, since h(x′′) ⩾ h(y′′), we also know that d_{ε}(x̃, x′′) ⩾ h(y′′) − h(x̃) = d_{ε}(y′, x′) − 2ηd_{ε}(x, y). Hence,

2ηd_{ε}(x, y) ⩾ d_{ε}(x̃, x^{∗}) ⩾ d_{ε}(x̃, x′′)−d_{ε}(x^{∗}, x′)−d_{ε}(x′, x′′) ⩾ d_{ε}(x′, y′)−6ηd_{ε}(x, y) ⩾ (1−8η)d_{ε}(x, y),

which is a contradiction, since η < 1/10.

Proof of Lemma 6.14. Since (x, y, z, w) is a δ-fork, by Theorem 6.4, both (x, y, z) and (x, y, w) are 7δd_{ε}(x, y)-near a tent-type configuration, a path-type configuration, or the corresponding reverse configurations. We have 10 possible combinations of these pairs, as appearing in Table 1. By applying Lemmas 6.18 and 6.19 with η = 7δ, we rule out three of these configurations, and a fourth configuration is possible but only as 35δd_{ε}(x, y)-near a type II configuration.

We are left with six possible configurations. By applying Lemmas 6.16 and 6.17 with η = 7δ we conclude that in two of those configurations we have d_{ε}(w, z) ⩽ (69δ + 2ε_{h_{0}})d_{ε}(x, y), and the rest are configurations that are 7δd_{ε}(x, y)-near one of the types I–IV.

6.2.3 Classification of approximate 3-paths

We start with the following natural notion:

Definition 6.20. For x_{0}, x_{1}, x_{2}, x_{3} ∈ B_{∞} the quadruple (x_{0}, x_{1}, x_{2}, x_{3}) is called a (1+δ)-approximate P_{3} if there exists L > 0 such that for every 0 ⩽ i ⩽ j ⩽ 3 we have

(j − i)L ⩽ d_{ε}(x_{i}, x_{j}) ⩽ (1 + δ)(j − i)L.

Note that in this case x_{1} ∈ Mid(x_{0}, x_{2}, δ) and x_{2} ∈ Mid(x_{1}, x_{3}, δ).

As in the case of δ-forks, there are 10 possible concatenations of two midpoints configurations (path-type or tent-type): P-P, P-p, P-T, P-t, p-P, p-T, p-t, T-T, T-t, t-T (the midpoint configurations p-p, P-p, t-p, T-p, p-P, t-P, T-P, t-t, T-t, t-T are respectively such concatenations with the order of x_{0}, x_{1}, x_{2}, x_{3} reversed). We will rule out some of these possibilities, and obtain some stronger properties for the rest. See Table 2.

As in the case of δ-forks, it will be beneficial to give names to three special types approximate 3-paths:

Midpoint configuration Reverse configuration Type
(P-P)  (p-p)  type A
(P-p)  (P-p)  impossible
(P-T)  (t-p)  impossible
(P-t)  (T-p)  type B
(p-P)  (p-P)  impossible
(p-T)  (t-P)  type C
(p-t)  (T-P)  impossible
(T-T)  (t-t)  possible only as type C
(T-t)  (T-t)  impossible
(t-T)  (t-T)  impossible

Table 2: The possible configurations of 3 paths.

Definition 6.21. For x_{0}, x_{1}, x_{2}, x_{3} ∈ B_{∞} and η > 0, a quadruple (x_{0}, x_{1}, x_{2}, x_{3}) is called:

• η-near a type A configuration if both (x_{0}, x_{1}, x_{2}) and (x_{1}, x_{2}, x_{3}) are η-near path-type configurations,

• η-near a type B configuration if (x_{0}, x_{1}, x_{2}) is η-near a path-type configuration, and (x_{3}, x_{2}, x_{1}) is η-near tent-type configuration,

• η near type C configuration if (x_{2}, x_{1}, x_{0}) is η-near a path-type configuration, and (x_{1}, x_{2}, x_{3}) is η-near a tent-type configuration.

See also Figure 6.

Figure 6: The three possible types of approximate 3-paths.

The following lemma is the main result of this subsection.

Lemma 6.22. Assume that ε_{n} < \frac{1}{4} for all n and fix δ < 1/200. Assume that (x_{0}, x_{1}, x_{2}, x_{3}) is a (1 + δ)-approximate P_{3}. Then either (x_{0}, x_{1}, x_{2}, x_{3}) or (x_{3}, x_{2}, x_{1}, x_{0}) is 35δd_{ε}(x_{0}, x_{1})-near a configuration of type A, B or C.

The proof of Lemma 6.22 is again a case analysis that examines all 10 possible ways (up to symmetry) to concatenate two midpoint configurations. The proof is divided into a few lemmas according to the cases, and is completed at the end of this subsection.

Lemma 6.23. Assume that ε_{n} < \frac{1}{4} for all n and that (x_{0}, x_{1}, x_{2}, x_{3}) is a (1 + δ)-approximate P_{3} such that (x_{0}, x_{1}, x_{2}) is ηd_{ε}(x_{0}, x_{1})-near a path-type configuration. If max{δ, η} < 1/200 then either (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{0}, x_{1})-near a path-type configuration (type A), or (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{0}, x_{1})- near a tent-type configuration (type B).

Proof. Due to Theorem 6.4 we only need to rule out the possibility that (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{1}, x_{2})- near a path-type configuration, or that (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{1}, x_{2})-near a tent-type configuration. Let (x′_{0}, x′_{1}, x′_{2}) be a path-type configuration that is ηd_{ε}(x_{0}, x_{1})-near (x_{0}, x_{1}, x_{2}).

Suppose first that (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{1}, x_{2})-near the path-type configuration (x′′_{3}, x′′_{2}, x′′_{1}). Since h(x′_{1}) ⩾ h(x′_{2}) and h(x′′_{2}) ⩾ h(x′′_{1}) we have,

|h(x_{1}) − h(x_{2})| ⩽ |h(x_{1}) − h(x′_{1})| + (h(x′_{1}) − h(x′_{2})) + |h(x′_{2}) − h(x_{2})| ⩽ d_{ε}(x_{1}, x′_{1}) + (h(x′_{1}) − h(x′_{2})) + d_{ε}(x′_{2}, x_{2}) ⩽ 2ηd_{ε}(x_{0}, x_{1}) + (h(x′_{1}) − h(x′_{2})) , (74)

and similarly,

|h(x_{1}) − h(x_{2})| ⩽ |h(x_{1}) − h(x′′_{1})| + (h(x′′_{2}) − h(x′′_{1})) + |h(x′′_{2}) − h(x_{2})| ⩽ d_{ε}(x_{1}, x′′_{1}) + (h(x′′_{2}) − h(x′′_{1})) + d_{ε}(x′_{2}, x_{2}) ⩽ 14δd_{ε}(x_{0}, x_{1}) + (h(x′′_{2}) − h(x′′_{1})) . (75)

By summing (74) and (75) we obtain the bound

2|h(x_{1}) − h(x_{2})| ⩽ (2η + 14δ) d_{ε}(x_{0}, x_{1}) + d_{ε}(x′_{1}, x′′_{1}) + d_{ε}(x′_{2}, x′′_{2}) ⩽ (4η + 28δ) d_{ε}(x_{0}, x_{1}).

Thus

|h(x_{1}) − h(x_{2})| ⩽ (2η + 14δ)d_{ε}(x_{0}, x_{1}).  (76)

Since x′_{0} is a descendant of x′_{1},

|h(x_{0}) − h(x_{1}) − d_{ε}(x_{0}, x_{1})| ⩽ |h(x′_{0}) − h(x′_{1}) − d_{ε}(x_{0}, x_{1})| + 2ηd_{ε}(x_{0}, x_{1}) = |d_{ε}(x′_{0}, x′_{1}) − d_{ε}(x_{0}, x_{1})| + 2δd_{ε}(x_{0}, x_{1}) ⩽ 4ηd_{ε}(x_{0}, x_{1}). (77)

Similarly, since x′′_{3} is a descendant of x′′_{2},

|h(x_{3}) − h(x_{2}) − d_{ε}(x_{0}, x_{1})| ⩽ |h(x′′_{3}) − h(x′′_{2}) − d_{ε}(x_{0}, x_{1})| + 14δd_{ε}(x_{1}, x_{2}) = |d_{ε}(x′′_{3}, x′′_{2}) − d_{ε}(x_{0}, x_{1})| + 14δd_{ε}(x_{0}, x_{1}) ⩽ 28δd_{ε}(x_{0}, x_{1}). (78)

Hence,

|h(x′′_{3}) − h(x′_{0})| ⩽ |h(x′′_{3}) − h(x_{3})| + |h(x_{3}) − h(x_{2}) − d_{ε}(x_{0}, x_{1})| + |h(x_{2}) − h(x_{1})| +|h(x_{0}) − h(x_{1}) − d_{ε}(x_{0}, x_{1})| + |h(x_{0}) − h(x′_{0})|

⩽^{(76)∧(77)∧(78)} d_{ε}(x′′_{3}, x_{3}) + 28δd_{ε}(x_{0}, x_{1}) + (2η + 14δ)d_{ε}(x_{0}, x_{1}) + 4ηd_{ε}(x_{0}, x_{1}) + d_{ε}(x_{0}, x′_{0})

⩽ (49δ + 7η)d_{ε}(x_{0}, x_{1}).  (79)

We record for future reference the following consequence of (76) and (79):

min{h(x′_{0}), h(x′′_{3})} − min{h(x′_{1}), h(x′′_{2})} ⩽ max {h(x′_{0}) − h(x′_{1}), h(x′_{0}) − h(x′′_{2})}
⩽^{(79)} max {d_{ε}(x′_{0}, x′_{1}), h(x′′_{3}) − h(x′′_{2}) + (49δ + 7η)d_{ε}(x_{0}, x_{1})}
⩽ max {(1 + 2η)d_{ε}(x_{0}, x_{1}), d_{ε}(x′′_{3}, x′′_{2}) + (49δ + 7η)d_{ε}(x_{0}, x_{1})}
⩽ (1 + 64δ + 7η)d_{ε}(x_{0}, x_{1}).  (80)

We next claim that

lca(x′_{0}, x′′_{3}) = lca(x′_{1}, x′′_{2}).  (81)

Indeed, since x′_{1} is an ancestor of x′_{0} and x′′_{2} is an ancestor of x′′_{3}, if lca(x′_{0}, x′′_{3}) ≠ lca(x′_{1}, x′′_{2}) then either x′_{1} is a descendant of x′′_{2}, or x′′_{2} is a descendant of x′_{1}. If x′_{1} is a descendant of x′′_{2} then

(η + 7δ)d_{ε}(x_{0}, x_{1}) ⩾ d_{ε}(x′_{1}, x′′_{1}) ⩾ d_{ε}(x′′_{2}, x′_{1}) ⩾ d_{ε}(x_{2}, x_{1}) − (η + 7δ)d_{ε}(x_{0}, x_{1})

⩾ \frac{1}{1 + δ} d_{ε}(x_{0}, x_{1}) − (η + 7δ)d_{ε}(x_{0}, x_{1}),

which is a contradiction since δ, η < 1/200. Similarly, if x′′_{2} is a descendant of x′_{1} then

(η + 7δ)d_{ε}(x_{0}, x_{1}) ⩾ d_{ε}(x′_{2}, x′′_{2}) ⩾ d_{ε}(x′′_{2}, x′_{1}) ⩾ \frac{1}{1 + δ} d_{ε}(x_{0}, x_{1}) − (η + 7δ)d_{ε}(x_{0}, x_{1}),

arriving once more at a contradiction. This proves (81).

Now,

\frac{3}{1 + δ} d_{ε}(x_{0}, x_{1}) ⩽ d_{ε}(x_{0}, x_{3})

⩽ d_{ε}(x′′_{3}, x′_{0}) + (η + 7δ)d_{ε}(x_{0}, x_{1})

⩽^{(79)} 2ε_{min{h(x′_{0}),h(x′′_{3})}} [min{h(x′_{0}), h(x′′_{3})} − h(lca(x′_{0}, x′′_{3}))] + (8η + 56δ)d_{ε}(x_{0}, x_{1})

=^{(81)} 2ε_{min{h(x′_{0}),h(x′′_{3})}} [min{h(x′_{1}), h(x′′_{2})} − h(lca(x′_{1}, x′′_{2}))] + (8η + 56δ)d_{ε}(x_{0}, x_{1})

+ 2ε_{min{h(x′_{0}),h(x′′_{3})}} [min{h(x′_{0}), h(x′′_{3})} − min{h(x′_{1}), h(x′′_{2})}]

⩽^{(80)} 2ε_{min{h(x′_{1}),h(x′′_{2})}} [min{h(x′_{1}), h(x′′_{2})} − h(lca(x′_{1}, x′′_{2}))]

+ (8η + 56δ + \frac{1 + 64δ + 7η}{2} ) d_{ε}(x_{0}, x_{1})  (82)

⩽ d_{ε}(x′_{1}, x′′_{2}) + (\frac{1}{2} + 88δ + 12η) d_{ε}(x_{0}, x_{1})

⩽ (\frac{3}{2} + 96δ + 13η) d_{ε}(x_{0}, x_{1}),  (83)

where in (82) we used min{h(x′_{0}), h(x′′_{3})} ⩾ min{h(x′_{1}), h(x′′_{2})} and ε_{min{h(x′_{0}),h(x′′_{3})}} < 1/4. Since max{η, δ} < 1/200, the bound (83) is a contradiction.

Next suppose that (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{0}, x_{1})-near a tent-type configuration (x′′_{1}, x′′_{2}, x′′_{3}). Since h(x′_{2}) ⩽ h(x′_{1}) and h(x′′_{2}) ⩾ h(x′′_{1}), we have

|h(x_{1}) − h(x_{2})| ⩽ |h(x_{1}) − h(x′_{1})| + (h(x′_{1}) − h(x′_{2})) + |h(x′_{2}) − h(x_{2})|
⩽ d_{ε}(x_{1}, x′_{1}) + (h(x′_{1}) − h(x′_{2})) + (h(x′′_{2}) − h(x′′_{1})) + d_{ε}(x′_{2}, x_{2})
⩽ d_{ε}(x_{1}, x′_{1}) + d_{ε}(x′_{1}, x′′_{1}) + d_{ε}(x′_{2}, x′′_{2}) + d_{ε}(x′_{2}, x_{2})
⩽ (4η + 14δ)d_{ε}(x_{0}, x_{1}).  (84)

On the other hand, x′′_{1} is an ancestor of x′′_{2}, and therefore we have

(\frac{1}{1 + δ} − 14δ) d_{ε}(x_{0}, x_{1}) ⩽ d_{ε}(x′′_{1}, x′′_{2}) = h(x′′_{2}) − h(x′′_{1})

⩽ |h(x_{1}) − h(x_{2})| + 14δd_{ε}(x_{0}, x_{1}) ⩽^{(84)} (4η + 28δ)d_{ε}(x_{0}, x_{1}), (85)

which is a contradiction since max{η, δ} < 1/200.

Lemma 6.24. Assume that ε_{n} < \frac{1}{4} for all n and that (x_{0}, x_{1}, x_{2}, x_{3}) is a (1 + δ)-approximate P_{3} such that (x_{2}, x_{1}, x_{0}) is ηd_{ε}(x_{0}, x_{1})-near a path-type configuration. If max{δ, η} < 1/200 then either (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{0}, x_{1})-near a path-type configuration (reverse type A), or (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{0}, x_{1})-near a tent-type configuration (type C).

Proof. Let (x′_{2}, x′_{1}, x′_{0}) be in path-type configuration that is ηd_{ε}(x_{0}, x_{1})-near (x_{2}, x_{1}, x_{0}). First, assume for contradiction that (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{1}, x_{2})-near a tent-type configuration (x′′_{3}, x′′_{2}, x′′_{1}). Then h(x′′_{1}) ⩾ h(x′′_{2}), where as h(x′_{2}) − h(x′_{1}) = d_{ε}(x′_{2}, x′_{1}). Arguing as in (84), it follows that |h(x_{1})−h(x_{2})| ⩽ (2η +28δ)d_{ε}(x_{0}, x_{1}), and we arrive at a contradiction by arguing similarly to (85).

Next, assume for contradiction that (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{1}, x_{2})-near a path-type configuration (x′′_{1}, x′′_{2}, x′′_{3}). Then h(x′′_{1}) − h(x′′_{2}) = d_{ε}(x′′_{1}, x′′_{2}), whereas h(x′_{2}) − h(x′_{1}) = d_{ε}(x′_{1}, x′_{2}). By summing these two identities, we arrive at a contradiction as follows:

(\frac{2}{1 + δ} − 2η − 14δ) d_{ε}(x_{0}, x_{1}) ⩽ d_{ε}(x′_{1}, x′_{2}) + d_{ε}(x′′_{1}, x′′_{2}) = (h(x′_{2}) − h(x′′_{2})) + (h(x′′_{1}) − h(x′_{1}))

⩽ d_{ε}(x′_{2}, x′′_{2}) + d_{ε}(x′_{1}, x′′_{1}) ⩽ (2η + 14δ)d_{ε}(x_{0}, x_{1}).

Lemma 6.25. Assume that ε_{n} < \frac{1}{4} for all n and that (x_{0}, x_{1}, x_{2}, x_{3}) is a (1 + δ)-approximate P_{3} such that (x_{0}, x_{1}, x_{2}) is ηd_{ε}(x_{0}, x_{1})-near a tent-type configuration. If max{δ, η} < 1/200 then either (x_{2}, x_{1}, x_{0}) is (14δ + 3η)d_{ε}(x_{0}, x_{1})-near a path-type configuration and (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{1}, x_{2})- near a tent-type configuration (type C), or (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{0}, x_{1})-near a path-type configuration (reverse type B).

Proof. Let (x′_{0}, x′_{1}, x′_{2}) be a tent-type configuration that is ηd_{ε}(x_{0}, x_{1})-near (x_{0}, x_{1}, x_{2}). First, suppose that (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{1}, x_{2})-near a tent-type configuration (x′′_{1}, x′′_{2}, x′′_{3}). Note that |h(x′_{1}) − h(x′′_{1})| ⩽ d_{ε}(x′_{1}, x′′_{1}) ⩽ (η + 7δ)d_{ε}(x_{0}, x_{1}). So, let x′′_{0} be an ancestor of x′′_{1} at distance h(x′_{1}) − h(x′_{0}) − (η + 7δ)d_{ε}(x_{0}, x_{1}) ∈ [0, h(x′′_{1})] from x′′_{1}, and let x_{0}^{∗} be an ancestor of x′_{1} at distance h(x′_{1}) − h(x′_{0}) − (η + 7δ)d_{ε}(x_{0}, x_{1}) from x′_{1}. Then h(x′_{1}) − h(x_{0}^{∗}) = h(x′′_{1}) − h(x′′_{0}) and d_{ε}(x_{0}^{∗}, x′_{0}) ⩽ (η + 7δ)d_{ε}(x_{0}, x_{1}). By Lemma 6.9,

d_{ε}(x_{0}, x′′_{0}) − (2η + 7δ)d_{ε}(x_{0}, x_{1} ⩽ d_{ε}(x_{0}, x′′_{0}) − d_{ε}(x_{0}^{∗}, x′_{0}) − d_{ε}(x′_{0}, x_{0}) ⩽ d_{ε}(x_{0}^{∗}, x′′_{0}) ⩽ d_{ε}(x′_{1}, x′′_{1}) ⩽ (η + 7δ)d_{ε}(x_{0}, x_{1}).

Hence (x′′_{2}, x′′_{1}, x′′_{0}) is a path-type configuration that is (14δ + 3η)d_{ε}(x_{0}, x_{1})-near (x_{2}, x_{1}, x_{0}).

Next assume for contradiction that (x_{3}, x_{2}, x_{1}) is 7δd_{ε}(x_{1}, x_{2}) near a tent-type configuration (x′′_{3}, x′′_{2}, x′′_{1}). Then

(1 − 15δ) d_{ε}(x_{0}, x_{1}) ⩽ (\frac{1}{1 + δ} − 14δ) d_{ε}(x_{0}, x_{1}) ⩽ h(x′′_{2}) − h(x′′_{3}) ⩽ (1 + 15δ)d_{ε}(x_{0}, x_{1}), (86)

and

(1 − δ − 2η) d_{ε}(x_{0}, x_{1}) ⩽ (\frac{1}{1 + δ} − 2η) d_{ε}(x_{0}, x_{1}) ⩽ h(x′_{1}) − h(x′_{0}) ⩽ (1 + δ + 2η)d_{ε}(x_{0}, x_{1}). (87)

So, let x_{3}^{##} be an ancestor of x′′_{2} at distance h(x′′_{2}) − h(x′′_{3}) − (16δ + 2η) d_{ε}(x_{0}, x_{1}) ∈ [0, h(x′′_{2})] from x′′_{2}, and let x_{0}^{#} be an ancestor of x′_{1} at distance h(x′′_{2}) − h(x′′_{3}) − (16δ + 2η) d_{ε}(x_{0}, x_{1}) ∈ [0, h(x′_{1})] from x′_{1}. Then

d_{ε}(x′′_{3}, x_{3}^{##}) ⩽ (16δ + 2η) d_{ε}(x_{0}, x_{1}),  (88)

and

d_{ε}(x′_{0}, x_{0}^{#}) = |h(x′_{0}) − h(x_{0}^{#})| = |h(x′_{0}) − (h(x′_{1}) − h(x′′_{2}) + h(x′′_{3}) + (16δ + 2η) d_{ε}(x_{0}, x_{1}))|

⩽^{(86)∧(87)} 2(16δ + 2η)d_{ε}(x_{0}, x_{1}). (89)

Moreover, h(x_{1}) − h(x_{0}^{#}) = h(x′′_{2}) − h(x_{3}^{##}), so by Lemma 6.9 we have

(\frac{3}{1 + δ} − 55δ − 7η) d_{ε}(x_{0}, x_{1}) ⩽ d_{ε}(x_{0}, x_{3}) − (55δ + 7η)d_{ε}(x_{0}, x_{1}) ⩽^{(88)∧(89)} d_{ε}(x_{0}^{#}, x_{3}^{##})

⩽ d_{ε}(x′_{1}, x′′_{2}) ⩽ (1 + 8δ + η)d_{ε}(x_{0}, x_{1}),

which is a contradiction since max{δ, η} < 1/200.

Lastly, assume for contradiction that (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{1}, x_{2})-near a path-type configuration (x′′_{1}, x′′_{2}, x′′_{3}). Then since h(x′_{1}) ⩽ h(x′_{2}) we have

(\frac{1}{1 + δ} − 14δ) d_{ε}(x_{0}, x_{1}) ⩽ d_{ε}(x′′_{1}, x′′_{2}) = h(x′′_{1}) − h(x′′_{2}) ⩽ (h(x′′_{1}) − h(x′′_{2})) + (h(x′_{2}) − h(x′_{1}))

⩽ d_{ε}(x′′_{1}, x′_{1}) + d_{ε}(x′′_{2}, x′_{2}) ⩽ (14δ + 2η)d_{ε}(x_{0}, x_{1}),

a contradiction.

Lemma 6.26. Assume that ε_{n} < \frac{1}{4} for all n and that (x_{0}, x_{1}, x_{2}, x_{3}) is a (1 + δ)-approximate P_{3} such that (x_{2}, x_{1}, x_{0}) is ηd_{ε}(x_{0}, x_{1})-near a tent-type configuration. If max{δ, η} < 1/200 then (x_{1}, x_{2}, x_{3}) cannot be 7δd_{ε}(x_{0}, x_{1}) near a tent-type configuration.

Proof. Let (x′_{2}, x′_{1}, x′_{0}) be a tent-type configuration that is ηd_{ε}(x_{0}, x_{1})-near (x_{2}, x_{1}, x_{0}). Suppose for contradiction that (x_{1}, x_{2}, x_{3}) is 7δd_{ε}(x_{0}, x_{1})-near a tent-type configuration (x′′_{1}, x′′_{2}, x′′_{3}). Then h(x′_{1}) − h(x′_{2}) = d_{ε}(x′_{1}, x′_{2}), whereas h(x′′_{2}) − h(x′′_{1}) = d_{ε}(x′′_{1}, x′′_{2}). Taking the sum of these two inequalities we conclude that

d_{ε}(x′′_{1}, x′′_{2}) + d_{ε}(x′_{1}, x′_{2}) ⩽ d_{ε}(x′_{1}, x′′_{1}) + d_{ε}(x′_{2}, x′′_{2}) ⩽ (2η + 14δ)d_{ε}(x_{0}, x_{1}).

At the same time, (\frac{2}{1+δ} − 2η − 14δ) d_{ε}(x_{0}, x_{1}) ⩽ d_{ε}(x′′_{1}, x′′_{2}) + d_{ε}(x′_{1}, x′_{2}), which leads to the desired contradiction.

Proof of Lemma 6.22. Since (x_{0}, x_{1}, x_{2}, x_{3}) is a (1+δ)-approximate P_{3}, we have x_{1} ∈ Mid(x_{0}, x_{2}, δ), and x_{2} ∈ Mid(x_{1}, x_{3}, δ). Since the assumptions of Theorem 6.4 hold, we can apply with η = 7δ Lemmas 6.23, 6.24, 6.25, 6.26, and conclude that either (x_{0}, x_{1}, x_{2}, x_{3}) or (x_{3}, x_{2}, x_{1}, x_{0}) must be 35δd_{ε}(x_{0}, x_{1})-near a configuration of type A, B or C.

6.3 Nonembeddability of vertically faithful B_{4}

In what follows we need some standard notation on trees. As before, B_{n} is the complete binary tree of height n; the root of B_{n} is denoted by r. Denote by I(B_{n}) the set of internal vertices of B_{n}, i.e., vertices of B_{n} which are not the root or a leaf. For a vertex v in {r} ∪ I(B_{n}) we denote by v_{0} and v_{1} its children. For α ∈ {0, 1}^{∗} (the set of finite sequences of ’0’ and ’1’) and a ∈ {0, 1} we denote by v_{αa} = (v_{α})_{a}.

The aim of the current section is to prove the following lemma.

Lemma 6.27. Fix 0 < δ < 1/400 and let f : B_{4} → (B_{∞}, d_{ε}) be a (1 + δ)-vertically faithful embedding. Then the distortion of f satisfies

dist(f) ⩾ \frac{1}{500δ + ε_{h_{0}}} ,

where h_{0} = min_{x∈B_{4}} h(f(x)).

The proof of Lemma 6.27 is by a contradiction. By Lemma 6.14, assuming the distortion of f is small, all the δ-forks in the (1 + δ)-vertically faithful embedding must be of types I–IV. By exploring the constrains implied by Lemma 6.22 on how those δ-forks can be “stitched” together, we reach the conclusion that they are sufficiently severe to force any vertically faithful embedding of B_{4} to have a large contraction, and therefore high distortion.

Fix f : B_{4} → (B_{∞}, d_{ε}). For u ∈ I(B_{4}) we denote by F(u) the fork in which u is the center point, i.e., if v be the parent of u in B_{4}, then

F(u) =^{def} (f(v), f(u), f(u_{0}), f(u_{1})).

We shall assume from now on that f satisfies the assumptions of Lemma 6.27, i.e., that it satisfies (8) with D = 1 + δ for some δ < 1/400 and λ > 0.

Lemma 6.28. Fix u ∈ B_{4} with h(u) ∈ {1, 2}. If the fork F(u) is 37δλ-near a type I or type III configuration, then there exists w ∈ I(B_{4}) satisfying

d_{ε}(f(w_{0}), f(w_{1})) ⩽ (170δ + ε_{h_{0}}) · 2λ.  (90)

Proof. Let v be the parent of u. Hence, (f(v), f(u), f(u_{0}), f(u_{1})) is 35δ(1 + δ)λ-near a type I or a type III configuration. Assume first that (f(v), f(u), f(u_{0}), f(u_{1})) is 37δλ-near a type I configuration. If both (f(u_{0}), f(u), f(v)) and (f(u_{1}), f(u), f(v)) were 37δλ-near a path type configuration then by Lemma 6.16 (with η = 37δ) we would have

d_{ε}(f(u_{0}), f(u_{1})) ⩽ (339δ + 2ε_{h_{0}})(1 + δ)λ ⩽ (170δ + ε_{h_{0}}) · 2λ,  (91)

proving (90) with w = u. The same conclusion holds when (f(v), f(u), f(u_{0}), f(u_{1})) is 37δλ-near a type III configuration: in this case without loss of generality (f(v), f(u), f(u_{0})) is 37δλ-near a tent-type configuration and (f(u_{1}), f(u), f(v)) is 37δλ-near a path-type configuration. Using Lemma 6.16 as above we would arrive at the conclusion (91) if (f(u_{0}), f(u), f(v)) were 37δλ-near a path-type type configuration. Thus, in both the type I and type III cases of Lemma 6.28 we may assume that (f(v), f(u), f(u_{0})) is 37δλ-near a tent-type configuration, and that, by Lemma 6.8, (f(v), f(u), f(u_{0})) is not 37δλ-near a path-type configuration, and (f(u_{0}), f(u), f(v)) is not 37δλnear a path-type configuration or a tent-type configuration.

By Lemma 6.22 (and Table 2) (f(u_{0c}), f(u_{0}), f(u), f(v)) must be 35δ(1 + δ)λ-near a type B configuration for both c ∈ {0, 1}. This means that (f(u_{0c}), f(u_{0}), f(u)) are both 35δ(1 + δ)λnear a path-type configuration, and so by Lemma 6.16 (with η = 35δ(1 + δ)) we deduce that d_{ε}(f(u_{00}), f(u_{01})) ⩽ (170δ + ε_{h_{0}}) · 2λ.

Lemma 6.29. Fix u ∈ B_{4} with h(u) ∈ {1, 2}. If F(u) is 37δλ-near a type II configuration then for both b ∈ {0, 1} either F(u_{b}) is 99δλ-near a type II configuration, or d_{ε}(f(u_{b0}), f(u_{b1})) ⩽ 400δλ.

Proof. Let v be the parent of u. For both c ∈ {0, 1} we know that (f(v), f(u), f(u_{0}), f(u_{0c})) is a (1 + δ)-approximate P_{3}, and therefore by Lemma 6.22 either (f(v), f(u), f(u_{0}), f(u_{0c})) or (f(u_{0c}), f(u_{0}), f(u), f(v)) is 35δ(1 + δ)λ-near a configuration of type A, B or C. Note that since (f(v), f(u), f(u_{0})) is assumed to be 37δλ-near a path-type configuration, we rule out the possibility that (f(v), f(u), f(u_{0}), f(u_{0c})) is 35δ(1 + δ)λ-near a configuration of type C, since otherwise both (f(v), f(u), f(u_{0})) and (f(u_{0}), f(u), f(v)) would be 37δλ-near path-type configurations, contradicting Lemma 6.8. For the same reason we rule out the possibility that (f(u_{0c}), f(u_{0}), f(u), f(v)) is 35δ(1 + δ)λ-near a configuration of type A or type B. An inspection of the three remaining possibilities shows that either (f(u), f(u_{0}), f(u_{0c})) is 37δλ-near a path-type configuration, or (f(u_{0c}), f(u_{0}), f(u)) is 37δλ-near a tent-type configuration.

Now,

• If for both c ∈ {0, 1} we have that (f(u), f(u_{0}), f(u_{0c})) is 37δλ-near a path-type configuration, then F(u_{0}) is 37δλ-near a type II configuration.

• If for both c ∈ {0, 1} we have that (f(u_{0c}), f(u_{0}), f(u)) are 37δλ-near a tent-type configuration, then by Lemma 6.17 we have d_{ε}(f(u_{01}), f(u_{00})) ⩽ 400δ.

• By Lemma 6.18, the only way that (f(u), f(u_{0}), f(u_{00})) could be 37δλ-near a path type configuration while at the same time (f(u_{01}), f(u_{0}), f(u)) is 37δλ-near a tent-type configuration (or vice versa), is that F(u_{0}) is 99δλ-near a type II configuration.

Lemma 6.30. Fix u ∈ B_{4} with h(u) ∈ {1, 2}. If F(u) is 35δ(1 + δ)λ-near a type IV configuration, then there exists b ∈ {0, 1} such that F(u_{b}) is 37δλ-near a type II configuration.

Proof. Let v be the parent of u. Without loss of generality (f(u_{0}), f(u), f(v)) is 35δ(1 + δ)λ-near a tent-type configuration. By Lemma 6.22 (using Lemma 6.8 to rule out the remaining possibilities), this means that for both c ∈ {0, 1} the quadruple (f(u_{0c}), f(u_{0}), f(u), f(v)) is 35δ(1 + δ)^{2}λ-near a type C configuration, and therefore F(u_{0}) is 35δ(1 + δ)^{2}λ near a type II configuration.

Lemma 6.31. Fix u ∈ B_{4} with h(u) ∈ {0, 1, 2}. If F(u_{0}) and F(u_{1}) are both 99δλ-near type a II configuration then d_{ε}(f(u_{0}), f(u_{1})) ⩽ 1000δλ.

Proof. By our assumptions, (f(u), f(u_{0}), f(u_{00})) is 99δλ-near a path type configuration (u′, u′_{0}, u′_{00}) and (f(u), f(u_{1}), f(u_{10})) is 99δλ-near a path-type configuration (u′′, u′′_{1}, u′′_{10}). We may assume without loss of generality that h(u′′) − h(u′_{1}) ⩽ h(u′) − h(u′_{0}). We may therefore consider the ancestor u_{1}^{∗} of u′ such that h(u′)−h(u_{1}^{∗}) = h(u′′)−h(u′′_{1}), implying in particular that h(u_{1}^{∗}) ⩾ h(u′_{0}) (recall that u′_{0} is an ancestor of u′, and u′′_{1} is ancestor of u′′). By Lemma 6.9 we have

d_{ε}(u_{1}^{∗}, u′′_{1}) ⩽ d_{ε}(u′, u′′) ⩽ 198δλ.  (92)

Hence,

h(u′) − h(u_{1}^{∗}) = d_{ε}(u′, u_{1}^{∗}) ⩾^{(92)} d_{ε}(u′, u′′_{1}) − 198δλ ⩾ d_{ε}(f(u), f(u_{1})) − 394δλ ⩾ (1 − 394δ)λ. (93)

But, we also know that

h(u′) − h(u′_{0}) = d_{ε}(u′, u′_{0}) ⩽ d_{ε}(f(u), f(u_{0})) + 198δλ ⩽ (1 + 200δ)λ.  (94)

It follows from (93) and (94) that d_{ε}(u′_{0}, u_{1}^{∗}) = h(u_{1}^{∗}) − h(u′_{0}) ⩽ 601δλ. Therefore,

d_{ε}(f(u_{1}), f(u_{0})) ⩽ d_{ε}(f(u_{0}), u′_{0}) + d_{ε}(u′_{0}, u_{1}^{∗}) + d_{ε}(u_{1}^{∗}, u′′_{1}) + d_{ε}(u′′_{1}, f(u_{1})) = 1000δλ.

Proof of Lemma 6.27. We may assume that for all u ∈ I(B_{4}) the fork F(u) is 35δ(1 + δ)λ-near a configuration of type I, II, III, or IV. Indeed, otherwise the proof is complete by Lemma 6.14. If F(r_{0}) is 35δ(1 + δ)λ-near a type I or type III configuration, then by Lemma 6.28 the proof is complete. If F (r_{0}) is 35δ(1 + δ)λ-near a type IV configuration then by Lemma 6.30 there exists b ∈ {0, 1} such that F (r_{0b}) is 37δλ-near a type II configuration. It therefore remains to deal with the case in which for some u ∈ {r_{0}, r_{0b}} the fork F(u) is 37δλ-near a type II configuration. Applying Lemma 6.29, either we are done, or both F(u_{0}) and F(u_{1}) are 99δλ-near a type II configuration, but then by Lemma 6.31 the proof of Lemma 6.27 is complete.

6.4 Nonembeddability of binary trees

We are now in position to complete the proof of Theorem 1.10.

Proof of Theorem 1.10. Write ε_{n} = 1/s(n), and ε = {ε_{n}}_{n=0}^{∞}. Thus {ε_{n}}_{n=0}^{∞} is non-increasing, {nε_{n}}_{n=0}^{∞} is non-decreasing, and ε_{n} ⩽ 1/4. We can therefore choose the metric space (X, d_{X}) = (B_{∞}, d_{ε}). The identity embedding of B_{n} into the top n-levels of B_{∞} shows that c_{X}(B_{n}) ⩽ s(n). It remains to prove the lower bound on c_{X}(B_{n}). To this end take an arbitrary injection f : B_{n} → X satisfying dist(f) ⩽ s(n), and we will now prove that

dist(f) ⩾ s (⌊\frac{n}{40s(n)}⌋) (1 − \frac{Cs(n) log s(n)}{log n}) .  (95)

By adjusting the constant C in (95), we may assume below that n is large enough, say, n ⩾ 100. Write h_{0} = ⌊n/(40s(n))⌋ and define X_{>h_{0}} = {x ∈ B_{∞} : h(x) > h_{0}}. We claim that there exists a complete binary subtree T ⊆ B_{n} of height at least ⌈n/3⌉, such that we have f(T) ⊆ X_{>h_{0}}. Indeed, let h_{min} = min{h(x) : x ∈ f(B_{n})} and h_{max} = max{h(x) : x ∈ f(B_{n})}. If h_{min} > h_{0} then f(B_{n}) ⊆ X_{>h_{0}}, and we can take T = B_{n}. So assume that h_{min} < h_{0}. Since f is an injection it must satisfy h_{max} ⩾ n. Hence ∥f∥_{Lip} ⩾ \frac{h_{max}−h_{min}}{2n} ⩾ \frac{n−h_{0}}{2n} ⩾ \frac{1}{4}. Since dist(f) ⩽ s(n) we conclude that ∥f^{−1}∥_{Lip} ⩽ 4s(n). It follows that, since diam(X ∖ X_{>h_{0}}) ⩽ 2h_{0}, we have diam(f^{−1}(X ∖ X_{>h_{0}})) ⩽ 8h_{0}s(n) ⩽ n/5. If the top ⌈n/3⌉ levels of B_{n} are mapped into X_{>h_{0}} then we are done, so assume that there exists u ∈ f^{−1}(X ∖ X_{>h_{0}}) of depth at most ⩽ ⌈n/3⌉. In this case f^{−1}(X ∖ X_{>h_{0}}) must be contained in the first ⌈n/3⌉ + n/5 < 2n/3 − 1 levels of B_{n}, so we can take T to be any subtree of B_{n} contained in the last ⌈n/3⌉ levels of B_{n}.

Fix δ ∈ (0, 1). By Theorem 1.14 (with t = 4, D = s(n) and ξ = δ), there exists a universal constant κ > 0 such that if n ⩾ s(n)^{κ/δ} then there exists a mapping ϕ : B_{4} → B_{n} with dist(ϕ) ⩽ 1+δ such that f ∘ ϕ is a (1 + δ)-vertically faithful embedding of B_{4} into X_{>h_{0}}. Choosing δ = κ\frac{log s(n)}{log n}, by increasing C in (95) if necessary, we may assume that δ < 1/400. Lemma 6.27 then implies

(1 + δ) dist(f) ⩾ dist(f ∘ ϕ) ⩾ \frac{1}{500δ + ε_{h_{0}}} = \frac{1}{500κ\frac{log s(n)}{log n} + \frac{1}{s(⌊n/(40s(n))⌋)}} .

The deduction of (7) from (6) is a simple exercise: if s(n) = o(log n/ log log n) then we have (s(n) log s(n))/ log n = o(1). The desired claim will then follow once we check that

lim sup_{n→∞} \frac{s (⌊n/(40s(n))⌋)}{s(n)} = 1.  (96)

Indeed, if (96) failed then there would exist ε_{0} ∈ (0, 1) and n_{0} ∈ ℕ such that for all n ⩾ n_{0},

s (⌊n/ log n⌋) ⩽ s (⌊n/(40s(n))⌋) ⩽ (1 − ε_{0})s(n).  (97)

Iterating (97), it would follow that s(n_{j}) ⩾ n_{j}^{Ω(1)} for some subsequence {n_{j}}_{j=1}^{∞}, a contradiction.

Proof of Theorem 1.12. The proof is identical to the above argument: all one has to notice is that when s(n) = D for all n ∈ ℕ the resulting metric d_{ε} on B_{∞} is D-equivalent to the original shortest path metric on B_{∞}. In this case, if c_{X}(B_{n}) ⩽ D − ε then the bound (95) implies that n ⩽ D^{CD^{2}/ε}.

7 Discussion and open problems

A very interesting question that arises naturally from Theorem 1.3 and is also a part of the Ribe program, is finding a metric characterization of q-smoothness. A Banach space (X, ∥ · ∥_{X}) is called q-smooth if it admits an equivalent norm ||| · ||| such that there is a constant S > 0 satisfying:

|||x||| = 1 ∧ y ∈ X ⟹ \frac{|||x + y||| + |||x − y|||}{2} ⩽ 1 + S|||y|||^{q}.

A Banach space X is p-convex if and only if its dual space X^{∗} is q-smooth, where \frac{1}{p} + \frac{1}{q} = 1 [17]. It is known that a Banach space X is p-convex for some p < ∞ (i.e., superreflexive) if and only if it is q-smooth for some q > 1 (this follows from [10, 29]). Hence Bourgain’s metric characterization of superreflexivity can be viewed as a statement about uniform smoothness as well. However, we still lack a metric characterization of the more useful notion of q-smoothness. Trees are natural candidates for finite metric obstructions to p-convexity, but it is unclear what would be the possible finite metric witnesses to the “non-q-smoothness” of a metric space.

H-trees are geometric objects that are quite simple combinatorially, yet as we have seen, they have interesting bi-Lipschitz properties. It would therefore be of interest to investigate the geometry of H-trees for its own right. In particular, what is the L_{1} distortion of an H-tree? How close can an H-tree be to a metric of negative type?

References

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

[2] 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.

[3] S. Bates, W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9(6):1092–1127, 1999.

[4] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

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

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

[7] P. Enflo. Banach spaces which can be given an equivalent uniformly convex norm. In Proceedings of the International Symposium on Partial Differential Equations and the Geometry of Normed Linear Spaces (Jerusalem, 1972), volume 13, pages 281–288 (1973), 1972.

[8] M. Gromov. Metric structures for Riemannian and non-Riemannian spaces. Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, english edition, 2007.

[9] R. C. James. Uniformly non-square Banach spaces. Ann. of Math. (2), 80:542–550, 1964.

[10] R. C. James. Some self-dual properties of normed linear spaces. In Symposium on Infinite-Dimensional Topology (Louisiana State Univ., Baton Rouge, La., 1967), pages 159–175. Ann. of Math. Studies, No. 69. Princeton Univ. Press, Princeton, N.J., 1972.

[11] W. B. Johnson and G. Schechtman. Diamond graphs and super-reflexivity. J. Topol. Anal., 1(2):177–189, 2009.

[12] T. J. Laakso. Plane with A_{∞}-weighted metric not bi-Lipschitz embeddable to ℝ^{N}. Bull. London Math. Soc., 34(6):667–676, 2002.

[13] U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285–307, 2001.

[14] J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: dimension, snowflakes, and average distortion. European J. Combin., 26(8):1180–1190, 2005.

[15] J. R. Lee and A. Naor. Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal., 14(4):745–747, 2004.

[16] J. R. Lee, A. Naor, and Y. Peres. Trees and Markov convexity. Geom. Funct. Anal., 18(5):1609– 1659, 2009.

[17] J. Lindenstrauss. On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J., 10:241–252, 1963.

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

[19] J. Matoušek. Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces. Comment. Math. Univ. Carolin, 33(3):451–463, 1992.

[20] 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.

[21] M. Mendel. Metric dichotomies. In Limits of graphs in group theory and computer science, pages 59–76. EPFL Press, Lausanne, 2009.

[22] M. Mendel and A. Naor. Scaled Enflo type is equivalent to Rademacher type. Bull. London Math. Soc., 39(3):493–498, 2007.

[23] M. Mendel and A. Naor. Markov convexity and local rigidity of distorted metrics [extended abstract]. In Computational geometry (SCG’08), pages 49–58. ACM, New York, 2008.

[24] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247–298, 2008.

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

[26] I. Newman and Y. Rabinovich. A lower bound on the distortion of embedding planar metrics into Euclidean space. Discrete Comput. Geom., 29(1):77–81, 2003.

[27] E. Odell and T. Schlumprecht. The distortion problem. Acta Math., 173(2):259–281, 1994.

[28] G. Pisier. Sur les espaces de Banach qui ne contiennent pas uniformément de l_{n}^{1}. C. R. Acad. Sci. Paris Sér. A-B, 277:A991–A994, 1973.

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

[30] 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.

[31] M. Ribe. On uniformly homeomorphic normed spaces. Ark. Mat., 14(2):237–244, 1976.