Tight spans and Gromov hyperbolicity

The definition of a metric space guarantees that if we pick three points {A,B,C} from it, we can draw a triangle in the Euclidean plane, with vertices labeled {A,B,C}, so that the side lengths are equal to the corresponding distances {|AB|, |AC|, |BC|}. In other words, we can represent any triple of points as vertices of a triangle.

Triangle representation

There is another, perhaps less obvious representation: as vertices of a tripod. Specifically, we can draw a graph of the form shown below and assign length to each edge so that {|AB|} is equal to the length of the shortest path from {A} to {B}, etc.

Tripod representation

Indeed, we have the system of linear equations

{\displaystyle \begin{cases}   a+b & = |AB| \\    a+c & = |AC| \\    b+c & = |BC| \\    \end{cases}}

with a unique solution

\displaystyle   \begin{cases} a &= \frac{1}{2}(|AB|+|AC|-|BC|) \\   b &= \frac{1}{2}(|AB|+|BC|-|AC|) \\    c &= \frac{1}{2}(|AC|+|BC|-|AB|)    \end{cases}

The numbers {a,b,c} are clearly nonnegative; if a number is zero, the corresponding edge can be contracted to a point. Simple as they are, these formulas have a name: {a} is called the Gromov product of {B} and {C} with respect to {A}, and is denoted {(B|C)_A}.

The more geometric way to arrive at tripod representation is to inscribe a circle in the triangle shown above, and note how the points of tangency divide the sides of the triangle:

Gromov products from inscribed circle

Next question: can we represent four points {A,B,C,D} in a similar way? The first approach fails: in general there is no Euclidean quadrilateral in which the sides and diagonals represent the distances between these four points. For example, if {|AB|=|BC|=|CD|=|DA|=1} and {|AC|=|BD|=2}, then any Euclidean representation must place both {B} and {D} in the midpoint between {A} and {C}, which contradicts {|BD|} being nonzero. Let’s try the metric graph approach.

By analogy with the tripod, we might hope at first for something like

Metric tree

but this does not work in general. Indeed, four points determine six distances, and the graph has only five degrees of freedom. We can add one more degree of freedom by thickening the connecting edge to a rectangle:

Generic tight span of a 4-point metric space

Does this work? Can we really find the required nonnegative numbers {a,b,c,d,e,f}? Yes! Writing and solving a system of six linear equations is tedious but can be done. A better way is to recognize that we have four tripods here, such as the tripod with vertices {A,B,C} and the edge lengths {a+e}, {b}, {c+f}. This immediately tells us that {b=(A|C)_B}. Similarly, {a=(B|C)_A}, {c=(B|D)_C} and {d=(A|C)_D}. The remaining lengths {e} and {f} can now be found directly. But in fact, we can find {e,f} independently of the other four lengths by considering the perfect matchings between the points {A,B,C,D}. Namely,

\displaystyle    \begin{cases}   |AB|+|CD| &= (a+b+c+d) + 2e \\   |AD|+|BC| &= (a+b+c+d) + 2f \\   |AC|+|BD| &= (a+b+c+d) + 2e+2f    \end{cases}

From here we get nonnegative {e} and {f} if and only if {\{AC,BD\}} is the longest matching of vertices (or one of the longest). In other words, we must consider the lengths of matchings before marking {A,B,C,D} on the graph. But once they are marked correctly, the rest is now clear: the numbers {2e} and {2f} are the amounts by which the longest matching exceeds the other two. In particular, the rectangle collapses into an edge precisely when the two longest matchings have the same length.

What we have here are examples of tight spans of metric spaces: the tripod is the tight span of 3-point space {\{A,B,C\}}, and the six-edge graph is the 1-skeleton of the tight span of {\{A,B,C,D\}}. (The rectangle should have been filled in to form a 2-cell; in general the tight span of n points is a polyhedral complex of dimension up to {\lfloor n/2\rfloor}.)

By definition, a metric space is Gromov hyperbolic if there exists a constant {\delta\ge 0} such that the tight span of any 4-point subset satisfies {\min(e,f)\le \delta}; that is, the rectangle in the middle is not too fat. Informally, this means the space is (contained in) a uniformly thickened metric tree. In terms of distances, the definition says that the lengths of the two longest matchings of {A,B,C,D} differ by at most {2\delta}. Out of several equivalent definitions of Gromov hyperbolicity, this is the most elementary one; it does not require the consideration of geodesics.

However, the real power of Gromov hyperbolicity transpires in the setting of geodesic spaces, where any two points are connected by an isometric image
of a line segment. To begin with, in geodesic spaces it suffices to consider the case when {D} lies on the geodesic from {A} to {C} (otherwise we replace {D}
with a nearby point on the geodesic). The hyperbolicity condition now says that in the geodesic triangle {ABC} each point on the side {AC} is within distance {\delta} of one of two other sides. Informally, all geodesic triangles in a Gromov hyperbolic space are uniformly thin.

This is indeed the case in the hyperbolic plane {\mathbb H^2}. Indeed, a direct computation shows that the area of any geodesic triangle in {\mathbb H^2} is less than {\pi} (it is {\pi} minus the sum of the angles). On the other hand, the area of a hyperbolic disk of radius {r} grows indefinitely as {r\rightarrow\infty}, since the total area of {\mathbb H^2} is infinite. It follows that in {\mathbb H^2} there is a uniform upper bound on the radius of a circle that can be inscribed into a triangle; the Gromov hyperbolicity of {\mathbb H^2} follows at once.

Even more immediately, {\mathbb R} is Gromov hyperbolic, with {\delta=0}. But {\mathbb R^2} is not, as it contains arbitrarily fat triangles (also, the perfect matchings of the points {\{(\pm n, \pm n)\}} have lengths {4\sqrt{2}n, 4n, 4n}, contradicting the four-point condition). Similarly, the graph of {y=|x|} with metric induced by restriction contains four-point configurations \{(\pm n,n),(\pm 2n,2n)\} and therefore is not Gromov hyperbolic. Since this graph is bi-Lipschitz equivalent to a line, we see that in general metric spaces Gromov hyperbolicity is not a bi-Lipschitz invariant. How could we expect it to be? bi-Lipschitz maps introduce multiplicative distortion of distances {L^{-1}|AB|\le |f(A)f(B)|\le L|AB|}, while Gromov hyperbolicity requires an additive bound.

Yet, if two geodesic metric spaces are bi-Lipschitz equivalent, then either both are Gromov hyperbolic, or neither. One can even replace bi-Lipschitz equivalence with a coarser notion of quasi-isometry, which requires {L^{-1}|AB|-M\le |f(A)f(B)|\le L|AB|+M} (and {f} need not be surjective; it should only cover some {\epsilon}-net in the codomain). The quasi-isometric invariance is what makes it possible to discuss hyperbolicity of finitely generated groups… but that topic will have to wait for another day.

2 thoughts on “Tight spans and Gromov hyperbolicity”

    1. I knew… tight span is another name for injective envelope of a metric space. I probably did not use the former term when I talked about category Met of metric spaces with 1-Lipschitz maps as morphisms.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s