2 Notation and definitions

We will denote $\mathbb{N}\cup \{0\}$ by $\mathbb{N}_{0}$ and given $n\in \mathbb{N}_{0}$ , we will denote the set $\{i\in \mathbb{N}_{0}\mid i\leqslant n\}$ by $[n]$ . Given a finite sequence $A=(a_{i})_{i=1}^{n}\subseteq \mathbb{N}_{0}$ , the length of $A$ , denoted by $|A|$ , is defined to be $n$ ; and the maximum of $A$ , denoted by $\max A$ , is defined to be $\max \{a_{i}\}_{i=1}^{n}$ . If $m\in \mathbb{N}_{0}$ , then we define $A\restriction _{m}$ by $A\restriction _{m}\,=(a_{i})_{i=1}^{m}$ if $m\leqslant n$ and $A\restriction _{m}\,=A$ if $m>n$ . We write $B\preccurlyeq A$ if $B=A\restriction _{m}$ for some $m\in \mathbb{N}_{0}$ , and write $B\prec A$ if $B\preccurlyeq A$ and $B\neq A$ . Given another finite sequence $B$ , we denote by $A\wedge B$ the longest sequence $C$ such that $C\preccurlyeq A$ and $C\preccurlyeq B$ , and by $A^{\frown }B$ the concatenation of $A$ and $B$ . Note that if $A_{1}\preccurlyeq A_{2}$ and $A_{1}\not\preccurlyeq B$ , then $A_{2}\wedge B=A_{1}\wedge B$ . Note also that if $A_{1}\preccurlyeq B$ and $A_{2}\preccurlyeq B$ , then either $A_{1}\preccurlyeq A_{2}$ or $A_{2}\preccurlyeq A_{1}$ . We denote the sequence of length $0$ (the empty sequence) by $\emptyset$ . Given a set $X$ and $n\in \mathbb{N}_{0}$ , we denote by $X^{n}$ the set of sequences in $X$ with length equal to $n$ and by $X^{{\leqslant}n}$ the set of all sequences in $X$ with length at most $n$ .

Given a graph $G$ , we always use the (unweighted) shortest-path metric when discussing the distance between two vertices in $G$ . We denote the vertex set of $G$ by $V(G)$ and the edge set of $G$ by $E(G)$ .

For what follows, two bundle graphs are considered the same if there is a graph isomorphism between them mapping top to top and bottom to bottom. Suppose $G$ is a $\unicode[STIX]{x1D705}$ -branching bundle graph for some cardinality $\unicode[STIX]{x1D705}\neq 0$ . If $\unicode[STIX]{x1D705}=1$ , then $G$ is a path, and in this case $G^{\Vert ^{\unicode[STIX]{x1D705}}}=G$ . If $\unicode[STIX]{x1D705}$ is finite and $\unicode[STIX]{x1D705}>1$ , then $G\neq G^{\Vert ^{\unicode[STIX]{x1D705}}}$ whenever $|V(G)|\geqslant 3$ by a simple cardinality argument. However, if $\unicode[STIX]{x1D705}$ is infinite, then $(G^{\Vert ^{\unicode[STIX]{x1D705}}})^{\Vert ^{\unicode[STIX]{x1D705}}}=G^{\Vert ^{\unicode[STIX]{x1D705}}}$ (since $\unicode[STIX]{x1D705}\cdot \unicode[STIX]{x1D705}=\unicode[STIX]{x1D705}$ ). But note that for $\unicode[STIX]{x1D705}>1$ , $G$ could not have been formed in the last step of the sequence of operations by both series composition and parallel composition if $|V(G)|\geqslant 3$ . This is because if $G$ is formed in the last step via series composition, then $G$ will have a vertex $v$ that is neither the top nor bottom of $G$ such that no other vertex in $G$ has the same height as $v$ (this $v$ is the glued vertex from the definition). That is, $G$ has a vertex cut consisting of one vertex $v$ . And if $G$ is formed in the last step via parallel composition, then no such vertex will exist. Thus, for infinite $\unicode[STIX]{x1D705}$ , $G\neq G^{\Vert ^{\unicode[STIX]{x1D705}}}$ implies $G$ was formed in the last step via series composition.

Now, suppose $H$ is another $\unicode[STIX]{x1D705}$ -branching bundle graph. Then if $G^{\prime }$ is a $\unicode[STIX]{x1D705}$ -branching bundle graph with the same height as $G$ , and $H^{\prime }$ is a $\unicode[STIX]{x1D705}$ -branching bundle graph, then $G^{\frown }H={G^{\prime }}^{\frown }H^{\prime }$ if and only if $G=G^{\prime }$ and $H=H^{\prime }$ , by an easy connected component argument. Finally, note that if $u,v\in V(G^{\Vert ^{\unicode[STIX]{x1D705}}})$ are adjacent, then they must be copies of vertices that are adjacent in $G$ and must furthermore be contained in the same copy of $G$ . Thus, if $G\neq G^{\Vert ^{\unicode[STIX]{x1D705}}}$ and $H\neq H^{\Vert ^{\unicode[STIX]{x1D705}}}$ , then $G^{\Vert ^{\unicode[STIX]{x1D705}}}=H^{\Vert ^{\unicode[STIX]{x1D705}}}$ if and only if $G=H$ . These observations show that the following definition is well defined.

It is not difficult to see that given two $\unicode[STIX]{x1D705}$ -branching bundle graphs, $G$ and $G^{\prime }$ , a new $\unicode[STIX]{x1D705}$ -branching bundle graph can be created by replacing every edge of $G$ with a copy of $G^{\prime }$ (where the bottom of $G^{\prime }$ is placed on the lower endpoint of the edge and the top on the higher). We give a proof of this fact in §6. Thus the diamond and Laakso graphs used in [Reference Johnson and Schechtman11], [Reference Ostrovskii and Randrianantoanina17], and [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4] are all examples of bundle graphs.

Suppose $G$ is a $\unicode[STIX]{x1D705}$ -branching bundle graph with height $M+1$ for some cardinality $\unicode[STIX]{x1D705}$ and $M\in \mathbb{N}_{0}$ . From the definitions, every vertex of $G$ at a given height will have the same depth. And if we know the depth associated with each height, we can use Definition 2.3 to go backwards to find a sequence of operations from Definition 2.1 that can be used to create $G$ . That is, we do not actually need to know the sequence of operations used to create $G$ . All information about $G$ is contained in the branching number $\unicode[STIX]{x1D705}$ and the sequence of depths $W=(w_{r})_{r=0}^{M+1}$ , where $w_{r}$ is the depth (with respect to $\unicode[STIX]{x1D705}$ ) associated to height $r$ (we include $w_{0}=w_{M+1}=0$ for convenience).

Suppose $r\in [M+1]$ is such that $w_{r}>0$ , and let $v$ be a vertex of $G$ with height $r$ . Since $w_{r}>0$ , $v$ is a copy of some vertex $v^{\prime }$ in some $\unicode[STIX]{x1D705}$ -branching bundle graph $G^{\prime }$ (that was used in parallel composition in one of the steps to create $G$ ). To distinguish $v$ from other copies of $v^{\prime }$ , we label the copies of $G^{\prime }$ with elements of $\unicode[STIX]{x1D705}$ and record the copy in which $v$ was found as $a_{w_{r}}$ . Now in the graph $G^{\prime }$ , $v^{\prime }$ has depth $w_{r}-1$ . If $w_{r}-1>0$ , then we go through this process again for $v^{\prime }$ to obtain $a_{w_{r}-1}$ . We repeat this process until we obtain a sequence $A=(a_{i})_{i=1}^{w_{r}}$ that can be used to distinguish $v$ from any other vertex at height $r$ . Doing this for every vertex in $G$ yields a labeling of the vertex set. Actually, we could perform this process on any finite sequence in $\mathbb{N}_{0}$ beginning and ending in 0 to obtain a $\unicode[STIX]{x1D705}$ -branching bundle graph (although in this case, the sequence we start with may not correspond to the sequence of depths for the bundle graph).

With this labeling in mind, we are now in the position to give a non-recursive definition of a bundle graph that is equivalent to Definition 2.1. Note that two adjacent vertices $u$ and $v$ of a bundle graph must differ in height by exactly 1. And recall that if $u$ and $v$ are adjacent and were created during parallel composition of a bundle graph $G^{\prime }$ , then $u$ and $v$ must be in the same copy of  $G^{\prime }$ .

Definition 2.4. Given a finite sequence $W=(w_{r})_{r=0}^{M+1}\subseteq \mathbb{N}_{0}$ such that $w_{0}=w_{M+1}=0$ and a cardinality $\unicode[STIX]{x1D705}$ , the $\unicode[STIX]{x1D705}$ -branching bundle graph associated with $W$ is $T_{W,\unicode[STIX]{x1D705}}=(V,E)$ , defined by

$$\begin{eqnarray}\displaystyle V & = & \displaystyle \{(r,A)\mid r\in [M+1]\text{ and }A\in \unicode[STIX]{x1D705}^{w_{r}}\},\nonumber\\ \displaystyle E & = & \displaystyle \{\{(r,A),(s,B)\}\subseteq V\mid |r-s|=1\text{ and }A\preccurlyeq B\}.\nonumber\end{eqnarray}$$

The vertices $(0,\emptyset )$ and $(M+1,\emptyset )$ in $V$ are called the bottom and top, respectively, of $T_{W,\unicode[STIX]{x1D705}}$ .

We illustrate in Figure 1 a typical bundle graph with its vertex labeling.

Figure 1

$T_{W,\unicode[STIX]{x1D705}}$ with $W=(0,0,1,0,0,2,1,1,1,2,1,0)$ and $\unicode[STIX]{x1D705}=2$ .

Now that we have a way to represent a bundle graph with Definition 2.4, the next order of business is deriving a formula for the shortest-path metric.

By Lemma 2.7, a path between two vertices $u=(r,A)$ and $v=(s,B)$ in a bundle graph must contain a vertex $(t,C)$ such that both $C\preccurlyeq A$ and $C\preccurlyeq B$ . There are two cases to consider when trying to create a shortest path between $u$ and $v$ : either such a vertex $(t,C)$ can be found so that $t$ is between $r$ and $s$ , or not. In either case we have $w_{t}=|C|\leqslant |A\wedge B|$ .

We introduce some notation to differentiate these two possibilities. Given two vertices $u=(r,A)$ and $v=(s,B)$ in a bundle graph, we will write $u\Updownarrow v$ to mean that there is $t\in [M+1]$ between $r$ and $s$ (inclusive) such that $w_{t}\leqslant |A\wedge B|$ . We will write $u~\cancel{\Updownarrow }~v$ to mean the opposite. Note, in particular, that if $A\preccurlyeq B$ or $B\preccurlyeq A$ , then $u\Updownarrow v$ , and if $u~\cancel{\Updownarrow }~v$ , then $|A\wedge B|<\min \{|A|,|B|\}$ .

We show in the following proposition that the distance between a vertex in a bundle graph and one of its ancestors or descendants is simply the difference in height between the two. By Lemma 2.7, finding the distance between two arbitrary vertices in a bundle graph thus amounts to finding a highest common ancestor or lowest common descendant of the two vertices.

For example, using Figure 1, one may see that $(5,(1,1))-(6,(1))-(7,(1))-(8,(1))-(9,(1,0))$ is a shortest path between $(5,(1,1))$ and $(9,(1,0))$ . But a path between $(5,(1,1))$ and $(9,(0,1))$ must first go through either $(4,\emptyset )$ or $(11,\emptyset )$ .

Given two vertices $u=(r,A)$ and $v=(s,B)$ in a bundle graph $T_{W,\unicode[STIX]{x1D705}}$ , we define $n(u,v)$ and $m(u,v)$ by

$$\begin{eqnarray}\displaystyle n(u,v) & = & \displaystyle \max \{t\in [M+1]\mid w_{t}\leqslant |A\wedge B|\text{and }t\leqslant \min \{r,s\}\},\nonumber\\ \displaystyle m(u,v) & = & \displaystyle \min \{t\in [M+1]\mid w_{t}\leqslant |A\wedge B|\text{and }t\geqslant \max \{r,s\}\}.\nonumber\end{eqnarray}$$

Following the definitions, one sees that if $u~\cancel{\Updownarrow }~v$ , then $(n(u,v),A\wedge B\restriction _{w_{n(u,v)}})$ is the highest common ancestor of $u$ and $v$ and $(m(u,v),A\wedge B\restriction _{w_{m(u,v)}})$ is the lowest common descendant of $u$ and $v$ .

Proposition 2.9. Let $T_{W,\unicode[STIX]{x1D705}}=(V,E)$ be a bundle graph with shortest-path metric $d$ , and fix $u=(r,A)$ and $v=(s,B)$ in $V$ . Then

Proof. By the definition of the edge set $E$ , $d(u,v)\geqslant |r-s|$ . Suppose first that $A\preccurlyeq B$ . Recursively construct the sequence $(C_{i})_{i=0}^{|r-s|}$ by letting

$$\begin{eqnarray}C_{0}=\left\{\begin{array}{@{}ll@{}}A,\quad & r\leqslant s,\\ B,\quad & s<r,\end{array}\right.\end{eqnarray}$$

and given $C_{i-1}$ for $i\in [|r-s|]\setminus \{0\}$ , choosing $C_{i}\in \unicode[STIX]{x1D705}^{w_{\min \{r,s\}+i}}$ so that $C_{i-1}\wedge C_{i}\in \{C_{i-1},C_{i}\}$ and $C_{i}\wedge B\in \{C_{i},B\}$ . Then $((\min \{r,s\}+i,C_{i}))_{i=0}^{|r-s|}$ is a path between $u$ and $v$ , and so $d(u,v)\leqslant |r-s|$ . That is, $d(u,v)=|r-s|$ . The case $B\preccurlyeq A$ is similar.

Now, if $u\Updownarrow v$ , then there is $t$ between $r$ and $s$ such that $|A\wedge B|\geqslant w_{t}$ . Thus, by what was shown above,

$$\begin{eqnarray}\displaystyle d(u,v) & {\leqslant} & \displaystyle d(u,(t,A\wedge B\restriction _{w_{t}}))+d((t,A\wedge B\restriction _{w_{t}}),v)\nonumber\\ \displaystyle & = & \displaystyle |r-t|+|t-s|\nonumber\\ \displaystyle & = & \displaystyle |r-s|\nonumber\end{eqnarray}$$

and so $d(u,v)=|r-s|$ .

If $u~\cancel{\Updownarrow }~v$ , then by Lemma 2.7 a shortest path between $u$ and $v$ must contain a vertex that is either a common ancestor or a common descendant of $u$ and $v$ . The result follows from what was shown above by taking the minimum of lengths of paths between $u$ and $v$ that contain either the highest common ancestor or lowest common descendant.◻

Continuing our example from Figure 1, one may check that $w_{7}=1\leqslant |(1)|=|(1,1)\wedge (1,0)|$ . Thus $(5,(1,1))\Updownarrow (9,(1,0))$ and so $d((5,(1,1)),(9,(1,0)))=9-5=4$ by Proposition 2.9. Similarly, there is no $t\in [11]$ between $5$ and $9$ such that $w_{t}\leqslant 0=|\emptyset |=|(1,1)\wedge (0,1)|$ , meaning $(5,(1,1))~\cancel{\Updownarrow }~(9,(1,0))$ . One may determine that $n((5,(1,1)),(9,(0,1)))=4$ and $m((5,(1,1)),(9,(0,1)))=11$ . By Proposition 2.9, $d((5,(1,1)),(9,(0,1)))=\min \{5+9-2\cdot 4,2\cdot 11-(9+5)\}=6$ .

Throughout the next few sections, we describe various bi-Lipschitz embeddings of bundle graphs into Banach spaces. We define now the notation that will regularly be used, and fix for the rest of the paper $W=(w_{r})_{r=0}^{M+1}\subseteq \mathbb{N}_{0}$ such that $w_{0}=w_{M+1}=0$ . For $r\in [M+1]$ and $i\in \mathbb{N}_{0}$ , define $x(r,i)$ , $y(r,i)$ , and $z(r,i)$ by

(2) $$\begin{eqnarray}\displaystyle x(r,i) & = & \displaystyle \left\{\begin{array}{@{}ll@{}}0,\quad & i=0,\\ \max \{t\in [M+1]\mid w_{t}<i\text{ and }t\leqslant r\},\quad & i>0,\end{array}\right.\end{eqnarray}$$

(3) $$\begin{eqnarray}\displaystyle y(r,i) & = & \displaystyle \left\{\begin{array}{@{}ll@{}}M+1,\quad & i=0,\\ \min \{t\in [M+1]\mid w_{t}<i\text{ and }t\geqslant r\},\quad & i>0,\end{array}\right.\end{eqnarray}$$

(4) $$\begin{eqnarray}\displaystyle z(r,i) & = & \displaystyle \left\{\begin{array}{@{}ll@{}}r,\quad & i=0,\\ \min \{r-x(r,i),y(r,i)-r\},\quad & i>0.\end{array}\right.\end{eqnarray}$$

Given $r\in [M+1]$ and $i\in \mathbb{N}$ , $x(r,i)$ records the last height no greater than $r$ in which the vertices of a bundle graph associated with $W$ have depth less than $i$ . Similarly, $y(r,i)$ records the first height no lesser than $r$ in which the vertices of a bundle graph associated with $W$ have depth less than $i$ . And $z(r,i)$ simply records the distance one would have to travel from height $r$ to get to a vertex with depth less than $i$ in a bundle graph associated with $W$ . Note that $x(r,i)=y(r,i)=r$ and $z(r,i)=0$ for $i>w_{r}$ .

Consider $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ for some cardinality $\unicode[STIX]{x1D705}$ . If $u~\cancel{\Updownarrow }~v$ (recall this means there is no $t\in [M+1]$ between $r$ and $s$ such that $w_{t}\leqslant |A\wedge B|$ ), then a comparison of the definitions of $n(u,v)$ and $m(u,v)$ with notations (2) and (3), respectively, yields $n(u,v)=x(r,|A\wedge B|+1)=\,x(s,|A\wedge B|+1)$ and $m(u,v)=y(r,|A\wedge B|+1)=y(s,|A\wedge B|+1)$ . This fact will be used repeatedly in the proofs to follow.

3 Embedding into Banach spaces with good $\ell _{\infty }$ -trees

In this section, we show that for any countable cardinality $\unicode[STIX]{x1D705}$ , $T_{W,\unicode[STIX]{x1D705}}$ is bi-Lipschitzly embeddable into any Banach space with a good $\ell _{\infty }$ -tree of height $\max W$ with distortion bounded above by a constant depending only on the good $\ell _{\infty }$ -tree.

The given definition is a finite height analogue of [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4, Definition 3.1]. The first condition states that every “branch” $(y_{B})_{B\preccurlyeq A}$ of the good $\ell _{\infty }$ -tree is $C^{2}$ -equivalent to the unit vector basis of $\ell _{\infty }^{n+1}$ . The second condition states that the sequence making up the good $\ell _{\infty }$ -tree is basic with basis constant less than or equal to $D$ . Note that the condition on the enumeration implies $\unicode[STIX]{x1D70E}_{0}=\emptyset$ .

Theorem 3.2 below generalizes [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4, Theorem 3.1]. The proof we show here has the same main idea as the proof in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4], but is much shorter due to the fact that we fix at the beginning a single bundle graph, rather than prove the result for an entire family of bundle graphs. This gets rid of a lengthy induction argument.

Theorem 3.2. Fix a countable cardinality $\unicode[STIX]{x1D705}$ and suppose $X$ is a Banach space containing a $(C,D)$ -good $\ell _{\infty }$ -tree $(y_{\unicode[STIX]{x1D70E}_{i}})_{i=0}^{\infty }$ of height $\max W$ for some $C,D>0$ . Then there is a bi-Lipschitz embedding $\unicode[STIX]{x1D713}:T_{W,\unicode[STIX]{x1D705}}\rightarrow X$ such that for all $u,v\in V(T_{W,\unicode[STIX]{x1D705}})$ ,

$$\begin{eqnarray}\frac{1}{3D(1+D)}d(u,v)\leqslant \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\leqslant Cd(u,v),\end{eqnarray}$$

where $d$ is the shortest-path metric for $T_{W,\unicode[STIX]{x1D705}}$ , and furthermore,

$$\begin{eqnarray}\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\geqslant d(u,v)/D\end{eqnarray}$$

when $u\Updownarrow v$ .

Proof. Define the map $\unicode[STIX]{x1D713}:T_{W,\unicode[STIX]{x1D705}}\rightarrow X$ by

$$\begin{eqnarray}\unicode[STIX]{x1D713}((r,A))=\mathop{\sum }_{B\preccurlyeq A}z(r,|B|)y_{B}\end{eqnarray}$$

(see notation (4) in the previous section) for every $(r,A)\in V(T_{W,\unicode[STIX]{x1D705}})$ .

Take any $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ and suppose first that $u$ and $v$ are adjacent with $A\preccurlyeq B$ (implying $w_{r}\leqslant w_{s}$ ). Then,

$$\begin{eqnarray}\displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X} & = & \displaystyle \biggl\|\mathop{\sum }_{E\preccurlyeq A}z(r,|E|)y_{E}-\mathop{\sum }_{E\preccurlyeq B}z(s,|E|)y_{E}\biggr\|_{X}\nonumber\\ \displaystyle & = & \displaystyle \biggl\|\mathop{\sum }_{E\preccurlyeq B}(z(r,|E|)-z(s,|E|))y_{E}\biggr\|_{X}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle C\max _{0\leqslant i\leqslant w_{s}}\{|z(r,i)-z(s,i)|\}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle C,\nonumber\end{eqnarray}$$

where the second line follows from the assumption that $A\preccurlyeq B$ and the fact that $z(r,i)=0$ for $w_{r}<i\leqslant w_{s}$ , the third line from property $(i)$ of the $\ell _{\infty }$ -tree, and the last line from the assumption that $|r-s|=1$ . The triangle inequality applied to shortest paths then shows that $\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\leqslant Cd(u,v)$ for all $u,v\in V(T_{W,\unicode[STIX]{x1D705}})$ .

For the left-hand inequality, take any $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ , and suppose first that $u\Updownarrow v$ . Then property (ii) of the $\ell _{\infty }$ -tree yields

$$\begin{eqnarray}\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\geqslant \frac{1}{D}|z(r,0)-z(s,0)|=\frac{1}{D}|r-s|=\frac{1}{D}d(u,v).\end{eqnarray}$$

Suppose now that $u~\cancel{\Updownarrow }~v$ . As mentioned in the last paragraph of the previous section, note that $n(u,v)=x(r,|A\wedge B|+1)=x(s,|A\wedge B|+1)$ and $m(u,v)=y(r,|A\wedge B|+1)=y(s,|A\wedge B|+1)$ . Let $n_{1}\in \mathbb{N}_{0}$ be such that $\unicode[STIX]{x1D70E}_{n_{1}}\preccurlyeq A$ and $|\unicode[STIX]{x1D70E}_{n_{1}}|=|A\wedge B|+1$ . Similarly, let $n_{2}\in \mathbb{N}_{0}$ be such that $\unicode[STIX]{x1D70E}_{n_{2}}\preccurlyeq B$ and $|\unicode[STIX]{x1D70E}_{n_{2}}|=|A\wedge B|+1$ . For $i\in \mathbb{N}_{0}$ , let

$$\begin{eqnarray}\unicode[STIX]{x1D6FC}_{i}=\left\{\begin{array}{@{}ll@{}}z(r,|\unicode[STIX]{x1D70E}_{i}|)-z(s,|\unicode[STIX]{x1D70E}_{i}|),\quad & \unicode[STIX]{x1D70E}_{i}\preccurlyeq A\wedge B,\\ z(r,|\unicode[STIX]{x1D70E}_{i}|),\quad & A\wedge B\prec \unicode[STIX]{x1D70E}_{i}\preccurlyeq A,\\ -z(s,|\unicode[STIX]{x1D70E}_{i}|),\quad & A\wedge B\prec \unicode[STIX]{x1D70E}_{i}\preccurlyeq B,\\ 0\quad & \text{otherwise}.\end{array}\right.\end{eqnarray}$$

Then, by property (ii) of the $\ell _{\infty }$ -tree and Proposition 2.9,

$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\nonumber\\ \displaystyle & & \displaystyle \quad =\mathop{\biggl\|\mathop{\sum }_{i=0}^{\infty }\unicode[STIX]{x1D6FC}_{i}y_{\unicode[STIX]{x1D70E}_{i}}\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{1}{D}\max \biggl\{\mathop{\biggl\|\mathop{\sum }_{i=0}^{n_{1}}\unicode[STIX]{x1D6FC}_{i}y_{\unicode[STIX]{x1D70E}_{i}}\biggr\|}\nolimits_{X},\mathop{\biggl\|\mathop{\sum }_{i=0}^{n_{2}}\unicode[STIX]{x1D6FC}_{i}y_{\unicode[STIX]{x1D70E}_{i}}\biggr\|}\nolimits_{X},\Vert \unicode[STIX]{x1D6FC}_{0}y_{\emptyset }\Vert _{X}\biggr\}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{1}{D(1+D)}\max \{|\unicode[STIX]{x1D6FC}_{n_{1}}|,|\unicode[STIX]{x1D6FC}_{n_{2}}|,|\unicode[STIX]{x1D6FC}_{0}|\}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{D(1+D)}\max \{z(r,|A\wedge B|+1),z(s,|A\wedge B|+1),|z(r,0)-z(s,0)|\}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{D(1+D)}\max \left\{\min \{r-n(u,v),m(u,v)-r\},\right.\nonumber\\ \displaystyle & & \displaystyle \quad \left.\min \{s-n(u,v),m(u,v)-s\},|r-s|\right\}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{1}{3D(1+D)}d(u,v).\square\nonumber\end{eqnarray}$$

It was also shown in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4] (see Theorem 3.2 of that paper) that any reflexive Banach space with an unconditional asymptotic structure that is not asymptotically uniformly convexifiable will contain $(1+\unicode[STIX]{x1D700},1+\unicode[STIX]{x1D700})$ -good $\ell _{\infty }$ -trees of arbitrary height, for any $\unicode[STIX]{x1D700}>0$ . Thus, Theorem 3.2 of this paper yields the following corollary.

Finally, in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4] it was shown (see Theorem 4.1 of that paper) that if a Banach space $X$ is asymptotically midpoint uniformly convexifiable, then no family of bundle graphs with non-trivial (meaning there is a vertex with non-zero depth) $\aleph _{0}$ -branching base graph is equi-bi-Lipschitzly embeddable into $X$ . This fact combined with Corollary 3.4 actually shows that the non-equi-bi-Lipschitz embeddability of any family of bundle graphs generated by a non-trivial $\aleph _{0}$ -branching bundle graph characterizes asymptotic uniform convexifiability within the class of reflexive Banach spaces with an asymptotic unconditional structure. We recall the definition of a family of bundle graphs generated from a base graph in §6.

4 Embedding into $L_{1}$

In this section we show that for any countable cardinality $\unicode[STIX]{x1D705}$ , $T_{W,\unicode[STIX]{x1D705}}$ is bi-Lipschitzly embeddable into $L_{1}([0,M+1])$ (equipped with Lebesgue measure $\unicode[STIX]{x1D706}$ ) with distortion bounded above by 2. Note however that for finite $\unicode[STIX]{x1D705}$ , $T_{W,\unicode[STIX]{x1D705}}$ belongs to the family of series-parallel graphs and so is already known to be bi-Lipschitzly embeddable into $\ell _{1}$ with distortion bounded above by 2 (see [Reference Chakrabarti, Jaffe, Lee and Vincent8]). That this distortion bound is optimal follows from work done in [Reference Lee and Raghavendra14]. For each $v\in V(T_{W,\unicode[STIX]{x1D705}})$ , we map $v$ to the characteristic function of some set. To get the distortion we desire, we need to make sure that the symmetric differences of the sets involved are large enough in Lebesgue measure. The construction is somewhat technical, but is essentially done through intersections of supports of independent Bernoulli random variables.

Let $D$ be any common multiple of the numbers in $[M+1]\setminus \{0\}$ . Let ${\mathcal{F}}$ be the family of all finite unions of open subintervals of $[0,M+1]$ such that for each $P\in {\mathcal{F}}$ , there is $N\in \mathbb{N}_{0}$ such that each maximal (with respect to set containment) subinterval of $P$ is equal to $(qD/D^{N+1},(qD+r)/D^{N+1})$ for some $q\in [(M+1)D^{N}-1]$ and $r\in [D]$ ; and given $P\in {\mathcal{F}}$ , let $N(P)$ be the minimum of such $N$ associated with $P$ . Note here that if $P,P^{\prime }\in {\mathcal{F}}$ are such that $N(P)<N(P^{\prime })$ , then every subinterval of $P^{\prime }$ is either contained in a subinterval of $P$ or has empty intersection with $P$ .

Let $(\unicode[STIX]{x1D70E}_{i})_{i=0}^{\infty }$ be an enumeration of $\aleph _{0}^{{\leqslant}\max W}$ and let $(P_{i})_{i=0}^{\infty }$ be an enumeration of ${\mathcal{F}}$ such that $P_{0}=\emptyset$ and $N(P_{i})\leqslant i$ for all $i\in \mathbb{N}_{0}$ . For each $i,j\in \mathbb{N}_{0}$ , let $\unicode[STIX]{x1D703}(i,j)=2^{i}3^{j}-N(P_{j})$ . Define $f:\mathbb{\aleph }_{0}^{{\leqslant}\max W}\times {\mathcal{F}}\times [D]\rightarrow {\mathcal{F}}$ by

$$\begin{eqnarray}f(\unicode[STIX]{x1D70E}_{i},P_{j},k)=\mathop{\bigcup }_{\ell =0}^{n}\mathop{\bigcup }_{m=0}^{D^{\unicode[STIX]{x1D703}(i,j)}-1}\biggl(\unicode[STIX]{x1D6FC}_{\ell }+\frac{mD(\unicode[STIX]{x1D6FD}_{\ell }-\unicode[STIX]{x1D6FC}_{\ell })}{D^{\unicode[STIX]{x1D703}(i,j)+1}},\unicode[STIX]{x1D6FC}_{\ell }+\frac{(mD+k)(\unicode[STIX]{x1D6FD}_{\ell }-\unicode[STIX]{x1D6FC}_{\ell })}{D^{\unicode[STIX]{x1D703}(i,j)+1}}\biggr)\end{eqnarray}$$

whenever $P_{j}=\bigsqcup _{\ell =0}^{n}(\unicode[STIX]{x1D6FC}_{\ell },\unicode[STIX]{x1D6FD}_{\ell })$ (where $\sqcup$ means disjoint union), for all $i,j\in \mathbb{N}_{0}$ and $k\in [D]$ .

We list the properties we need from $f$ in the following lemma, but one may think of $f(A,P,k)$ as the intersection of $P$ with the support of a Bernoulli random variable that has probability of success equal to $k/D$ . And if $B\neq A$ , then $f(B,P,k)$ is also such an intersection, but with a Bernoulli random variable that is independent from that used for $f(A,P,k)$ .

Proof. (i) This is obvious from the definition of $f$ .

(ii) Every maximal subinterval of $P_{j}$ has length less than or equal to $1/D^{N(P_{j})}$ , so by the definition of $f$ , every maximal subinterval of $f(\unicode[STIX]{x1D70E}_{i},P_{j},k)$ has length less than or equal to

$$\begin{eqnarray}\frac{k}{D^{\unicode[STIX]{x1D703}(i,j)+1}}\cdot \frac{1}{D^{N(P_{j})}}=\frac{k}{D^{2^{i}3^{j}+1}}\leqslant \frac{1}{D^{2^{i}3^{j}}}.\end{eqnarray}$$

This means $N(f(\unicode[STIX]{x1D70E}_{i},P_{j},k))\geqslant 2^{i}3^{j}-1$ . Similarly, every (non-trivial) maximal subinterval of $P_{j}$ has length greater than or equal to $1/D^{N(P_{j})+1}$ , and so every (non-trivial) maximal subinterval of $f(\unicode[STIX]{x1D70E}_{i},P_{j},k)$ has length greater than or equal to

$$\begin{eqnarray}\frac{k}{D^{\unicode[STIX]{x1D703}(i,j)+1}}\cdot \frac{1}{D^{N(P_{j})+1}}=\frac{k}{D^{2^{i}3^{j}+2}}\geqslant \frac{1}{D^{2^{i}3^{j}+2}}.\end{eqnarray}$$

Therefore $N(f(\unicode[STIX]{x1D70E}_{i},P_{j},k))\leqslant 2^{i}3^{j}+2$ .

(iii) Supposing $P_{j}=\bigsqcup _{\ell =0}^{n}(\unicode[STIX]{x1D6FC}_{\ell },\unicode[STIX]{x1D6FD}_{\ell })$ , then

$$\begin{eqnarray}\unicode[STIX]{x1D706}(f(\unicode[STIX]{x1D70E}_{i},P_{j},k))=\mathop{\sum }_{\ell =0}^{n}\mathop{\sum }_{m=0}^{D^{\unicode[STIX]{x1D703}(i,j)}-1}\frac{k(\unicode[STIX]{x1D6FD}_{\ell }-\unicode[STIX]{x1D6FC}_{\ell })}{D^{\unicode[STIX]{x1D703}(i,j)+1}}=\frac{k}{D}\mathop{\sum }_{\ell =0}^{n}(\unicode[STIX]{x1D6FD}_{\ell }-\unicode[STIX]{x1D6FC}_{\ell })=\frac{k}{D}\unicode[STIX]{x1D706}(P_{j}).\end{eqnarray}$$

(iv) Since $N(P)<N(P_{j})$ , every subinterval of $P_{j}$ is either contained in a subinterval of $P$ or has empty intersection with $P$ . Thus, if $P_{j}=\bigsqcup _{\ell =0}^{n}(\unicode[STIX]{x1D6FC}_{\ell },\unicode[STIX]{x1D6FD}_{\ell })$ and $I=\{\ell \in [n]\mid (\unicode[STIX]{x1D6FC}_{\ell },\unicode[STIX]{x1D6FD}_{\ell })\subseteq P\}$ , then

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}(P\cap f(\unicode[STIX]{x1D70E}_{i},P_{j},k)) & = & \displaystyle \mathop{\sum }_{\ell \in I}\mathop{\sum }_{m=0}^{D^{\unicode[STIX]{x1D703}(i,j)}-1}\frac{k(\unicode[STIX]{x1D6FD}_{\ell }-\unicode[STIX]{x1D6FC}_{\ell })}{D^{\unicode[STIX]{x1D703}(i,j)+1}}\nonumber\\ \displaystyle & = & \displaystyle \frac{k}{D}\mathop{\sum }_{\ell \in I}(\unicode[STIX]{x1D6FD}_{\ell }-\unicode[STIX]{x1D6FC}_{\ell })=\frac{k}{D}\unicode[STIX]{x1D706}(P\cap P_{j}).\square\nonumber\end{eqnarray}$$

We are now ready to define the sets needed for our bi-Lipschitz embedding. This is done by recursively defining the sets based on the depths of the vertices in our bundle graph. At any given depth we construct the sets out of subsets of the sets that were defined for the previous depth. If a vertex has height $r$ and depth $0$ , we assign the set $[0,r]$ to this vertex. Suppose there are vertices at heights $r\leqslant s$ with depth $0$ and $v$ is a vertex with depth $1$ at height halfway between $r$ and $s$ . We assign a set of measure $r+(s-r)/2$ to $v$ by taking the union of $[0,r]$ with half of the set $[0,s]\setminus [0,r]$ . So for instance, we might assign the set $[0,r]\cup [r,(s-r)/2]$ to $v$ . However, there will be another vertex with depth $1$ at the same height as $v$ (if $\unicode[STIX]{x1D705}>1$ ). For this vertex, we need to assign a different set of measure $r+(s-r)/2$ , so we take half of the set $[0,s]\setminus [0,r]$ in a way that is independent of the way we did it with $v$ . For instance, we might use $[0,r]\cup [r,(s-r)/4]\cup [(s-r)/2,3(s-r)/4]$ . A similar process for all depths is used until every vertex has a subset of $[0,M+1]$ assigned to it with Lebesgue measure equal to its height. We use the function $f$ defined above to take care of the independent selection of sets. At this point we fix for the rest of the section a countable cardinality $\unicode[STIX]{x1D705}$ . The formal construction follows (recall notations (2) and (3) from §2).

Given $v=(r,A)\in V(T_{W,\unicode[STIX]{x1D705}})$ , define the sets $S_{x}(v,i)$ and $S_{y}(v,i)$ in ${\mathcal{F}}$ for $i\in [w_{r}]$ recursively by

$$\begin{eqnarray}\displaystyle S_{x}(v,0) & = & \displaystyle [0,x(r,1)]\setminus [x(r,1)],\nonumber\\ \displaystyle S_{y}(v,0) & = & \displaystyle [0,y(r,1)]\setminus [y(r,1)],\nonumber\end{eqnarray}$$

and

$$\begin{eqnarray}\displaystyle S_{x}(v,i) & = & \displaystyle f\biggl(A\restriction _{i},S_{y}(v,i-1)\setminus \text{clos}(S_{x}(v,i-1)),\frac{x(r,i+1)-x(r,i)}{y(r,i)-x(r,i)}D\biggr),\nonumber\\ \displaystyle S_{y}(v,i) & = & \displaystyle f\biggl(A\restriction _{i},S_{y}(v,i-1)\setminus \text{clos}(S_{x}(v,i-1)),\frac{y(r,i+1)-x(r,i)}{y(r,i)-x(r,i)}D\biggr),\nonumber\end{eqnarray}$$

for $i\in [w_{r}]\setminus \{0\}$ . Finally, let $S(v)=\text{clos}(\bigcup _{i=0}^{w_{r}}S_{x}(v,i))$ .

Lemma 4.3. Fix $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ . Then

Proof. Let $K=|A\wedge B|$ . Suppose first that $u\Updownarrow v$ and $r\leqslant s$ . Then $y(r,K+1)\leqslant x(s,K+1)$ . Let $n\in [K]$ be such that $x(s,i)<y(r,i)$ (which implies $x(s,i)=x(r,i)$ and $y(s,i)=y(r,i)$ ) for all $i\in [n]$ while $y(r,n+1)\leqslant x(s,n+1)$ . An easy induction argument shows that $S_{x}(u,i)=S_{x}(v,i)$ and $S_{y}(u,i)=S_{y}(v,i)$ for all $i\in [n-1]$ , and $S_{y}(u,n)\subseteq S_{x}(v,n)$ . Another easy induction argument and Lemma 4.1(i) shows $S_{x}(u,i)\subseteq \bigcup _{j=0}^{n}S_{x}(v,j)$ for all $i\in [w_{r}]$ by, and so Lemma 4.2(v) yields

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706}(S(u)\cap S(v)) & = & \displaystyle \unicode[STIX]{x1D706}\biggl(\mathop{\bigcup }_{i=0}^{w_{r}}S_{x}(u,i)\cap \mathop{\bigcup }_{j=0}^{w_{s}}S_{x}(v,j)\biggr)\nonumber\\ \displaystyle & = & \displaystyle \unicode[STIX]{x1D706}\biggl(\mathop{\bigcup }_{i=0}^{w_{r}}S_{x}(u,i)\biggr)=x(r,w_{r}+1)=r.\nonumber\end{eqnarray}$$

Suppose now that $u~\cancel{\Updownarrow }~v$ . Then $x(r,i)=x(s,i)$ and $y(r,i)=y(s,i)$ for all $i\in [K+1]$ , and so $S_{x}(u,i)=S_{x}(v,i)$ and $S_{y}(u,i)=S_{y}(v,i)$ for all $i\in [K]$ , by an easy induction argument. Note that $x(r,K+1)=x(s,K+1)=n(u,v)$ and $y(r,K+1)=y(s,K+1)=m(u,v)$ . For any $i\in [w_{r}]\setminus [K]$ and $j\in [w_{s}]\setminus [K]$ , repeated applications of Lemma 4.1(ii) and (iv) and then Lemma 4.2(iii) show

$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D706} (S_{x}(u,i) & \cap & \displaystyle S_{x}(v,j))\nonumber\\ \displaystyle & = & \displaystyle \frac{x(r,i+1)-x(r,i)}{y(r,K+1)-x(r,K+1)}\cdot \frac{x(s,j+1)-x(s,j)}{y(s,K+1)-x(s,K+1)}\nonumber\\ \displaystyle & & \displaystyle \cdot \,\unicode[STIX]{x1D706}(S_{y}(u,K)\setminus S_{x}(u,K))\nonumber\\ \displaystyle & = & \displaystyle \frac{(x(r,i+1)-x(r,i))(x(s,j+1)-x(s,j))}{m(u,v)-n(u,v)}.\nonumber\end{eqnarray}$$

This with Lemma 4.2(iv) and (v) implies

$$\begin{eqnarray}\displaystyle & & \displaystyle \unicode[STIX]{x1D706}(S(u)\cap S(v))\nonumber\\ \displaystyle & & \displaystyle =\unicode[STIX]{x1D706}\biggl(\mathop{\bigcup }_{i=0}^{w_{r}}S_{x}(u,i)\cap \mathop{\bigcup }_{j=0}^{w_{s}}S_{x}(v,j)\biggr)\nonumber\\ \displaystyle \quad & & \displaystyle =x(r,K+1)+\mathop{\sum }_{i=K+1}^{w_{r}}\mathop{\sum }_{j=K+1}^{w_{s}}\frac{(x(r,i+1)-x(r,i))(x(s,j+1)-x(s,j))}{m(u,v)-n(u,v)}\nonumber\\ \displaystyle \quad & & \displaystyle =x(r,K+1)+\frac{(x(r,w_{r}+1)-x(r,K+1))(y(s,w_{s}+1)-y(s,K+1))}{m(u,v)-n(u,v)}\nonumber\\ \displaystyle \quad & & \displaystyle =n(u,v)+\frac{(r-n(u,v))(s-n(u,v))}{m(u,v)-n(u,v)}.\square\nonumber\end{eqnarray}$$

The next theorem generalizes [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4, Theorem 3.3] (and our earlier lemmas likewise generalized Lemma 3.6 and its discussion in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4]). We once again follow the same line of thought in our proof as in the proof in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4], but again our proof is shorter. This time we have still used a recursive process to define the embedding (this has been absorbed in our lemmas), but it has been made simpler by again fixing a single bundle graph at the beginning and performing the recursion over the depths of its vertices.

Theorem 4.4. There is a bi-Lipschitz embedding $\unicode[STIX]{x1D713}:T_{W,\unicode[STIX]{x1D705}}\rightarrow L_{1}$ such that for all $u,v\in V(T_{W,\unicode[STIX]{x1D705}})$ ,

$$\begin{eqnarray}{\textstyle \frac{1}{2}}d(u,v)\leqslant \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}}\leqslant d(u,v),\end{eqnarray}$$

where $d$ is the shortest-path metric for $T_{W,\unicode[STIX]{x1D705}}$ , and furthermore

$$\begin{eqnarray}\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}}=d(u,v)\end{eqnarray}$$

when $u\Updownarrow v$ .

Proof. Define the map $\unicode[STIX]{x1D713}:T_{W,\unicode[STIX]{x1D705}}\rightarrow L_{1}$ by $\unicode[STIX]{x1D713}(v)=\unicode[STIX]{x1D712}_{S(v)}$ for every $v\in V(T_{W,\unicode[STIX]{x1D705}})$ .

Take any $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ and suppose first that $u\Updownarrow v$ . By Lemmas 4.2(v) and 4.3,

$$\begin{eqnarray}\displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}} & = & \displaystyle \unicode[STIX]{x1D706}(S(u))+\unicode[STIX]{x1D706}(S(v))-2\unicode[STIX]{x1D706}(S(u)\cap S(v))\nonumber\\ \displaystyle & = & \displaystyle r+s-2\min \{r,s\}=|r-s|=d(u,v).\nonumber\end{eqnarray}$$

Lemma 2.7 and the triangle inequality applied to shortest paths then shows that $\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}}\leqslant d(u,v)$ for all $u,v\in V(T_{W,\unicode[STIX]{x1D705}})$ .

Suppose now that $u~\cancel{\Updownarrow }~v$ . By Lemmas 4.2(v) and 4.3,

$$\begin{eqnarray}\displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}} & = & \displaystyle \unicode[STIX]{x1D706}(S(u))+\unicode[STIX]{x1D706}(S(v))-2\unicode[STIX]{x1D706}(S(u)\cap S(v))\nonumber\\ \displaystyle & = & \displaystyle r+s-2n(u,v)-2\frac{(r-n(u,v))(s-n(u,v))}{m(u,v)-n(u,v)}\nonumber\\ \displaystyle & = & \displaystyle \unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}-2\frac{\unicode[STIX]{x1D6FC}\unicode[STIX]{x1D6FD}}{\unicode[STIX]{x1D6FE}},\nonumber\end{eqnarray}$$

where $\unicode[STIX]{x1D6FC}=r-n(u,v)$ , $\unicode[STIX]{x1D6FD}=s-n(u,v)$ , and $\unicode[STIX]{x1D6FE}=m(u,v)-n(u,v)$ . Suppose first that $\max \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}\leqslant \frac{1}{2}\unicode[STIX]{x1D6FE}$ . Then by Proposition 2.9 and the above,

$$\begin{eqnarray}\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}}\geqslant \unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}-\min \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}=\max \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}\geqslant {\textstyle \frac{1}{2}}d(u,v).\end{eqnarray}$$

Suppose next that $\min \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}\leqslant \frac{1}{2}\unicode[STIX]{x1D6FE}\leqslant \max \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}$ . Then by Proposition 2.9 and the above,

$$\begin{eqnarray}\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}}=\min \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}+\max \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}\biggl(1-2\frac{\min \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}}{\unicode[STIX]{x1D6FE}}\biggr)\geqslant \frac{1}{2}\unicode[STIX]{x1D6FE}\geqslant \frac{1}{2}d(u,v).\end{eqnarray}$$

Finally, suppose $\frac{1}{2}\unicode[STIX]{x1D6FE}\leqslant \min \{\unicode[STIX]{x1D6FC},\unicode[STIX]{x1D6FD}\}$ . Then by Proposition 2.9 and the above,

$$\begin{eqnarray}\displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{L_{1}} & = & \displaystyle \frac{1}{2\unicode[STIX]{x1D6FE}}(2\unicode[STIX]{x1D6FC}\unicode[STIX]{x1D6FE}+2\unicode[STIX]{x1D6FD}\unicode[STIX]{x1D6FE}-4\unicode[STIX]{x1D6FC}\unicode[STIX]{x1D6FD})\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2\unicode[STIX]{x1D6FE}}(\unicode[STIX]{x1D6FE}^{2}-(2\unicode[STIX]{x1D6FC}-\unicode[STIX]{x1D6FE})(2\unicode[STIX]{x1D6FD}-\unicode[STIX]{x1D6FE}))\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \frac{1}{2\unicode[STIX]{x1D6FE}}(\unicode[STIX]{x1D6FE}^{2}-(\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}-\unicode[STIX]{x1D6FE})\unicode[STIX]{x1D6FE})\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}(2\unicode[STIX]{x1D6FE}-(\unicode[STIX]{x1D6FC}+\unicode[STIX]{x1D6FD}))\nonumber\\ \displaystyle & = & \displaystyle \frac{1}{2}d(u,v).\Box \nonumber\end{eqnarray}$$

5 Embedding into Banach spaces with ESA bases

In this section we show that for any finite cardinality $\unicode[STIX]{x1D705}$ , $T_{W,\unicode[STIX]{x1D705}}$ is bi-Lipschitzly embeddable into any Banach space with an ESA (equal-signs-additive) basis with distortion bounded above by a constant depending only on $W$ .

The properties ESA, SA, and IS were first defined and studied by Brunel and Sucheston in [Reference Brunel and Sucheston6] and [Reference Brunel and Sucheston7]. In [Reference Brunel and Sucheston7], they show that a sequence is ESA if and only if it is SA, and that every ESA sequence is also an IS basis for its linear span. We will use these facts without mention. More information about ESA sequences can be found in [Reference Brunel and Sucheston7] and [Reference Argyros, Motakis and Sari1].

To construct the embedding, we follow roughly the same procedure as used in the previous section. However, with $L_{1}$ we were able to subdivide the interval $[0,M+1]$ as finely as needed to accommodate the bundle graph. That is, we could use the existence of infinitely many independent Bernoulli random variables. If instead of $L_{1}$ , we try to embed into a general Banach space with a basis, we still need independent Bernoulli random variables to choose the support of an embedded vertex, but the random variables are now discrete. In other words, the more vertices in our graph we have to embed, the further down the basis we have to go if we want to mimic the procedure used for $L_{1}$ . This and the fact that we do not have an explicitly defined norm anymore make the argument more subtle.

We fix now for the rest of this section a finite cardinality $\unicode[STIX]{x1D705}$ and let $\unicode[STIX]{x1D707}=|\unicode[STIX]{x1D705}^{{\leqslant}\max W}|\in \mathbb{N}$ . We also fix an independent collection $\{Y_{i}\}_{i=1}^{\unicode[STIX]{x1D707}}$ of Bernoulli random variables defined on $[2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ (equipped with the uniform probability measure) with probability of success equal to $1/2$ . Concretely, for each $i\in [\unicode[STIX]{x1D707}]\setminus \{0\}$ , we may define $Y_{i}:[2^{\unicode[STIX]{x1D707}}]\setminus \{0\}\rightarrow \{0,1\}$ by

$$\begin{eqnarray}Y_{i}(j)=\left\{\begin{array}{@{}ll@{}}1,\quad & j\equiv n\;(\text{mod}\,2^{\unicode[STIX]{x1D707}-(i-1)})\text{ for some }n\in [2^{\unicode[STIX]{x1D707}-i}]\setminus \{0\},\\ 0\quad & \text{otherwise},\end{array}\right.\end{eqnarray}$$

for all $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ . For each $j\in \mathbb{N}$ , let $I_{j}=[j(M+1)]\setminus [(j-1)(M+1)]$ , and let ${\mathcal{F}}_{j}$ be the family of subsets of $I_{j}$ such that for each $P\in {\mathcal{F}}_{j}$ , either $P=\emptyset$ , or $P\neq \emptyset$ and $|P|=\max (P)-\min (P)+1$ (which implies $P$ has no “gaps”). That is, we break up the natural number line into blocks of size $M+1$ and let ${\mathcal{F}}_{j}$ be the family of intervals contained in the the $j$ th block.

Let $\{\unicode[STIX]{x1D70E}_{i}\}_{i=0}^{\unicode[STIX]{x1D707}}$ be an enumeration of $\unicode[STIX]{x1D705}^{{\leqslant}\max W}$ . For $A\in \unicode[STIX]{x1D705}^{{\leqslant}\max W}$ and $i\in [\unicode[STIX]{x1D707}]$ , we let $Y_{A}=Y_{i}$ if $A=\unicode[STIX]{x1D70E}_{i}$ . Define for each $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ the function $f_{j}:\unicode[STIX]{x1D705}^{{\leqslant}\max W}\times {\mathcal{F}}_{j}\times [M]\rightarrow {\mathcal{F}}_{j}$ by

$$\begin{eqnarray}f_{j}(\unicode[STIX]{x1D70E}_{i},P,k)=I_{j}\cap \{Y_{i}(j)(\inf P+\ell ),(1-Y_{i}(j))(\sup P-\ell )\}_{\ell =0}^{k-1}\end{eqnarray}$$

for all $i\in [\unicode[STIX]{x1D707}]$ , $P\in {\mathcal{F}}_{j}$ , and $k\in [M]$ .

To summarize what is happening, we assign independent Bernoulli random variables to the elements of $\unicode[STIX]{x1D705}^{{\leqslant}\max W}$ . Given $A\in \unicode[STIX]{x1D705}^{{\leqslant}\max W}$ with its assigned random variable $Y_{A}$ and an interval $P$ in $I_{j}$ , $f_{j}(A,P,k)$ will take the first $k$ elements of $P$ in $I_{j}$ if $Y_{A}(j)=1$ and the last $k$ elements if $Y_{A}(j)=0$ . Note that $f_{j}(\unicode[STIX]{x1D70E}_{i},P,k)\subseteq P$ if $k\leqslant |P|$ . Thus, if $P$ is a union of subintervals of the $I_{j}$ , we can use the $f_{j}$ to simultaneously select $k$ elements from $P$ out of each interval $P\cap I_{j}$ , and these selections will be independent for different elements of $\unicode[STIX]{x1D705}^{{\leqslant}\max W}$ . This is quite analogous to what happened in the last section. The construction of the supports of our embedded vertices is likewise similar, but in the end we cannot just map a vertex to a characteristic function. We have to modify slightly in order to use the ESA property to obtain a good distortion (again, recall notations (2) and (3) from §2).

Given $v=(r,A)\in V(T_{W,\unicode[STIX]{x1D705}})$ and $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ , define the sets $S_{x,j}(v,i)$ and $S_{y,j}(v,i)$ in ${\mathcal{F}}_{j}$ for $i\in [w_{r}]$ recursively by

$$\begin{eqnarray}\displaystyle S_{x,j}(v,0) & = & \displaystyle [(j-1)(M+1)+x(r,1)]\setminus [(j-1)(M+1)],\nonumber\\ \displaystyle S_{y,j}(v,0) & = & \displaystyle [(j-1)(M+1)+y(r,1)]\setminus [(j-1)(M+1)],\nonumber\end{eqnarray}$$

and

$$\begin{eqnarray}\displaystyle S_{x,j}(v,i) & = & \displaystyle f_{j}(A\restriction _{i},S_{y,j}(v,i-1)\setminus S_{x,j}(v,i-1),x(r,i+1)-x(r,i)),\nonumber\\ \displaystyle S_{y,j}(v,i) & = & \displaystyle f_{j}(A\restriction _{i},S_{y,j}(v,i-1)\setminus S_{x,j}(v,i-1),y(r,i+1)-x(r,i)),\nonumber\end{eqnarray}$$

for $i\in [w_{r}]\setminus \{0\}$ ; and then define

$$\begin{eqnarray}S_{j}(v)=\mathop{\bigcup }_{i=0}^{w_{r}}S_{x,j}(v,i).\end{eqnarray}$$

Finally, let

$$\begin{eqnarray}\displaystyle S_{j,+}(v) & = & \displaystyle \{(j-1)(M+1)+n\mid n\in S_{j}(v)\},\nonumber\\ \displaystyle S_{j,-}(v) & = & \displaystyle \{(3j-1)(M+1)-n\mid n\in S_{j}(v)\}.\nonumber\end{eqnarray}$$

$S_{j,+}$ will take a copy of $S_{j}(V)$ and put it in $I_{2j-1}$ . $S_{j,-}$ will also take a copy of $S_{j}(V)$ and put it in $I_{2j}$ . The copy for $S_{j,-}$ , however, is backwards. That is, $S_{j,-}$ is a reflection of $S_{j,+}$ across the middle of $I_{2j-1}\cup I_{2j}$ . The purpose of this is to allow us to take advantage of the subadditivity of an ESA basis later.

At this point we are almost ready to define the embedding, but we need to be able to make sure that for enough $j\in [\unicode[STIX]{x1D707}]\setminus \{0\}$ , the symmetric difference of $S_{j}(u)$ and $S_{j}(v)$ is large enough when $u\neq v\in V(T_{W,\unicode[STIX]{x1D705}})$ . Unfortunately, the amount of $j\in [\unicode[STIX]{x1D707}]\setminus \{0\}$ we can do this for depends on $W$ . We define the parameter $p_{W}$ to be the minimum of all $p\in \mathbb{N}$ such that for all $r\in [M+1]$ and $i\in \mathbb{N}_{0}$ ,

• ∙ $x(r,i+p)\geqslant (x(r,i)+y(r,i))/2$ whenever $r\geqslant (x(r,i)+y(r,i))/2$ .

• ∙ $y(r,i+p)\leqslant (x(r,i)+y(r,i))/2$ whenever $r\leqslant (x(r,i)+y(r,i))/2$ .

One may easily check that $p_{W}\leqslant \max W+1$ .

Lemma 5.3. Fix $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ such that $u~\cancel{\Updownarrow }~v$ and $r\leqslant s$ . Let

$$\begin{eqnarray}\displaystyle {\mathcal{I}}_{u,v} & = & \displaystyle \{\!j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}~|~Y_{B\restriction _{|A\wedge B|+n}}(j)=1\nonumber\\ \displaystyle & & \displaystyle \quad \text{and }Y_{A\restriction _{|A\wedge B|+n}}(j)=0\text{ for all }n\in [p_{W}]\setminus \{0\}\!\}\!.\nonumber\end{eqnarray}$$

Then for each $j\in {\mathcal{I}}_{u,v}$ , there is ${\mathcal{L}}_{j}\subseteq \bigcup _{k=|A\wedge B|+1}^{w_{s}}S_{x,j}(v,k)$ such that:

1. (i) $|{\mathcal{L}}_{j}|\geqslant d(u,v)/2$ , where $d$ is the shortest-path metric for $T_{W,\unicode[STIX]{x1D705}}$ ;

2. (ii) $\max {\mathcal{L}}_{j}<\inf \bigcup _{k=|A\wedge B|+1}^{w_{r}}S_{x,j}(u,k)$ .

Proof. Let $K=|A\wedge B|$ . We have $x(r,i)=x(s,i)$ and $y(r,i)=y(s,i)$ for all $i\in [K+1]$ , and so $S_{x,j}(u,i)=S_{x,j}(v,i)$ and $S_{y,j}(u,i)=S_{y,j}(v,i)$ for all $i\in [K]$ , by an easy induction argument. Note that $x(r,K+1)=x(s,K+1)=n(u,v)$ and $y(r,K+1)=y(s,K+1)=m(u,v)$ , which implies $|S_{y,j}(v,K)\setminus S_{x,j}(v,K)|=m(u,v)-n(u,v)>0$ , by Lemma 5.2(iii). Note that $x(r,i)\leqslant x(s,i)$ and $y(r,i)\leqslant y(s,i)$ for all $i\in [M+1]$ by the fact that $r\leqslant s$ .

Suppose first that $s\leqslant (m(u,v)+n(u,v))/2$ and let ${\mathcal{L}}_{j}=\bigcup _{k=K+1}^{w_{s}}S_{x,j}(v,k)$ for each $j\in {\mathcal{I}}_{u,v}$ . Then by definition of $p_{W}$ ,

$$\begin{eqnarray}\displaystyle & & \displaystyle \min S_{y,j}(v,K)\setminus S_{x,j}(v,K)+y(s,K+p_{W}+1)-n(u,v)-1\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \min S_{y,j}(v,K)\setminus S_{x,j}(v,K)+\frac{m(u,v)-n(u,v)}{2}-1\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \max S_{y,j}(u,K)\setminus S_{x,j}(u,K)-\biggl(\frac{m(u,v)-n(u,v)}{2}-1\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad \leqslant \max S_{y,j}(u,K)\setminus S_{x,j}(u,K)-(y(r,K+p_{W}+1)-n(u,v)-1),\nonumber\end{eqnarray}$$

and so, by Lemma 5.2(viii) and (ix), ${\mathcal{L}}_{j}\cap (\bigcup _{k=K+1}^{w_{r}}S_{x,j}(u,k))=\emptyset$ and therefore $\max {\mathcal{L}}_{j}<\inf \bigcup _{k=K+1}^{w_{r}}S_{x,j}(u,k)$ for each $j\in {\mathcal{I}}_{u,v}$ . Moreover, by Lemma 5.2(v) and Proposition 2.9,

$$\begin{eqnarray}|{\mathcal{L}}_{j}|=x(s,w_{s}+1)-x(s,K+1)=s-n(u,v)\geqslant d(u,v)/2\end{eqnarray}$$

for each $j\in {\mathcal{I}}_{u,v}$ .

Suppose now that $r\geqslant (m(u,v)+n(u,v))/2$ and let

for each $j\in {\mathcal{I}}_{u,v}$ . Then by definition of $p_{W}$ ,

$$\begin{eqnarray}\displaystyle & & \displaystyle \min S_{y,j}(v,K)\setminus S_{x,j}(v,K)+x(s,K+p_{W}+1)-n(u,v)-1\nonumber\\ \displaystyle & & \displaystyle \qquad \geqslant \min S_{y,j}(v,K)\setminus S_{x,j}(v,K)+\frac{m(u,v)-n(u,v)}{2}-1\nonumber\\ \displaystyle & & \displaystyle \qquad \geqslant \max S_{y,j}(u,K)\setminus S_{x,j}(u,K)-\biggl(\frac{m(u,v)-n(u,v)}{2}-1\biggr)\nonumber\\ \displaystyle & & \displaystyle \qquad \geqslant \max S_{y,j}(u,K)\setminus S_{x,j}(u,K)-(x(r,K+p_{W}+1)-n(u,v)-1),\nonumber\end{eqnarray}$$

and so, by Lemma 5.2(viii) and (ix), ${\mathcal{L}}_{j}\cup (\bigcup _{k=K+1}^{w_{r}}S_{x,j}(u,k))=S_{y,j}(v,K)\setminus S_{x,j}(v,K)$ and therefore, by Lemma 5.2(v) and Proposition 2.9,

$$\begin{eqnarray}\displaystyle |{\mathcal{L}}_{j}| & = & \displaystyle |S_{y,j}(v,i)\setminus S_{x,j}(v,i)|-\biggl|\biggl(\mathop{\bigcup }_{k=K+1}^{w_{r}}S_{x,j}(u,k)\biggr)\biggr|\nonumber\\ \displaystyle & = & \displaystyle (m(u,v)-n(u,v))-(r-n(u,v))=m(u,v)-r\geqslant d(u,v)/2\nonumber\end{eqnarray}$$

for each $j\in {\mathcal{I}}_{u,v}$ . Moreover, $\max {\mathcal{L}}_{j}<\inf \bigcup _{k=K+1}^{w_{r}}S_{x,j}(u,k)$ for each $j\in {\mathcal{I}}_{u,v}$ .

Finally, suppose $r\leqslant (m(u,v)+n(u,v))/2\leqslant s$ and let

$$\begin{eqnarray}{\mathcal{L}}_{j}=\{\min S_{y,j}(v,K)\setminus S_{x,K}(v,i)+\ell \}_{\ell =0}^{(m(u,v)-n(u,v))/2-1}\end{eqnarray}$$

for each $j\in {\mathcal{I}}_{u,v}$ . Then by definition of $p_{W}$ ,

$$\begin{eqnarray}\displaystyle \max {\mathcal{L}}_{j} & {\leqslant} & \displaystyle \min \{\!\min S_{y,j}(v,K)\setminus S_{x,j}(v,K)\nonumber\\ \displaystyle & & \displaystyle +\,x(s,K+p_{W}+1)-n(u,v)-1,\nonumber\\ \displaystyle & & \displaystyle \max S_{y,j}(u,K)\setminus S_{x,j}(u,K)\nonumber\\ \displaystyle & & \displaystyle -\,(y(r,K+p_{W}+1)-n(u,v)-1)\!\},\nonumber\end{eqnarray}$$

and so, by Lemma 5.2(viii) and (ix), ${\mathcal{L}}_{j}\subseteq \bigcup _{k=K+1}^{w_{s}}S_{x,j}(v,k)$ and $\max {\mathcal{L}}_{j}<\inf \bigcup _{k=K+1}^{w_{r}}S_{x,j}(u,k)$ for each $j\in {\mathcal{I}}_{u,v}$ . Moreover, by Proposition 2.9, $|{\mathcal{L}}_{j}|=(m(u,v)-n(u,v))/2\geqslant d(u,v)/2$ for each $j\in {\mathcal{I}}_{u,v}$ .◻

The next theorem (combined with the two previous lemmas) generalizes the results and procedures found in [Reference Ostrovskii and Randrianantoanina17, §3]. As in the previous two sections, the techniques we use are largely inspired from the source, with perhaps the most important differences being the introduction of the parameter $p_{W}$ and the fixing of a single bundle graph at the beginning. And as before, both the labeling and recursive procedure here are simpler, with the main difficulty being taken care of in Lemma 5.3.

Theorem 5.4. Suppose $X$ is a Banach space with an ESA basis $(e_{n})_{n=1}^{\infty }$ . Then there is a bi-Lipschitz embedding $\unicode[STIX]{x1D713}:T_{W,\unicode[STIX]{x1D705}}\rightarrow X$ such that for all $u,v\in V(T_{W,\unicode[STIX]{x1D705}})$ ,

$$\begin{eqnarray}\frac{1}{2^{2p_{W}+1}}d(u,v)\leqslant \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\leqslant d(u,v),\end{eqnarray}$$

where $d$ is the shortest-path metric for $T_{W,\unicode[STIX]{x1D705}}$ , and furthermore $\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}=d(u,v)$ when $u\Updownarrow v$ .

Proof. Let $\unicode[STIX]{x1D702}=\Vert \sum _{j=1}^{2^{\unicode[STIX]{x1D707}}}e_{2j-1}-e_{2j}\Vert _{X}$ and define the map $\unicode[STIX]{x1D713}:T_{W,\unicode[STIX]{x1D705}}\rightarrow X$ by

$$\begin{eqnarray}\unicode[STIX]{x1D713}(v)=1/\unicode[STIX]{x1D702}\mathop{\sum }_{j=1}^{2^{\unicode[STIX]{x1D707}}}\biggl(\mathop{\sum }_{n\in S_{j,+}(v)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(v)}e_{n}\biggr)\end{eqnarray}$$

for every $v\in V(T_{W,\unicode[STIX]{x1D705}})$ .

Take any $u=(r,A)$ and $v=(s,B)$ in $V(T_{W,\unicode[STIX]{x1D705}})$ . Let $K=|A\wedge B|$ and suppose first that $u\Updownarrow v$ and $r\leqslant s$ . Then $y(r,K+1)\leqslant x(s,K+1)$ . Let $n\in [K]$ be such that $x(s,i)<y(r,i)$ (which implies $x(r,i)=x(s,i)$ and $y(r,i)=y(s,i)$ ) for all $i\in [n]$ while $y(r,n+1)\leqslant x(s,n+1)$ . An easy induction argument shows that $S_{x,j}(u,i)=S_{x,j}(v,i)$ and $S_{y,j}(u,i)=S_{y,j}(v,i)$ for all $i\in [n]$ and $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ ; and $S_{y,j}(u,n)\subseteq S_{x,j}(v,n)$ for all $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ . Another easy induction argument shows $S_{x,j}(u,i)\subseteq \bigcup _{k=0}^{n}S_{x,j}(v,k)$ for all $i\in [w_{r}]$ and $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ (and so $S_{j,+}(u)\subseteq S_{j,+}(v)$ and $S_{j,-}(u)\subseteq S_{j,-}(v)$ for all $j\in [2^{\unicode[STIX]{x1D707}}]\setminus \{0\}$ ). Thus, by Lemmas 2.9, 5.2(vi), and the assumption that the basis is ESA,

$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{\unicode[STIX]{x1D702}}\mathop{\biggl\|\mathop{\sum }_{j=1}^{2^{\unicode[STIX]{x1D707}}}\biggl(\biggl(\mathop{\sum }_{n\in S_{j,+}(u)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(u)}e_{n}\biggr)-\biggl(\mathop{\sum }_{n\in S_{j,+}(v)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(v)}e_{n}\biggr)\biggr)\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{\unicode[STIX]{x1D702}}\mathop{\biggl\|\mathop{\sum }_{j=1}^{2^{\unicode[STIX]{x1D707}}}\biggl(\mathop{\sum }_{n\in \cap S_{j,+}(v)\setminus S_{j,+}(u)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(v)\setminus S_{j,-}(u)}e_{n}\biggr)\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{\unicode[STIX]{x1D702}}\mathop{\biggl\|\mathop{\sum }_{j=1}^{2^{\unicode[STIX]{x1D707}}}(s-r)(e_{2j-1}-e_{2j})\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad =s-r\nonumber\\ \displaystyle & & \displaystyle \quad =d(u,v).\nonumber\end{eqnarray}$$

Lemma 2.7 and the triangle inequality applied to shortest paths then shows that $\Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\leqslant d(u,v)$ for all $u,v\in V(T_{W,\unicode[STIX]{x1D705}})$ .

Suppose now that $u~\cancel{\Updownarrow }~v$ and $r\leqslant s$ . Define ${\mathcal{I}}_{u,v}$ as in Lemma 5.3 and for each $j\in {\mathcal{I}}_{u,v}$ , let ${\mathcal{L}}_{j}$ be chosen as in Lemma 5.3. Note that, by independence of the Bernoulli random variables defined at the beginning of this section, $|{\mathcal{I}}_{u,v}|=2^{\unicode[STIX]{x1D707}-\unicode[STIX]{x1D708}}$ for some $\unicode[STIX]{x1D708}\in [2p_{W}]$ . Let

$$\begin{eqnarray}\displaystyle {\mathcal{L}}_{j,+} & = & \displaystyle \{(j-1)(M+1)+n\mid n\in {\mathcal{L}}_{j}\},\nonumber\\ \displaystyle {\mathcal{L}}_{j,+} & = & \displaystyle \{(3j-1)(M+1)-n\mid n\in {\mathcal{L}}_{j}\}.\nonumber\end{eqnarray}$$

Recall that $n\mapsto (j-1)(M+1)+n$ is a bijection from $I_{j}$ to $I_{2j-1}$ and $n\mapsto (3j-1)(M+1)-n$ is a bijection from $I_{j}$ to $I_{2j}$ for each $j\in {\mathcal{I}}_{u,v}$ . Furthermore, the images of the two maps will be reflections of each other across the middle of $I_{2j-1}\cup I_{2j}$ when the maps are applied to the same set. By Lemma 5.2(vi), Lemma 5.3, and the assumption that the basis is ESA,

$$\begin{eqnarray}\displaystyle & & \displaystyle \Vert \unicode[STIX]{x1D713}(u)-\unicode[STIX]{x1D713}(v)\Vert _{X}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{1}{\unicode[STIX]{x1D702}}\mathop{\biggl\|\mathop{\sum }_{j=1}^{2^{\unicode[STIX]{x1D707}}}\biggl(\biggl(\mathop{\sum }_{n\in S_{j,+}(u)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(u)}e_{n}\biggr)-\biggl(\mathop{\sum }_{n\in S_{j,+}(v)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(v)}e_{n}\biggr)\biggr)\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{1}{\unicode[STIX]{x1D702}}\biggl\|\mathop{\sum }_{j\in {\mathcal{I}}_{u,v}}\biggl(\biggl(\mathop{\sum }_{n\in S_{j,+}(v)}e_{n}-\mathop{\sum }_{n\in S_{j,+}(u)}e_{n}\biggr)-\biggl(\mathop{\sum }_{n\in S_{j,-}(v)}e_{n}-\mathop{\sum }_{n\in S_{j,-}(u)}e_{n}\biggr)\biggr)\biggr\|_{X}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{1}{\unicode[STIX]{x1D702}}\biggl\|\mathop{\sum }_{j\in {\mathcal{I}}_{u,v}}\biggl(\mathop{\sum }_{n\in {\mathcal{L}}_{j,+}}e_{n}-\mathop{\sum }_{n\in {\mathcal{L}}_{j,-}}e_{n}\biggr)\biggr\|_{X}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{d(u,v)}{2\unicode[STIX]{x1D702}}\biggl\|\mathop{\sum }_{j\in {\mathcal{I}}_{u,v}}(e_{2j-1}-e_{2j})\biggr\|_{X}\nonumber\\ \displaystyle & & \displaystyle \quad =\frac{d(u,v)}{2\unicode[STIX]{x1D702}}\cdot \frac{1}{2^{\unicode[STIX]{x1D708}}}\cdot \mathop{\sum }_{k=1}^{2^{\unicode[STIX]{x1D708}}}\mathop{\biggl\|\mathop{\sum }_{j=(k-1)2^{\unicode[STIX]{x1D707}-\unicode[STIX]{x1D708}}+1}^{k2^{\unicode[STIX]{x1D707}-\unicode[STIX]{x1D708}}}(e_{2j-1}-e_{2j})\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{d(u,v)}{2^{\unicode[STIX]{x1D708}+1}\unicode[STIX]{x1D702}}\mathop{\biggl\|\mathop{\sum }_{j=1}^{2^{\unicode[STIX]{x1D707}}}(e_{2j-1}-e_{2j})\biggr\|}\nolimits_{X}\nonumber\\ \displaystyle & & \displaystyle \quad \geqslant \frac{1}{2^{2p_{W}+1}}d(u,v).\square\nonumber\end{eqnarray}$$

We show in the next section that actually the entire family of bundle graphs generated by $T_{W,\unicode[STIX]{x1D705}}$ is bi-Lipschitzly embeddable with the same distortion bound of $2^{2p_{W}+1}$ into a Banach space with an ESA basis.

6 The $\oslash$ -product

Given two $\unicode[STIX]{x1D705}$ -branching bundle graphs $G$ and $H$ , we can define a new $\unicode[STIX]{x1D705}$ -branching bundle graph $G\oslash H$ by replacing every edge in $G$ with a copy of $H$ (where the bottom of $H$ is identified with the lower endpoint of the edge $H$ is replacing and the top of $H$ is identified with the higher endpoint). The definition of $\oslash$ -product seems to have first been formally introduced by Lee and Raghavendra in [Reference Lee and Raghavendra14], although the family of 2-branching diamond graphs (see the comment under Definition 6.5 for a definition involving $\oslash$ -products) were studied in [Reference Gupta, Newman, Rabinovich and Sinclair10] and [Reference Newman and Rabinovich16].

For this section we fix another sequence $W^{\prime }=\{w_{r}^{\prime }\}_{r=0}^{M^{\prime }+1}\subseteq \mathbb{N}_{0}$ such that $w_{0}^{\prime }=w_{M^{\prime }+1}^{\prime }=0$ . We will show how to determine $W^{\prime \prime }$ so that $T_{W,\unicode[STIX]{x1D705}}\oslash T_{W^{\prime },\unicode[STIX]{x1D705}}=T_{W^{\prime \prime },\unicode[STIX]{x1D705}}$ . Once $W^{\prime \prime }$ is found, we can use Theorem 5.4 to find a bound on the worst distortion for a bi-Lipschitz embedding of $T_{W^{\prime \prime },\unicode[STIX]{x1D705}}$ into a Banach space with an ESA basis. In particular, we show that the distortion bound found in Theorem 5.4 is no worse for $T_{W,\unicode[STIX]{x1D705}}\oslash T_{W,\unicode[STIX]{x1D705}}$ than it was for $T_{W,\unicode[STIX]{x1D705}}$ , allowing us to generalize the characterizations of superreflexivity found in [Reference Johnson and Schechtman11] and [Reference Ostrovskii and Randrianantoanina17].

Given a bundle graph $G=(V,E)$ and $n\in \mathbb{N}_{0}$ , let $V_{n}=\{v\in V\mid \text{height}(v)=n\}$ and let $E_{n}=\{\{u,v\}\in E\mid u\in V_{n}\text{ and }v\in V_{n+1}\}$ . If another bundle graph $H$ is given, we may create a new bundle graph $G\oslash _{n}H$ by replacing every edge in $E_{n}$ with $H$ for some $n$ . Explicitly, if $G=(V,E)$ and $H=(V^{\prime },E^{\prime })$ , and if $b$ and $t$ are the bottom and top, respectively, of $H$ ; then we define $G\oslash _{n}H=(V^{\prime \prime },E^{\prime \prime })$ by

$$\begin{eqnarray}V^{\prime \prime }=V\cup (E_{n}\times (V^{\prime }\setminus \{b,t\}))\end{eqnarray}$$

and

$$\begin{eqnarray}\displaystyle & & \displaystyle E^{\prime \prime }=\{e\in E\mid e\cap (V_{n}\cup V_{n+1})=\emptyset \}\nonumber\\ \displaystyle & & \displaystyle \cup \,\{\{u,(e,v)\}\mid e\in E_{n},~u\in V_{n}\cap e,\text{ and }\{b,v\}\in E^{\prime }\}\nonumber\\ \displaystyle & & \displaystyle \cup \,\{\{u,(e,v)\}\mid e\in E_{n},~u\in V_{n+1}\cap e,\text{ and }\{v,t\}\in E^{\prime }\}\nonumber\\ \displaystyle & & \displaystyle \cup \,\{\{(e,u),(e,v)\}\mid e\in E_{n}\text{ and }(\{u,v\}\setminus \{b,t\})\in E^{\prime }\}.\nonumber\end{eqnarray}$$

The formal definition of $G\oslash H$ is similar (just remove the subscripts and the first term in the definition of $E^{\prime \prime }$ ). It is clear that $G\oslash H$ can be created by performing $\oslash _{n}$ -products repeatedly until all the edges that were originally in $G$ have been replaced.

Lemma 6.1. Given $n\in [M]$ , the graph $T_{W,\unicode[STIX]{x1D705}}\oslash _{n}T_{W^{\prime },\unicode[STIX]{x1D705}}$ is the same bundle graph as $T_{W^{\prime \prime },\unicode[STIX]{x1D705}}$ , where $W^{\prime \prime }=(w_{r}^{\prime \prime })_{r=0}^{M+M^{\prime }+1}\subseteq \mathbb{N}_{0}$ is defined by

$$\begin{eqnarray}w_{r}^{\prime \prime }=\left\{\begin{array}{@{}ll@{}}w_{r},\quad & 0\leqslant i\leqslant n,\\ \max \{w_{n},w_{n+1}\}+w_{i-n}^{\prime },\quad & n<r<n+M^{\prime }+1,\\ w_{r-M^{\prime }},\quad & n+M^{\prime }+1\leqslant r\leqslant M+M^{\prime }+1.\end{array}\right.\end{eqnarray}$$

Proof. We simply provide the graph isomorphism, and leave the details to the reader. Define $F:T_{W,\unicode[STIX]{x1D705}}\oslash T_{W^{\prime },\unicode[STIX]{x1D705}}\rightarrow T_{W^{\prime \prime }}$ by

$$\begin{eqnarray}F(v)=\left\{\begin{array}{@{}ll@{}}(r,A),\quad & v=(r,A)\text{ and }r\leqslant n,\\ (n+r,B^{\frown }C),\quad & v=(\{(n,A),(n+1,B)\},(r,C))\text{ and }A\preccurlyeq B,\\ (n+r,A^{\frown }C),\quad & v=(\{(n,A),(n+1,B)\},(r,C))\text{ and }B\preccurlyeq A,\\ (r+M^{\prime }+1,A),\quad & v=(r,A)\text{ and }r>n,\end{array}\right.\end{eqnarray}$$

for each $v\in V(T_{W,\unicode[STIX]{x1D705}}\oslash _{n}T_{W^{\prime },\unicode[STIX]{x1D705}})$ .◻

With repeated application of Lemma 6.1, we obtain the following formula.

Proposition 6.2. The graph $T_{W,\unicode[STIX]{x1D705}}\oslash T_{W^{\prime },\unicode[STIX]{x1D705}}$ is graph-isomorphic to $T_{W^{\prime \prime },\unicode[STIX]{x1D705}}$ where $W^{\prime \prime }=(w_{r}^{\prime \prime })_{r=0}^{(M+1)(M^{\prime }+1)}\subseteq \mathbb{N}_{0}$ is defined by $w_{0}^{\prime \prime }=0$ and

$$\begin{eqnarray}w_{r}^{\prime \prime }=\left\{\begin{array}{@{}ll@{}}\max \{w_{n},w_{n+1}\}+w_{r-n(M^{\prime }+1)}^{\prime },\quad & n(M^{\prime }+1)<r<(n+1)(M^{\prime }+1),\\ w_{n+1},\quad & r=(n+1)(M^{\prime }+1),\end{array}\right.\end{eqnarray}$$

for all $n\in [M]$ .

Proposition 6.2 confirms what is to be expected regarding the depths of vertices in $T_{W,\unicode[STIX]{x1D705}}\oslash T_{W^{\prime },\unicode[STIX]{x1D705}}$ . Namely, that vertices in $T_{W,\unicode[STIX]{x1D705}}\oslash T_{W^{\prime },\unicode[STIX]{x1D705}}$ that originated from $T_{W,\unicode[STIX]{x1D705}}$ will keep the same depth as they originally had, and vertices that arise from a copy of $T_{W^{\prime },\unicode[STIX]{x1D705}}$ replacing an edge of $T_{W,\unicode[STIX]{x1D705}}$ would keep the same depths as they originally had, except that the maximum depth of the endpoints of the edge being replaced will be added to these depths. We now fix $W^{\prime \prime }$ obtained in Proposition 6.2. For what follows, we define the functions $x^{\prime }$ and $y^{\prime }$ for $W^{\prime }$ , and $x^{\prime \prime }$ and $y^{\prime \prime }$ for $W^{\prime \prime }$ , in the same way $x$ and $y$ were defined for $W$ (notations (2) and (3)) at the end of §2.

Corollary 6.3. For each $n\in [M]$ , let $K_{n}=\max \{w_{n},w_{n+1}\}$ . Then for all $n\in [M]$ , $r\in [(n+1)(M^{\prime }+1)]\setminus [n(M^{\prime }+1)]$ , and $i\in \mathbb{N}_{0}$ ,

$$\begin{eqnarray}\displaystyle x^{\prime \prime }(r,i) & = & \displaystyle \left\{\begin{array}{@{}ll@{}}(M^{\prime }+1)x(n+1,i),\quad & r=(n+1)(M^{\prime }+1),\\ (M^{\prime }+1)x(n,i),\quad & r\neq (n+1)(M^{\prime }+1)\text{ and }i\leqslant K_{n},\\ n(M^{\prime }+1)\quad & \\ \,\,+\,x^{\prime }(r-n(M^{\prime }+1),i-K_{n})\quad & \text{otherwise},\end{array}\right.\nonumber\\ \displaystyle y^{\prime \prime }(r,i) & = & \displaystyle \left\{\begin{array}{@{}ll@{}}(M^{\prime }+1)y(n+1,i),\quad & r=(n+1)(M^{\prime }+1)\text{ or }i\leqslant K_{n},\\ n(M^{\prime }+1)\quad & \\ \,\,+\,y^{\prime }(r-n(M^{\prime }+1),i-K_{n})\quad & \text{otherwise}.\end{array}\right.\nonumber\end{eqnarray}$$

In the next lemma we define $p_{W^{\prime }}$ for $W^{\prime }$ and $p_{W^{\prime \prime }}$ for $W^{\prime \prime }$ in the same way $p_{W}$ was defined for $W$ before Lemma 5.3 in the last section.

Lemma 6.4. The parameter $p_{W^{\prime \prime }}$ satisfies the inequality

$$\begin{eqnarray}p_{W^{\prime \prime }}\leqslant \max \{p_{W},p_{W^{\prime }}\}.\end{eqnarray}$$

Proof. Let $r\in [(M+1)(M^{\prime }+1)]$ and $i\in \mathbb{N}_{0}$ be such that $r\geqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ and suppose first that $r=(n+1)(M^{\prime }+1)$ for some $n\in [M]$ (the case $r=0$ is trivial). Then after using Corollary 6.3 and dividing by $M^{\prime }+1$ , we see that $n+1\geqslant (x(n+1,i)+y(n+1,i))/2$ , which, by definition of $p_{W}$ , implies $x(n+1,i+p_{W})\geqslant (x(n+1),i)+y(n+1,i))/2$ . By multiplying by $M^{\prime }+1$ and again using Corollary 6.3, we see that $x^{\prime \prime }(r,i+p_{W})\geqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ .

Suppose now that $n(M^{\prime }+1)<r<(n+1)(M^{\prime }+1)$ for some $n\in [M]$ and $i>K_{n}$ (where $K_{n}=\max \{w_{n},w_{n+1}\})$ . Then after using Corollary 6.3 and subtracting $n(M^{\prime }+1)$ , we see that $r-n(M^{\prime }+1)\geqslant (x^{\prime }(r-n(M^{\prime }+1),i-K_{n})+y^{\prime }(r-n(M^{\prime }+1),i-K_{n}))/2$ , which, by definition of $p_{W^{\prime }}$ implies $x^{\prime }(r-n(M^{\prime }+1),i-K_{n}+p_{W^{\prime }})\geqslant (x^{\prime }(r-n(M^{\prime }+1),i-K_{n})+y^{\prime }(r-n(M^{\prime }+1),i-K_{n}))/2$ . By adding $n(M^{\prime }+1)$ and again using Corollary 6.3, we see that $x^{\prime \prime }(r,i+p_{W^{\prime }})\geqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ .

Suppose finally that $n(M^{\prime }+1)<r<(n+1)(M^{\prime }+1)$ for some $n\in [M]$ and $i\leqslant K_{n}$ . Suppose further that $w_{n}<i\leqslant w_{n+1}$ . Then $x(n,i)=n$ and $y(n+1,i)>n+1$ . Thus, after applying Corollary 6.3 and then dividing by $M^{\prime }+1$ , we have

$$\begin{eqnarray}n+1>r/(M^{\prime }+1)\geqslant (n+y(n+1,i))/2,\end{eqnarray}$$

which implies $n+1\geqslant y(n+1,i)$ , a contradiction. Therefore, in order for the hypothesis to hold true, either $i\leqslant \min \{w_{n},w_{n+1}\}$ or $w_{n+1}<w_{n}$ . In either case, $y(n,i)=y(n+1,i)$ . So after applying Corollary 6.3 and dividing by $M^{\prime }+1$ , we have

$$\begin{eqnarray}n+1>(x(n,i)+y(n+1,i))/2=(x(n,i)+y(n,i))/2.\end{eqnarray}$$

This means $n\geqslant (x(n,i)+y(n,i))/2$ and so, by definition of $p_{W}$ , $x(n,i+p_{W})\geqslant (x(n,i)+y(n,i))/2=(x(n,i)+y(n+1,i))/2$ . After multiplying by $M^{\prime }+1$ and again applying Corollary 6.3, we have

$$\begin{eqnarray}\displaystyle x^{\prime \prime }(r,i+p_{W}) & {\geqslant} & \displaystyle x^{\prime \prime }(n(M^{\prime }+1),i+p_{W})\nonumber\\ \displaystyle & {\geqslant} & \displaystyle (x^{\prime \prime }(n(M^{\prime }+1),i)+y^{\prime \prime }((n+1)(M^{\prime }+1),i))/2\nonumber\\ \displaystyle & = & \displaystyle (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2.\nonumber\end{eqnarray}$$

We have shown that for all $r\in [(M+1)(M^{\prime }+1)]$ and $i\in \mathbb{N}_{0}$ , $x^{\prime \prime }(r,i+\max \{p_{W},p_{W^{\prime }}\})\geqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ whenever $r\geqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ . Similarly it can be shown $y^{\prime \prime }(r,i+\max \{p_{W},p_{W^{\prime }}\})\leqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ whenever $r\leqslant (x^{\prime \prime }(r,i)+y^{\prime \prime }(r,i))/2$ . Therefore $p_{W^{\prime \prime }}\leqslant \max \{p_{W},p_{W^{\prime }}\}$ .◻

There are a few families of bundle graphs that have earned special names. Given a cardinality $\unicode[STIX]{x1D705}$ , the family of $\unicode[STIX]{x1D705}$ -branching diamonds is the family generated by $T_{(0,1,0),\unicode[STIX]{x1D705}}$ , the family of $\unicode[STIX]{x1D705}$ -branching Laakso graphs is the family generated by $T_{(0,0,1,0,0),\unicode[STIX]{x1D705}}$ , and the family of $\unicode[STIX]{x1D705}$ -branching parasol graphs is the family generated by $T_{(0,0,1,0),\unicode[STIX]{x1D705}}$ . Diamond graphs seem to have first been introduced in [Reference Gupta, Newman, Rabinovich and Sinclair10] and [Reference Newman and Rabinovich16]. Laakso graphs were first introduced in [Reference Lang and Plaut13], based on ideas found in [Reference Laakso12]. Parasol graphs were first introduced in [Reference Dilworth, Kutzarova and Randrianarivony9]. Lemma 6.4 and Theorem 5.4 yield the following corollary.

Now that we have formally defined families of bundle graphs generated by a base graph, we come to the characterizations of Banach space properties via non-equi-bi-Lipschitz embeddability of families of graphs, as promised in the introduction. Work done by Brunel and Sucheston ([Reference Brunel and Sucheston7] and [Reference Brunel and Sucheston6], see also [Reference Ostrovskii and Randrianantoanina17, Theorem 2.3]), shows that for every non-reflexive Banach space $X$ , there is a Banach space with an ESA basis that is finitely representable in $X$ ; and so every family of bundle graphs generated by a finitely branching bundle graph is equi-bi-Lipschitzly embeddable into any non-reflexive Banach space by Theorem 5.4. Conversely, a consequence of [Reference Johnson and Schechtman11, Lemma 1, §4], says that the family of binary (that is, 2-branching) diamond graphs is not equi-bi-Lipschitzly embeddable into any Banach space with uniformly convex norm. Virtually the same proof shows that, in fact, every family of bundle graphs generated by a non-trivial bundle graph is not equi-bi-Lipschitzly embeddable into a Banach space with uniformly convex norm. Every superreflexive Banach space is uniformly convexifiable, so we have the following characterization(s) of superreflexivity.

Theorem 3.2 in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4] shows that within the class of reflexive Banach spaces with an unconditional structure, a Banach space that is not asymptotically uniformly convexifiable will contain $(1+\unicode[STIX]{x1D700},1+\unicode[STIX]{x1D700})$ -good $\ell _{\infty }$ trees of arbitrary height for all $\unicode[STIX]{x1D700}>0$ . Theorem 4.1 in [Reference Baudier, Causey, Dilworth, Kutzarova, Randrianarivony, Schlumprecht and Zhang4] then shows that every family of bundle graphs generated by a non-trivial infinitely branching bundle graph is not equi-bi-Lipschitzly embeddable into any Banach space that is asymptotically midpoint uniformly convexifiable. Thus we have the following metric characterization(s) of asymptotic uniform convexifiability within the class of reflexive Banach spaces with an unconditional asymptotic structure.