6 Coarse geometry of trees
The two obstructions below are deterministic statements about arbitrary infinite trees. They are proved over Mathlib’s SimpleGraph in its graph metric, and no hyperbolicity enters.
A map \(f\colon V\to V'\) is a \(D\)-quasi-isometry from \(G\) to \(G'\) when
for all \(x,y\), and every vertex of \(G'\) lies within \(D\) of the image. Two graphs are quasi-isometric when such a map exists for some \(D\).
A vertex \(m\) lies between \(u\) and \(v\) when every walk from \(u\) to \(v\) meets \(m\). A ray is a map \(\mathbb {N}\to V\) isometric onto its image and a line is such a map \(\mathbb {Z}\to V\). A hair at \(c\) of depth \(h\) is a component \(P\) of the complement of \(\{ c\} \) with \(d(v,c)\leq h\) for every \(v\in P\) and equality for some \(v\). Finally \(\mathrm{Ray}\) is \(\mathbb {N}\) with the path-graph structure.
Let \(f\) be a \(D\)-quasi-isometry between trees. Every vertex separating \(f(u)\) from \(f(v)\) lies within \(D\) of the image of a walk from \(u\) to \(v\).
Let \(p\) be a walk from \(u\) to \(v\), and write \(p_i\) for its \(i\)-th vertex. Suppose for a contradiction that every \(f(p_i)\) is more than \(D\) from \(m\). We show inductively that \(m\) does not lie between \(f(u)\) and \(f(p_i)\). This is clear for \(i=0\). If it fails for \(i+1\), the tree property applied at \(f(p_i)\) shows that \(m\) lies either between \(f(u)\) and \(f(p_i)\) or between \(f(p_i)\) and \(f(p_{i+1})\). The first alternative contradicts the induction hypothesis. In the second, metric additivity and the assumed lower bounds give
However, \(p_i\) and \(p_{i+1}\) are adjacent, so the upper quasi-isometry bound gives \(d'(f(p_i),f(p_{i+1}))\leq 2D\). At \(i=n\) the induction contradicts the assumption that \(m\) lies between \(f(u)\) and \(f(v)\). Hence some \(f(p_i)\) lies within \(D\) of \(m\).
A tree carrying hairs of unbounded depth is not quasi-isometric to a tree all of whose vertices lie within a bounded distance of a line.
Suppose that \(f\) is a \(D\)-quasi-isometry, and choose a hair \(P\) at \(c\) of depth
Let \(x\in P\) satisfy \(d(x,c)=h\). Choose a line \(l\) and \(k\in \mathbb {Z}\) such that \(d'(f(x),l(k))\leq R\). One of the two directions along \(l\) contains, arbitrarily far from \(l(k)\), a vertex \(z\) for which \(l(k)\) lies between \(f(c)\) and \(z\). Coarse surjectivity provides \(p\) with \(d'(f(p),z)\leq D\). Taking \(z\) sufficiently far away ensures that \(p\notin P\), since every point of \(P\) is within \(h\) of \(c\) and the upper quasi-isometry bound would otherwise keep \(f(p)\) too close to \(f(c)\).
The vertex \(l(k)\) lies between \(f(c)\) and \(f(p)\). Apply lemma 6.3 to a geodesic from \(c\) to \(p\) to obtain a vertex \(y\) on that geodesic with \(d'(f(y),l(k))\leq D\). Since \(x\in P\) and \(p\notin P\), the vertex \(c\) separates \(p\) from \(x\). As \(y\) lies between \(c\) and \(p\), it follows that \(c\) also lies between \(y\) and \(x\), and hence \(d(y,x)\geq d(c,x)=h\). On the other hand, \(d'(f(y),f(x))\leq D+R\), so the lower quasi-isometry bound gives
a contradiction.
A tree carrying three rays that pairwise meet only in their common initial vertex is not quasi-isometric to \(\mathrm{Ray}\).
Suppose that \(f\) is a \(D\)-quasi-isometry and set \(\rho =2D^2+1\). For distinct rays \(r_i\) and \(r_j\), uniqueness of paths in the source tree gives
Among the three vertices \(f(r_i(\rho ))\) of \(\mathrm{Ray}\), two lie on the same side of \(f(v)\). After exchanging them if necessary, \(f(r_i(\rho ))\) lies between \(f(v)\) and \(f(r_j(\rho ))\).
Apply lemma 6.3 to the geodesic from \(v\) to \(r_j(\rho )\). It gives a vertex \(y\) on this geodesic such that \(d(f(y),f(r_i(\rho )))\leq D\). The geodesic is the initial segment of \(r_j\), so \(y=r_j(t)\) for some \(t\leq \rho \). The two rays meet only at \(v\), and consequently
The lower quasi-isometry bound gives the opposite estimate
which is the required contradiction.