NEGATIVELY CURVED GRAPH AND PLANAR METRICS WITH APPLICATIONS TO TYPE

PHILIP L. BOWERS

A graph is of parabolic or hyperbolic type if the simple random walk on the vertices is, respectively, recurrent or transient. A plane triangulation graph is CP-parabolic or CP-hyperbolic if the maximal circle packing determined by the graph packs, respectively, the complex plane ℂ or the Poincaré disk 𝔻. We examine the implications that (Gromov) negative curvature carries for determining type, specifically in these settings. Our main result is encased in the following theorem.

Theorem. Every proper (Gromov) negatively curved metric space whose boundary contains a nontrivial continuum admits a (2, C)-quasi-isometric embedding of a uniform binary tree.

Corollaries of this theorem include

1. the simple random walk on every locally finite, negatively curved graph whose boundary contains a nontrivial continuum is transient;

2. the simple random walk on a locally finite, 1-ended negatively curved graph whose boundary contains more than one point is transient;

3. a negatively curved plane triangulation graph is CP-hyperbolic if and only if it has a circle boundary (equivalently, CP-parabolic if and only if it has a point boundary).

The classical “type problem” is that of determining whether a given noncompact, simply connected riemann surface is conformally equivalent to the plane ℂ or the disk 𝔻. The surface is said to be of parabolic type in the former case, and of hyperbolic type in the latter. Our concern is with two related discretizations of this classical problem, one via random walks on graphs, the other via planar circle packings. Connections between probabilistic characteristics and the type problem are deep and intimate, and have been known for a long time. For instance, a simply connected riemann surface is hyperbolic if and only if a Brownian traveler starting at any point has a positive escape probability. This generalizes to higher dimensional riemannian manifolds. A complete riemannian manifold is hyperbolic exactly when the Brownian motion generated by the Laplace-Beltrami operator is transient. Kanai discretized this in [26, 27] where he characterized hyperbolic riemannian manifolds of bounded geometry as, roughly, those that are quasi-isometric to certain graphs of hyperbolic type. Another discretization of type has occured more recently in the very geometric/combinatorial setting of circle packings, this a purely 2-dimensional phenomenon. Here, a triangulation of the plane determines a maximal circle packing of exactly one of the plane ℂ or the disk 𝔻, and there has been interest in finding conditions on the combinatorics of the triangulation that determine type; see, for instance, [18, 23, 28].

Date: March 16, 1998.

The author thanks the Department of Pure Mathematics and Mathematical Statistics at Cambridge University for their kind hospitality during his sabbatical visit in the first half of 1996, when this work began. The author also thanks an anonymous referee, especially for simplifying the proofs of Section 3.

It is of no surprise that negative curvature of a graph has implications for the type of the graph, but all work to date concerning these implications has assumed additional structure — either bounded degree or some sort of isoperimetric inequality. These, especially the latter, are very strong uniformity conditions that forbid the type of random asymptotic behavior that easily can occur in graphs and in circle packings, even in the context of negative curvature.

Our proof of the theorem occupies Section 1 and involves primarily the very fast divergence of geodesics in a negatively curved space, as well as the quasi-denseness of geodesic rays. The theorem itself in weaker forms is hinted at in Gromov’s work [21] and Bowditch’s exposition [8] of Gromov’s work. Actually, we prove a result stronger than the theorem, namely, that every metric space satisfying the hypotheses of the theorem admits, for any positive ε, a (1+ε, C(ε))-quasi-isometric embedding of a uniform binary tree, where C(ε) is small when measured in the length scale of the binary tree. The applications of the theorem to the determination of type are easy and appear in the subsequent sections. After recalling some standard facts about random walks in Section 2, we apply the theorem to confirm the first two corollaries listed above. These are compared with previous results of Ancona [4], and Kaimanovich and Woess [25], both of whom assume bounded degree and strong isoperimetric conditions in the context of simple ramdom walks. Section 3 develops some of the basic topology of negatively curved planar metrics. These metrics arise naturally from negatively curved plane triangulation graphs as quasi-isometric images, and we prove that their boundaries are either singletons or topological circles. The beautiful results of He and Schramm [23] determining the CP-type of plane triangulation graphs using vertex extremal length are reviewed in Section 4, after which the theorem, as well as results from the section preceding, are applied to the determination of CP-type. In particular, the third corollary listed above is proved. A final section, Section 5, concludes with a short discussion of further applications of the theorem that are due to Ken Stephenson and the author, proofs of which will appear in [9]. Since many readers whose background is in either random walks or circle packings may not be familiar with the recent developments on metric negative curvature, it seems fitting to include all the results that we will use from this theory in one section. Thus an appendix has been included that gives an overview of recent metric geometry with either references, or proofs when we could find no references, for all the results stated. As there is no uniformity of terminology in this rather young field, we take this opportunity to fix the terminology and notation that we use in our proofs, and we present some results in a nonstandard way that is particularly suited for our purposes in the paper proper.

1. Proof of the Theorem

Throughout this section, ρ denotes a proper, negatively curved geodesic metric on the set X with a fixed basepoint x_{0}, and Z denotes a nontrivial continuum in the Gromov boundary ∂X (see the Appendix for definitions). Also, all geodesic rays are assumed to be arclength parameterized. Since ρ is negatively curved, there exists a positive constant δ such that (X, ρ) has δ-inscribed triangles.

Lemma 1.1. Let α be a geodesic ray based at x_{0} that limits at a point of Z and let s be any positive parameter value. If there exists a geodesic ray β based at x_{0} that limits at a point of Z for which the ρ-distance between α(s) and β(s) is at least 4δ, then there exists a geodesic ray σ based at x_{0} that limits at a point of Z for which

2δ < ρ(α(s), σ(s)) < 4δ.

Proof. Assuming that the boundary ∂X is parameterized from the basepoint x_{0} as described in the Appendix, let

U = {σ(∞) ∈ ∂X: ρ(α(s), σ(s)) ≤ 2δ}

and

V = {σ(∞) ∈ ∂X: ρ(α(s), σ(s)) ≥ 4δ}.

Observe that U contains the point α(∞) ∈ Z and V contains the point β(∞) ∈ Z. From the definition of the topology on the boundary, as described in the Appendix, the sets U and V are closed in the boundary and, by Lemma A.4, they are disjoint. If there is no geodesic ray with the desired property, then the union of the two sets U and V covers Z, and it follows that U and V provide a separation of the connected set Z, a contradiction.

We apply this lemma recursively to define a collection of arclength parameterized geodesic rays σ_{b}, indexed by binary sequences b of finite length, that are based at x_{0} and limit at points of Z. First, choose such rays σ_{0} and σ_{1} based at x_{0} that limit at respective distinct points of Z. Since σ_{0}(∞) and σ_{1}(∞) are distinct boundary points, the ρ-distance between σ_{0}(t) and σ_{1}(t) is unbounded as t increases, and we may choose a parameter value t_{0} for which the ρ-distance between σ_{0}(t_{0}) and σ_{1}(t_{0}) is at least 2δ. Let Σ_{1} = {σ_{0}, σ_{1}}.

Fix a constant K ≥ 5 and, for the positive integer n, assume that we have constructed the set

Σ_{n} = {σ_{b}: |b| = n}

of geodesic rays based at x_{0} that limit at points of Z such that the ρ-distance between any two distinct points from the set

{σ_{b}(t_{0} + Kδ(n − 1)): |b| = n}

is at least 2δ. Here we are using |b| to denote the length of the binary sequence b. Lemma A.4 implies that the ρ-distance between any two points from the set

{σ_{b}(t_{0} + Kδn): |b| = n}

is at least (2K + 1)δ, which is greater than 4δ. For each σ_{b} in Σ_{n}, apply Lemma 1.1 with s of the lemma equal to t_{0} + Kδn to find a geodesic ray σ_{b∗} based at x_{0} that limits at a point of Z and for which

2δ < ρ(σ_{b}(t_{0} + Kδn), σ_{b∗}(t_{0} + Kδn)) < 4δ. (1.1)

For i = 0, 1, define σ_{bi} as σ_{b} if the last digit of b equals i; otherwise, define σ_{bi} as σ_{b∗}. This defines the set Σ_{n+1} = {σ_{b}: |b| = n + 1}, and our construction ensures, since (2K + 1)δ is at least 11δ, that the ρ-distance between any two points from the set

{σ_{b}(t_{0} + Kδn): |b| = n + 1}

is at least 2δ.

We now use the sets Σ_{n} to construct a mapping of a uniform binary tree 𝒯 into X. The tree 𝒯 is a nontrivial, rooted graph with intrinsic metric d (see Appendix) wherein each vertex other than the root vertex has degree three and each edge is isometric to a euclidean interval of some fixed length, which we take to be of length δ. The root itself, denoted as v_{∅} where ∅ stands for the empty binary sequence, has degree two. There are 2^{n} vertices in the sphere of radius nδ about the root vertex in 𝒯, and we assume that these have been labeled as v_{b}, where b ranges over the binary sequences of length n, and the children of vertex v_{b} are v_{b0} and v_{b1}. Define the mapping

λ: 𝒯 → X

on vertices by

λ(v_{b}) = σ_{b}(t_{0} + Kδ(|b| − 1)) (1.2)

if b ≠ ∅, with λ(v_{∅}) equal to the midpoint of a geodesic segment from λ(v_{0}) = σ_{0}(t_{0}) to λ(v_{1}) = σ_{1}(t_{0}), and extend to edges by mapping the edge from v_{b} to its child v_{b∗} convexly onto a geodesic segment from λ(v_{b}) to λ(v_{b∗}), using the segment that lies in σ_{b} whenever σ_{b} = σ_{b∗}.

Our first task is to calculate upper and lower bounds for the ρ-distance between the λ-images of any two vertices in 𝒯. Towards this end, first notice that the ρdistance between λ(v_{b}) and λ(v_{b∗}), where v_{b∗} is a child of v_{b}, is at least Kδ if b ≠ ∅; moreover, this distance is at most (K + 1)δ. This upper bound on the distance follows from the definition of λ on vertices, Equation (1.2), along with the fact that σ_{b0}(t) and σ_{b1}(t) are δ-close at parameter value t = t_{0} + Kδ(|b| − 1). This last fact follows from an examination of the internal points of a triangle with vertices x_{0}, λ(v_{b0}), and λ(v_{b1}), and the fact that K ≥ 5 along with (1.1). Let b0x and b1y be binary sequences that agree in the first |b| digits and observe that the upper bound of (K + 1)δ for the ρ-distances between the λ-images of a vertex and its children gives the upper bound

ρ(λ(v_{b0x}), λ(v_{b1y})) ≤ (K + 1)δ(|x| + |y| + 2) = (K + 1)d(v_{b0x}, v_{b1y}). (1.3)

A useful lower bound is a bit harder to come by. For this, let b and c be distinct binary sequences for which |b| = |c| and use Lemma A.4 and the fact that the ρ-distance between λ(v_{b}) and λ(v_{c}) is at least 2δ, while that between the λ-images of two sibling vertices is at most 4δ, to obtain the inequality

2Kδ + ρ(λ(v_{b}), λ(v_{c})) − 9δ ≤ ρ(λ(v_{b∗}), λ(v_{c∗})), (1.4)

where v_{b∗} and v_{c∗} are respective children of v_{b} and v_{c}. If |x| = |y| for the binary sequences b0x and b1y, starting with the fact that ρ(λ(v_{b0}), λ(v_{b1})) ≥ 2δ, successive applications of (1.4) imply that

((2K − 9)|x| + 2)δ ≤ ρ(λ(v_{b0x}), λ(v_{b1y})). (1.5)

For the general lower bound, assume that |x| ≥ |y|. Let z be the binary sequence of length |x| − |y|, all of whose digits are equal to the last digit of the binary sequence 1y. Then σ_{b1y} = σ_{b1yz} and (1.2) implies that

ρ(λ(v_{b1y}), λ(v_{b1yz})) = Kδ|z| = K(|x| − |y|)δ. (1.6)

The triangle inequality applied to the λ-images of the vertices v_{b0x}, v_{b1y}, v_{b1yz}, along with (1.5) and (1.6), gives the lower bound

((K − 9)|x| + K|y| + 2)δ ≤ ρ(λ(v_{b0x}), λ(v_{b1y})). (1.7)

After subtracting 9δ|y| from, and adding and subtracting 2(K − 9)δ to, the left hand side of (1.7), recalling also that the d-distance between the vertices v_{b0x} and v_{b1y} is (|x| + |y| + 2)δ, we obtain the lower bound

(K − 9)d(v_{b0x}, v_{b1y}) − 2(K − 10)δ ≤ ρ(λ(v_{b0x}), λ(v_{b1y})). (1.8)

Theorem 1.2. For each ε > 0, the space X admits a (1 + ε, C(ε))-quasi-isometric mapping of a uniform binary tree.

Proof. Let K ≥ 10 and scale the metric d by a factor of (K − 9) to obtain a metric d_{K} on 𝒯 in which each edge has length (K − 9)δ. Then for every pair of non-root vertices u and v of 𝒯, (1.3) and (1.8) imply that

d_{K}(u, v) − 2(K − 10)δ ≤ ρ(λ(u), λ(v)) ≤ \frac{K + 1}{K − 9}d_{K}(u, v).

It follows that the restriction of λ to the set V of non-root vertices of 𝒯 is a (\frac{K+1}{K−9}, 2(K − 10)δ)-quasi-isometry, when 𝒯 is given the scaled metric d_{K}. An application of Lemma A.2 with M = (K − 9)δ and N = (K + 1)δ implies that λ is a (μ, C)-quasi-isometry, where μ = \frac{K+1}{K−9} and C = 2(3K − 8)δ. Setting 1 + ε = μ and observing that ε monotonically decreases to zero as K = 9 + 10ε^{−1} monotonically increases yield the desired result.

Corollary 1.3. The (1 + ε, C(ε))-quasi-isometric mapping of the previous theorem extends continuously to a homeomorphism of the Cantor set boundary ∂𝒯 onto a Cantor set contained in the continuum Z.

Remark. Let 𝒯_{ε} denote the binary tree 𝒯 with the scaled metric d_{K}. Notice from the proof of Theorem 1.2 that the length of each edge of 𝒯_{ε} is L(ε) = 10δ/ε. It follows that

C(ε) = 60δ/ε + 38δ = 6L(ε) + 38δ. (1.9)

The following corollary implies the theorem in the Introduction. It and its companion corollary following say that every negatively curved space whose boundary contains a nontrivial continuum has embedded binary trees whose distortions from uniformity are small in the scale of the lengths of the edges of the embedded trees.

Corollary 1.4. For each ε > 0, the space X admits a (1+ε, C(ε))-quasi-isometric embedding of a uniform binary tree ℬ_{ε}, where C(ε) is O(εℓ(ε)) as ε ↓ 0 and ℓ(ε) denotes the length of each edge of ℬ_{ε}.

Proof. First we use the previous theorem and the remark to identify a (1+ε, C(ε))- quasi-isometric mapping with the desired properties, and then we adjust the mapping to an embedding. Fix ε > 0 so that 9 + 10ε^{−1} = K is an integer and scale the metric d_{K} of 𝒯_{ε} by a factor of (K − 9) to obtain the uniform binary tree ℬ_{ε} in which the length of each edge is

ℓ(ε) = (K − 9)^{2}δ = (K − 9)L(ε) = \frac{10L(ε)}{ε}. (1.10)

For each binary sequence b, let \overline{b} denote the binary sequence obtained from b by replacing each digit i of b by a string of (K − 9) i’s. Let f: ℬ_{ε} → 𝒯_{ε} be the isometric embedding defined on the vertices by f(v_{b}) = vb̄, and recall from the proof of Theorem 1.2 that λ: 𝒯_{ε} → X is a (1 + ε, C(ε))-quasi-isometric mapping, where C(ε) is given by (1.9). It follows that the composition λ ∘ f is a (1 + ε, C(ε))- quasi-isometric mapping. Notice that C(ε) increases without bound as ε ↓ 0, but (1.9) and (1.10) imply that

\frac{C(ε)}{εℓ(ε)} = \frac{3}{5} + \frac{19ε}{50},

so that C(ε) is O(εℓ(ε)) as ε ↓ 0.

We now adjust λ ∘ f to an embedding by redefining λ only near the vertices of the form vb̄. We save ourselves an unnecessary technical headache by assuming that ε is no more than two, so that (K − 9) is at least five. Let b ≠ ∅ be a binary sequence and, without loss of generality, assume that the last digit of b is zero. Then the parent of vb̄ in 𝒯_{ε} is of the form v_{a0}, for the appropriate binary sequence a, since the sequence \overline{b} ends in a string of (K − 9) zero’s. Recall that λ is defined on the edge vb̄v_{b̄1} as a convex map to a geodesic segment of ρ-length between Kδ and (K + 1)δ from λ(vb̄), which lies on the ray σb̄ = σ_{a0}, to λ(v_{b̄1}), which lies on the ray σ_{b̄1}. Let ς be the geodesic segment contained in the image λ(vb̄v_{b̄1}) that meets σb̄ at the single point x, and endpoint of ς, that lies between λ(v_{a0}) and λ(v_{b̄0}), and meets the subsegment of σ_{b̄1} between λ(v_{b̄1}) and λ(v_{b̄11}) at the single point y, the other endpoint of ς. Define λ′(vb̄) = x and λ′(v_{b̄1}) = y, and extend convexly to map the edge vb̄v_{b̄1} onto ς. A further convex adjustment on the edges v_{a0}vb̄, vb̄v_{b̄0}, and v_{b̄1}v_{b̄11} produces an embedding λ′ of the convex hull of the vertices v_{a0}, v_{b̄0}, and v_{b̄11} that agrees with λ at these three vertices, and that is (K + 1)δ-close to λ. Repeating this construction at every vertex of 𝒯_{ε} of the form vb̄, as well as performing a similar construction near v_{∅}, produces a mapping λ′: 𝒯_{ε} → X that is (K + 1)δ-close to λ and, as the reader may check, for which Λ = λ′ ∘ f is an embedding. An application of Lemma A.3 implies that Λ is a (1 + ε, C′(ε))-quasi-isometric embedding, where C′(ε) = C(ε) + 2(K + 1)δ. Using (1.9) and (1.10),

\frac{C′(ε)}{εℓ(ε)} = \frac{4}{5} + \frac{29ε}{50},

so that C′(ε) is O(εℓ(ε)) as ε ↓ 0.

The details of the constructions above imply the following corollary.

Corollary 1.5. For each ε > 0, the (1 + ε, C(ε))-quasi-isometric embedding Λ_{ε} of the uniform binary tree ℬ_{ε} guaranteed by the previous corollary may be chosen so that the ρ-length of the image of every edge e of ℬ_{ε} satisfies

m(ε) ≤ ℓ_{ρ}(Λ_{ε}(e)) ≤ M(ε), (1.11)

where both bounds m(ε) and M(ε) are asymptotic to ℓ(ε) = 100δ/ε^{2}, the length of each edge of ℬ_{ε}, as ε ↓ 0.

2. Simple Random Walks and Type

For a good exposition of important results about random walks on graphs that includes a section on the type problem, see the survey article [34]. All graphs considered in this section are connected and locally finite, but we do not assume that they have bounded degree nor that they satisfy any sort of isoperimetric inequality. The simple random walk (SRW) on the graph X = (V (X), E(X)) is the random walk for which the transition probability p(x, y) from vertex x to vertex y is given by

p(x, y) = \begin{cases}1/deg(x), & if xy ∈ E(X); \\ 0, & otherwise. \end{cases}

Here, of course, V (X) and E(X) denote, respectively, the vertex and edge sets of X. The SRW on X is recurrent if, with probability one, the random walk starting at some vertex x returns to x; otherwise, the SRW is transient. In the transient case, there is a positive probability for the event that a random walker will escape to infinity. The graph X is recurrent/transient whenever the SRW on X is recurrent/transient.

The word metric on the graph X is an intrinsic metric in which each edge has unit length, and the graph is said to be negatively curved or word hyperbolic if its word metric is negatively curved. We often use the adjective combinatorial to refer to word metric properties of a graph; for example, combinatorial length, distance, and diameter are always with reference to the word metric.

Let 𝒯 be a tree with word metric. A vertex of 𝒯 of degree at least three, as well as the root vertex if the tree is rooted, is called a branch vertex. Two branch vertices are consecutive if there is a simple edge path between them that traverses no other branch vertices. We say that 𝒯 is quasi-uniform if 𝒯 is nontrivial, there are no vertices of unit degree, and there is a finite upper bound on the combinatorial length of any simple path of degree-two vertices. Notice that every quasi-uniform tree has uncountably many ends and there is a finite upper bound on the combinatorial distance between any two consecutive branch vertices. Also, 𝒯 is binary if 𝒯 is rooted and the degree of each non-root vertex is at most three while that of the root vertex is at most two. The following two lemmas are well-known and imply, with Corollary 1.5, Items (1) and (2) of the Introduction.

Lemma 2.1. Every quasi-uniform binary tree is transient.

Proof. An argument as in [17, Chapter 6] implies that the electrical resistence to infinity is finite, which implies that the tree is transient.

Lemma 2.2. If the locally finite graph X contains a transient subgraph, then X itself is transient.

Proof. See, for example, [34, Section 2].

Remark. Note that these two lemmas together imply that every locally finite, quasi-uniform tree is transient since every such contains a quasi-uniform binary subtree.

Theorem 2.3. If X is a locally finite, negatively curved graph whose Gromov boundary contains a nontrivial continuum, then X is transient.

Proof. Since X is locally finite, its word metric is proper. By Corollary 1.5, there is a (2, C(1))-quasi-isometric embedding Λ_{1} of the uniform binary tree ℬ_{1} into X. Since Λ_{1} is an embedding into a graph and the degree of each non-root vertex of ℬ_{1} is three, the image of each such vertex under the embedding must be a vertex of X. It follows that X contains a binary subtree ℬ = Λ_{1}(ℬ_{1}) that is quasi-uniform. Apply the two lemmas above.

Corollary 2.4. If X is a locally finite, 1-ended, negatively curved graph whose Gromov boundary contains more than one point, then X is transient

We review some of the previous work on the implications that Gromov negative curvature holds for random walks on graphs. The terms from the general theory of random walks on graphs that we use in this paragraph are defined in, for instance, [34]. These previous results have been derived in more general contexts than that of simple random walks, but have assumed hypotheses that imply stronger geometric conditions on graphs than just mere negative curvature of the word metric. We focus on two results, both derived in the context of a random walk given by a stochastic transition matrix

P = (p(x, y))_{x,y∈V (X)}

that descibes the one-step transition probabilities. The first is a result of Ancona [4] who proves that if X is negatively curved and P is uniformly irreducible, has bounded range, and has spectral radius less than unity, then the Martin boundary ∂_{M}X coincides with the Gromov boundary ∂X, and the random walk converges to ∂X almost surely. The second is a result of Kaimanovich and Woess [25] who replace the bounded range hypothesis of Ancona with the weaker hypothesis that P satisfy a uniform first moment condition, and conclude that the random walk converges to ∂X almost surely. The uniform irreducibility condition implies that the graph X has bounded degree. In the context of a SRW, if a graph has bounded degree, then the spectral radius is less than unity if and only if the graph satisfies a strong isoperimetric inequality; [24] and [34, Theorem 3.3]. These results imply, when the random walk is simple, not only that X is transient, but the additional conclusion that the Martin boundary coincides with the Gromov boundary, to which the random walk converges almost surely. The price that is paid, though, for these stronger results are the very strong geometric limitations placed on the graph X that it both have bounded degree and satisfy a strong isoperimetric inequality, limitations absent from our results.

3. Negatively Curved Planar Metrics

Our attention now specializes to planar graphs, particularly those associated to circle packings of the euclidean and hyperbolic planes. As a preliminary to determining CP-type in the next section, we collect in this some basic topological results. The setting throughout is that of a complete, negatively curved geodesic metric ρ on the complex plane ℂ that is compatible with (i.e., induces the same topology as) the euclidean one.

Theorem 3.1. The Gromov boundary ∂_{ρ}ℂ is either a singleton or a topological circle.

The theorem is a consequence of the next two lemmas.

Lemma 3.2. The Gromov boundary ∂_{ρ}ℂ is a metric continuum.

Proof. For any positive number R, let \overline{U}_{ρ}(R) denote the closure of the unbounded complementary domain of the ρ-ball of radius R centered at the origin. For each positive integer n, let C_{n} be the union \overline{U}_{ρ}(n) ∪ ∂_{ρ}ℂ, a subspace of the compactification \overline{ℂ} = ℂ ∪ ∂_{ρ}ℂ of the plane ℂ. That each C_{n} is a metric continuum follows quickly from the fact that ℂ has one end, the definition of the topology on \overline{ℂ}, as well as the basic facts that \overline{ℂ} is compact and metrizable (see Appendix). As the boundary ∂_{ρ}ℂ is the decreasing intersection of the metric continua C_{n}, it is itself a metric continuum.

Lemma 3.3. Every pair of distinct points of ∂_{ρ}ℂ separates ∂_{ρ}ℂ.

Proof. Let a ≠ b be points of ∂_{ρ}ℂ and choose a bi-infinite geodesic γ such that γ(∞) = a and γ(−∞) = b. The trace |γ| is a closed planar set homeomorphic to a line, and hence separates the plane into exactly two components, say X^{∘} and Y^{∘}. Note that the respective restrictions of the metric ρ to the sets X = X^{∘} ∪ |γ| and Y = Y^{∘} ∪ |γ| are proper, geodesic, and negatively curved. It follows as in the proof of the preceding lemma, since X and Y each have one end, that the Gromov boundaries ∂X and ∂Y are metric continua. The inclusions of X and Y in ℂ induce embeddings of Gromov boundaries, so that ∂X and ∂Y are naturally (closed) subspaces of ∂_{ρ}ℂ. An easy exercise establishes that the intersection ∂X ∩ ∂Y is precisely the pair ∂γ = {a, b} and, as ∂X and ∂Y are each connected and contain the two points a and b, the sets U = ∂X − ∂γ and V = ∂Y − ∂γ are nonempty. It follows that the sets U and V form a separation of ∂_{ρ}ℂ − {a, b}.

Proof of Theorem 3.1. With Lemmas 3.2 and 3.3, an old characterization theorem of R.L. Moore [33, Theorem 28.14] applies to show that ∂_{ρ}ℂ, if not a singleton, is a topological circle.

We present next a useful property of the metric ρ when the Gromov boundary ∂_{ρ}ℂ is a singleton. We assume that ρ has δ-inscribed triangles for the fixed positive constant δ.

Theorem 3.4. If the Gromov boundary ∂_{ρ}ℂ is a singleton, then there is a constant L such that, for any compact subset K of ℂ, there is a simple closed curve of ρlength at most L that separates K from infinity.

Proof. Let γ be a geodesic ray based at the point γ(0) = z_{0}. For any point p not on γ, let α_{p} be a shortest geodesic segment connecting p to γ. Let β_{p} be a shortest path connecting p to γ from the side of γ “opposite to” the side from which α_{p} approaches γ. This is unambiguous as long as α_{p} meets γ at a point other than z_{0}, and when α_{p} happens to meet γ at z_{0}, β_{p} is chosen to equal α_{p}. The reader might notice that our description of β_{p}, even when α_{p} misses the basepoint z_{0}, allows for the possibility that β_{p} hits the point z_{0}. Always in this case, β_{p} must meet γ along an initial segment of γ. Let P be the set of points for which the length of the paths α_{p} and β_{p} coincide, in which case both are geodesic segments, each meeting γ in exactly one point. Continuity of the metric implies not only that P is not empty, but, moreover, that P is an unbounded set in the plane.

In the next paragraph, we verify that for points p of P far enough from the basepoint z_{0}, both companion segments α_{p} and β_{p} miss the basepoint z_{0}. For each such point, let α_{p} and β_{p} meet γ at the respective points a_{p} ≠ z_{0} and b_{p} ≠ z_{0}, and consider the triangle (or bigon if a_{p} and b_{p} coincide) pa_{p}b_{p} with sides |α_{p}|, |β_{p}|, and the subsegment of γ between a_{p} and b_{p}. Let x_{p} and y_{p} be points on the respective segments α_{p} and β_{p} of ρ-distance 2δ from the respective points a_{p} and b_{p}. By Lemma A.1, since α_{p} and β_{p} are shortest paths to γ from p, the ρ-distance from x_{p} to y_{p} is at most δ. Let C_{p} denote the piecewise geodesic path that starts at x_{p}, travels along α_{p} to a_{p}, continues along γ to b_{p}, then along β_{p} to y_{p}, and finally back to x_{p} along a geodesic segment. Note that the ρ-length of C_{p} is at most 2δ + 4δ + 2δ + δ = 9δ = L (look at the internal points of the isosceles triangle pa_{p}b_{p}). By the definition of α_{p}, the segment from x_{p} to y_{p} along C_{p} cannot touch γ, from which it follows that C_{p} meets γ only along the subsegment of γ between a_{p} and b_{p}, at which points C_{p} approaches γ from opposite sides. This implies that the curve C_{p} is essential in ℂ − {z_{0}}. Since the metric ball B_{ρ}(z_{0}, n) misses C_{p} when n < ρ(z_{0}, a_{p}) − 5δ, C_{p} separates B_{ρ}(z_{0}, n) from infinity. By choosing p with ρ(z_{0}, a_{p}) large enough, we may separate any given compact set from infinity by one of the paths C_{p}, from which the theorem follows.

Finally, if arbitrarily far from the basepoint z_{0} there are points of P at least one of whose companion shortest segments to γ meets γ at z_{0}, then a sequence p(i) of such points may be extracted for which either the sequence of segments α_{p(i)}, or the companion sequence β_{p(i)}, converges to a ray γ′ based at z_{0}. This limiting ray γ′ cannot be asymptotic (see Appendix) to the ray γ, for this would violate the fact that there is a shortest path from p(i) to γ, for arbitrarily large i, that travels all the way to the basepoint z_{0} to meet γ. It follows that the points [γ] and [γ′] of the boundary ∂_{ρ}ℂ are not the same, contradicting our assumption that the boundary is a singleton.

By choosing the points x_{p} and y_{p} in the proof above to be slightly more than δ units from the respective points a_{p} and b_{p}, rather than 2δ away, one may obtain the value 5δ for the constant L.

4. CP-type

Two discrete graphical versions of classical extremal length have appeared, the first in 1962 by Duffin [19], the edge extremal length, and the second more recently by Cannon [14], the vertex extremal length. Edge extremal length is useful for determining the type of a SRW on a locally finite graph [19]. Vertex extremal length is useful for constructing square tilings of rectangles with prescribed patterns of contact [15, 32]. In a remarkable paper [23], He and Schramm use vertex extremal length to give a complete combinatorial characterization of the CP-type of a plane triangulation graph. For bounded degree graphs, the two discrete versions of extremal length agree [23, Theorem 8.1], and one of the impressive accomplishments of [23] is the realization that vertex extremal length is a fine enough sieve with which to determine CP-type in the non-bounded degree setting, where edge extremal length fails. The results below about the CP-type of negatively curved plane triangulation graphs are verified by simple applications of the work of He and Schramm in [23], along with our results in Sections 1 and 3. We begin by recalling definitions and terminology.

For a graph 𝒢, V (𝒢) and E(𝒢) denote, respectively, the vertex and edge sets of 𝒢. A plane triangulation graph is the 1-skeleton of a triangulation of the plane, and a circle packing for the plane triangulation graph 𝒢 is a collection 𝒞 = {C_{v}: v ∈ V (𝒢)} of euclidean circles in the plane ℂ with pairwise disjoint interiors such that C_{v} is tangent to C_{w} whenever vw is an edge of 𝒢. By connecting the euclidean centers of tangent circles in the circle packing 𝒞 by line segments, we obtain a geometric realization of the abstract graph 𝒢 as the 1-skeleton of a geodesic triangulation of, necessarily, a simply-connected domain D(𝒞) in ℂ. This domain D(𝒞) is called the carrier of 𝒞, though this term in the literature often refers also to its geodesic triangulation described above. Whenever there is a circle packing for 𝒢 with carrier D, we say that 𝒢 packs the domain D. Notice that every plane triangulation graph is locally finite. The following is the basic existence-uniqueness result concerning infinite circle packings in the plane. In this form, existence is due to He and Schramm [22] and uniqueness to Schramm [31]. Previously, Beardon and Stephenson [5] had proved the result in the setting of bounded degree graphs, and subsequently, He and Schramm, in another impressive accomplishment of [23], have extended the existence result to include packings of more general simply-connected domains by sets of more general shapes than circles.

Circle Packing Theorem. Every plane triangulation graph packs exactly one of the plane ℂ or the unit disk 𝔻. A circle packing for a plane triangulation graph with carrier either ℂ or 𝔻 is unique up to Möbius transformations that fix the carrier.

Definition. The plane triangulation graph 𝒢 is CP-parabolic if it packs the plane ℂ and CP-hyperbolic if it packs the disk 𝔻. The Circle Packing Theorem implies that every plane triangulation graph is either CP-parabolic or CP-hyperbolic, but never both. A maximal circle packing for 𝒢 is one with carrier either ℂ or 𝔻.

Definition. The locally finite, connected graph 𝒢 is RW-parabolic if the SRW on 𝒢 is recurrent and RW-hyperbolic if it is transient.

For bounded degree plane triangulation graphs, these two notions of type coincide [23], but, though every CP-hyperbolic graph is RW-hyperbolic, there are plane triangulation graphs of unbounded degree that are CP-parabolic and, at the same time, RW-hyperbolic [23, Theorem 8.2]. Duffin’s notion of edge extremal length captures the RW-type of a graph while Cannon’s notion of vertex extremal length, as shown in [23], captures the CP-type. We refer the reader to Section 2 of [23] for the general definitions of combinatorial extremal length and are content with quoting the results from [23] that meet our purposes.

Definition. An infinite graph 𝒢 is VEL-parabolic if, for some (hence, any) vertex v, the vertex extremal length of the family Γ(v, ∞) of infinite, unbounded paths of vertices based at v is infinite; otherwise, 𝒢 is VEL-hyperbolic. Similarly, 𝒢 is EEL-parabolic if, for some (hence, any) vertex v, the edge extremal length of the family Γ(v, ∞) is infinite; otherwise, 𝒢 is EEL-hyperbolic.

We now quote [23, Theorem 7.2], He and Schramm’s combinatorial characterization of CP-type in terms of vertex extremal length.

Characterization Theorem. A plane triangulation graph is CP-parabolic if and only if it is VEL-parabolic; equivalently, CP-hyperbolic if and only if VEL-hyperbolic.

Recall that a graph is negatively curved if its word metric is so. The main purpose of this section is to verify the following theorem. Its proof consists of making several observations that allow us to apply Corollary 1.5, Theorem 3.1, Theorem 3.4, and the Characterization Theorem.

Theorem 4.1. A negatively curved plane triangulation graph is CP-parabolic if and only if its Gromov boundary is a singleton. A negatively curved plane triangulation graph is CP-hyperbolic if and only if its Gromov boundary is a topological circle.

Let K be a triangulation of the plane ℂ whose 1-skeleton is the graph 𝒢, and define |K|_{eq} to be the metric realization of K obtained by identifying each face of K with a euclidean unit equilateral triangle, and using the induced intrinsic metric. Our claim is that the resulting geodesic metric space |K|_{eq} is quasi-isometric with the graph 𝒢 with word metric. This follows quickly from the next observation, whose easy verification is left to the reader.

Lemma 4.2. Let (X, ρ) be a metric space and Y a quasi-dense subset of X. Suppose that there is a constant μ ≥ 1 such that each pair of points y_{0} and y_{1} of Y are joined by a ρ-rectifiable path in Y of ρ-length at most μρ(y_{0}, y_{1}). Then (Y, d) is quasi-isometric to (X, ρ), where d is the intrinsic metric determined by the restriction of ρ to Y; indeed, the inclusion of Y in X is a (μ, 0)-quasi-isometry with quasi-dense image.

Exercise. Obviously, the 1-skeleton 𝒢 of K is \frac{1}{\sqrt{3}}-dense in |K|_{eq}. Moreover, if x and y are points on two sides of a euclidean unit equilateral triangle △ that share the vertex v, then the path from x to y through v in ∂△ has length at most \frac{4}{\sqrt{3}} times the straight line distance in △ from x to y. Since the metric of |K|_{eq} is geodesic and equilateral on faces, Lemma 4.2 applies with μ = \frac{4}{\sqrt{3}} to show that 𝒢 with word metric is quasi-isometric to |K|_{eq}.

Lemma 4.3. The Gromov boundary ∂𝒢 of the negatively curved plane triangulation graph 𝒢 is either a singleton or a topological circle.

Proof. As 𝒢 is the 1-skeleton of the triangulation K, the previous exercise implies that |K|_{eq} is quasi-isometric to 𝒢 with word metric. As negative curvature is a quasi-isometry invariant, the metric of |K|_{eq} is negatively curved and, since 𝒢 is locally finite, the metric of |K|_{eq} is proper, hence complete. Since K triangulates ℂ, Theorem 3.1 implies that the Gromov boundary ∂|K|_{eq} is either a singleton or a topological circle. By the last paragraph of the Appendix and Lemma 4.2, the inclusion of 𝒢 into |K|_{eq} induces a homeomorphism of Gromov boundaries.

Proof of Theorem 4.1. The forward implications of the two statements of the theorem follow from Lemma 4.3, the Circle Packing Theorem, and the reverse implications, which are proved next.

According to the monotonicity property [23, 2.1], if 𝒢 contains a VEL-hyperbolic subgraph, then 𝒢 itself is VEL-hyperbolic. Assume that the Gromov boundary ∂𝒢 is a topological circle. By Corollary 1.5, as in the proof of Theorem 2.3, 𝒢 contains a quasi-uniform binary tree ℬ as a subgraph. It is a nice exercise in the calculation of combinatorial extremal length to show that every quasi-uniform binary tree is VEL-hyperbolic. Alternately, as ℬ has bounded degree, the VELtype of ℬ coincides with the EEL-type [23, Theorem 8.1], and as EEL-type coincides with RW-type for locally finite graphs [23, Theorem 2.6], Lemma 2.1 implies that ℬ is VEL-hyperbolic. Therefore, 𝒢 is VEL-hyperbolic and the Characterization Theorem applies to show that 𝒢 is CP-hyperbolic.

Assume now that the Gromov boundary ∂𝒢 is a singleton and that the word metric on 𝒢 has δ-inscribed triangles, for a fixed positive constant δ. Notice that since 𝒢 is not a tree, δ is at least unity. Fix a basepoint v_{0}, a vertex of 𝒢. By Theorem 3.4, there is a positive constant L such that every compact subset of |K|_{eq} is separated from infinity by a path of length at most L. By the exercise after Lemma 4.2, each such separating path may be replaced by a separating path in the 1-skeleton 𝒢 of |K|_{eq} of length at most \frac{4}{\sqrt{3}}L. This allows us to construct inductively a sequence of pairwise disjoint cycles c_{n}, each an edge path in the graph 𝒢 of combinatorial length at most \frac{4}{\sqrt{3}}L, and each separating v_{0} from infinity. It follows that every element of Γ(v_{0}, ∞) meets every |c_{n}|. Define a vertex label (or v-metric in the terminology of [23]) m: V (𝒢) → [0, ∞) by

m(v) = \begin{cases}1/n, & if v is a vertex of the cycle c_{n}; \\ 0, & otherwise, \end{cases}

which is well-defined since the cycles c_{n} are pairwise disjoint. Then the m-length of each path γ in Γ(v_{0}, ∞),

L_{m}(γ) = ∑_{i=1}^{∞} m(γ(i)),

is infinite while the m-area ∑_{v∈V (𝒢)} m(v)^{2} is finite. It follows that the vertex extremal length of the family Γ(v_{0}, ∞) is infinite (see [23, Section 2]) and, therefore, 𝒢 is VEL-parabolic. The Characterization Theorem applies to show that 𝒢 is CPparabolic.

The calculation of vertex extremal length in case the boundary is a singleton in the proof above works in more general settings, and is easily modified to prove the following corollary.

Corollary 4.4. Let v_{0} be a vertex in the graph 𝒢 and let {V_{n}} be a sequence of pairwise disjoint sets of vertices, each of which separates v_{0} from ∞. Suppose there exist positive constants C and ε such that, for each n,

Card(V_{n}) ≤ Cn^{1−ε}.

Then the graph 𝒢 is VEL-parabolic.

Finally, we mention a result of Northshield [29, 30], who constructed a boundary for bounded degree, planar graphs that satisfy a strong isoperimetric inequality and for which every circuit surrounds only finitely many vertices. He then proved that his boundary, say ∂_{N}𝒢 for the graph 𝒢, is either a topological circle or a singleton, and the SRW on 𝒢 converges almost surely to a ∂_{N}𝒢-valued random variable. If 𝒢 is in addition negatively curved, the Northshield boundary can be identified with the Poisson boundary, and if 𝒢 is also a plane triangulation graph, the Northshield boundary is the Martin boundary. See [34, Section 7.E] for definitions and further references.

5. Further Applications

We do not need that the embedded binary tree ℬ used in the proof of Theorem 4.1 be quasi-uniform to conclude that 𝒢 is CP-hyperbolic, only the weaker condition that it be transient. That ℬ is in fact quasi-uniform gives more information about the maximal circle packing for 𝒢 than merely that its carrier is the disk 𝔻. For example, the quasi-uniform condition can be used to get lower bounds on the hyperbolic radii of certain circles in the maximal packing, as well as various quasi-denseness results about circles that have uniformly large hyperbolic radii. We quote two illustrative results that will appear later [9] of Ken Stephenson and the author. In both, we assume that the unit disk 𝔻 carries its Poincaré metric making it a model for hyperbolic geometry. Recall that there is a finite upper bound on the combinatorial length of any simple path of degree-two vertices in a quasi-uniform binary tree ℬ. The smallest such upper bound is called the fundamental length for ℬ.

Theorem 5.1. If 𝒢 is a bounded degree plane triangulation graph with maximal packing 𝒞 that contains a quasi-uniform, binary subtree ℬ, then 𝒢 is CP-hyperbolic and there is a uniform positive lower bound λ on the hyperbolic radii of any circles C_{v} of 𝒞 that correspond to vertices v of the tree ℬ. The bound λ depends only on the maximum degree of 𝒢 and the fundamental length of ℬ.

Theorem 5.2. If 𝒢 is a CP-hyperbolic, negatively curved plane triangulation graph of bounded degree with maximal packing 𝒞, then there is a positive constant λ for which the union of the circles of 𝒞 of hyperbolic radii at least λ forms a quasi-dense subset of the disk in the Poincaré metric. The constant λ depends only on the maximum degree of 𝒢 and the thinness constant δ for the triangles of 𝒢.

Appendix . Negatively Curved Metrics — an Overview

References for recent metric geometry of negatively curved spaces are Gromov [21], Cannon [13], and Alonso et al. [3], and, for the related topic of nonpositively curved spaces, Bridson and Haefliger [10]. The older references Blumenthal [6], Blumenthal and Menger [7], Busemann [11, 12], Aleksandrov et al. [1], and Aleksandrov and Zalgaller [2] are invaluble both for comprehensive treatments of metric geometry and for expositions of the initial developments on metric curvature by a previous generation of mathematicians.

The metric ρ on the space X is geodesic if, for each pair of points x and y of X, there is a ρ-segment with endpoints x and y. This means thet there is an isometric map σ into X defined on the interval [0, ρ(x, y)] with σ(0) = x and σ(ρ(x, y)) = y. The metric ρ is proper if closed metric balls \overline{B}_{ρ}(x, R), for x in X and R > 0, are compact.

Exercise. The geodesic metric ρ is proper if and only if it is complete and the space X is locally compact.

The metric ρ is rectifiable if each pair of points of X are endpoints of a ρ-rectifiable path, a path γ of finite length

ℓ_{ρ}(γ) = sup_{𝒫}{∑ ρ(γ(t_{i}), γ(t_{i+1}))} ,

where the supremum is taken over all partitions 𝒫 of the domain interval of γ. The intrinsic metric on X determined by a rectifiable metric ρ is denoted as ρ_{∗} and defined by

ρ_{∗}(x, y) = inf{ℓ_{ρ}(γ): γ is a path containing x and y}.

The rectifiable metric ρ is intrinsic if ρ = ρ_{∗}. All geodesic metrics are intrinsic.

Exercise. If the metric ρ on the space X is intrinsic, then X is connected and locally connected.

Inscribed triangles and metric negative curvature. There are various equivalent ways of formulating an asymptotic version of negative curvature for geodesic metrics that captures the behavior that one expects from experience with simply connected, negatively curved riemannian manifolds. We prefer to work with the geometrically appealing notions of thin and inscribed triangles rather than Gromov’s original approach using hyperbolic inner products that, though at times offering cleaner proofs and constructions, nonetheless, is less intuitive to the uninitiated.

Let (X, ρ) be a geodesic metric space and δ a nonnegative constant. Though there may fail to be unique geodesics between points of X, it should cause no confusion to use the notation xy to denote some geodesic segment with endpoints x and y. With this notation, xyz denotes a set consisting of three geodesic segments xy, yz, and xz. The triangle xyz is δ-thin provided the ρ-distance from any point on any side of xyz to the union of the other two sides is at most δ. The internal points of xyz are the points μ(x) on segment yz, μ(y) on segment xz, and μ(z) on segment xy for which

ρ(x, μ(y)) = ρ(x, μ(z)), ρ(y, μ(x)) = ρ(y, μ(z)), and ρ(z, μ(x)) = ρ(z, μ(y)).

If xyz is a euclidean triangle in ℂ, the internal points are the points of tangency of the circle inscribed in xyz. The triangle xyz is δ-inscribed if the ρ-diameter of the set {μ(x), μ(y), μ(z)} of internal points is at most δ.

Remark. The reader should be cautious as the topic is young enough that terminology has not solidified. For example in [3], thin triangles are referred to as slim triangles, while [13] conforms to our usage, and a seemingly stronger notion of inscribed triangles than ours is referred to in [3] as thin triangles, while having δ-inscribed triangles is rendered as the insize is bounded by δ.

Definition. We say that the geodesic metric ρ on X has δ-thin (-inscribed) triangles if every geodesic triangle in X is δ-thin (-inscribed), and has thin (inscribed) triangles if it has δ-thin (-inscribed) triangles for some nonnegative constant δ. In either case, the constant δ is called a thinness constant for ρ or X.

In this paper, we primarily use the property of δ-inscribed triangles showcased in the following lemma. It is for this reason that we have introduced the lesserused term and atribute inscribed triangles rather than only the more common thin triangles.

Lemma A.1. If (X, ρ) has δ-inscribed triangles, then every geodesic triangle xyz is δ-uniform, meaning that if the points a on segment xμ(z) and b on segment xμ(y) satisfy ρ(x, a) = ρ(x, b), then the ρ-distance between a and b is at most δ, and similarly with x, y, and z permuted.

Proof. Since ρ has δ-inscribed triangles, it suffices to find points y′ on segment xy and z′ on segment xz such that the points a and b are two of the internal points of the triangle xy′z′. Let β, γ: [0, 1] → X be unit time parameterizations (i.e., proportional to arclength) of the respective geodesic segments xy and xz with β(0) = x = γ(0) and β(1) = y and γ(1) = z. Define s: [0, 1] → ℝ by

s(t) = \frac{1}{2}[ρ(x, β(t)) + ρ(x, γ(t)) − ρ(β(t), γ(t))],

so that the internal points of triangle xβ(t)γ(t) opposite β(t) and γ(t), respectively, are

μ(β(t)) = γ (\frac{s(t)}{ρ(x, z)}) and μ(γ(t)) = β (\frac{s(t)}{ρ(x, y)}) .

Since s is continuous with s(0) = 0 and s(1) = r = \frac{1}{2}(ρ(x, y) + ρ(x, z) − ρ(y, z)) = ρ(x, μ(y)) = ρ(x, μ(z)), s takes on every value between 0 and r. Let r_{0} = ρ(x, a) and observe that r_{0} is in the interval [0, r]. It follows that there is a number t_{0} in [0, 1] such that s(t_{0}) = r_{0}, and a and b are internal points opposite the respective vertices z′ = γ(t_{0}) and y′ = β(t_{0}) in the triangle xy′z′.

Exercise. Prove that every δ-thin triangle is 4δ-inscribed.

Definition. The previous lemma and exercise show that the geodesic metric ρ has thin triangles if and only if it has inscribed triangles. When ρ has thin or inscribed triangles, we say that ρ is asymptotically negatively curved or hyperbolic. We shall usually delete the descriptively correct adjective asymptotically and refer to a negatively curved metric.

Quasi-isometries. A not necessarily continuous function λ: T → X between the metric spaces (T, d) and (X, ρ) is a (μ, C)-quasi-isometry, where μ ≥ 1 and C ≥ 0 are constants, if for all points u and v of T,

\frac{1}{μ}d(u, v) − C ≤ ρ(λ(u), λ(v)) ≤ μd(u, v) + C.

A quasi-isometric mapping is a continuous quasi-isometry, and a quasiisometric embedding is one that is also a topological embedding. A subset V of T is M-dense if every point of T is M-close to some point of V, and is quasi-dense in T if it is M-dense for some M ≥ 0. (T, d) and (X, ρ) are quasiisometric if there is a quasi-isometry T → X whose image is quasi-dense in X. In this case, there is a quasi-isometry X → T whose image is quasi-dense in T. In fact, quasi-isometry is an equivalence relation on the class of metric spaces.

Lemma A.2. For positive constants M and N, if V is an M-dense subspace of T and λ: T → X is a function for which the restriction λ|V is a (μ, C)-quasi-isometry such that, for every v in V, the λ-image of the closed metric ball \overline{B}_{d}(v, M) is contained in the closed metric ball \overline{B}_{ρ}(λ(v), N), then λ is a (μ, C + 2μM + 2N)- quasi-isometry.

Proof. The proof is an exercise in the use of the triangle inequality.

Lemma A.3. Let λ, λ′: T → X be functions such that λ is a (μ, C)-quasi-isometry and λ′ is N-close to λ. Then λ′ is a (μ, C + 2N)-quasi-isometry.

Proof. The proof is an exercise in the use of the triangle inequality even easier than that of the previous lemma.

Exercise. Any geodesic metric quasi-isometric to a negatively curved metric is itself negatively curved.

Divergence of geodesic rays. Throughout the remainder of the appendix, (X, ρ) is a negatively curved geodesic metric space with, say, δ-inscribed triangles for some fixed positive δ, and x_{0} denotes a fixed basepoint in X. The next lemma presents the key divergence property of geodesic rays in a negatively curved metric space that is used several times in Section 1 to prove the theorem of the Introduction. Since we use it so often in this paper, and since we could find no proof of exactly the inequality presented in the lemma, we include a proof.

Lemma A.4. Let σ_{0} and σ_{1} be arclength parameterized geodesic rays (or segments) in X based at x_{0} and suppose that, for some parameter value t_{0}, the ρ-distance between σ_{0}(t_{0}) and σ_{1}(t_{0}) is at least 2δ. Then

ρ(σ_{0}(t), σ_{1}(t)) ≥ 2(t − t_{0}) + ρ(σ_{0}(t_{0}), σ_{1}(t_{0})) − δ,

for all t ≥ t_{0} (for which σ_{0}(t) and σ_{1}(t) are defined).

Proof. Let 2r denote the ρ-distance between σ_{0}(t_{0}) and σ_{1}(t_{0}). Since r ≤ t_{0},

\frac{δ}{2} ≤ t_{0} − r + \frac{δ}{2}.

For any τ in the half-open interval (t_{0} − r + \frac{δ}{2}, t_{0}], the triangle inequality implies that

2r ≤ 2(t_{0} − τ) + ρ(σ_{0}(τ), σ_{1}(τ)) < 2r − δ + ρ(σ_{0}(τ), σ_{1}(τ)),

implying that

δ < ρ(σ_{0}(τ), σ_{1}(τ)). (A.1)

Suppose there exists a parameter value t greater than or equal to t_{0} for which

ρ(σ_{0}(t), σ_{1}(t)) ≤ δ. (A.2)

Let t_{min} be the least such value of t. By continuity of the metric,

ρ(σ_{0}(t_{min}), σ_{1}(t_{min})) = δ,

and the triangle inequality implies, since the ρ-distance between σ_{0}(t_{0}) and σ_{1}(t_{0}) is at least 2δ, that

t_{0} ≤ t_{min} − \frac{δ}{2}. (A.3)

Since the points σ_{0}(t_{min} − \frac{δ}{2}) and σ_{1}(t_{min} − \frac{δ}{2}) are internal points of a triangle with vertices x_{0}, σ_{0}(t_{min}), and σ_{1}(t_{min}), the ρ-distance between them is at most δ. By (A.3), t_{min} is not the least parameter value greater than or equal to t_{0} that satisfies (A.2), a contradiction. This with the previous calculation shows that (A.1) holds for every τ larger than t_{0} − r + \frac{δ}{2}.

Now let t be any parameter value greater than t_{0} and set 2s equal to the ρdistance between σ_{0}(t) and σ_{1}(t). Then σ_{0}(t − s) and σ_{1}(t − s) are internal points of a triangle with vertices x_{0}, σ_{0}(t), and σ_{1}(t) and, hence, the ρ-distance between them is at most δ. From the previous paragraph it follows that

t − s ≤ t_{0} − r + \frac{δ}{2}.

Multiplication by 2 and rearrangement of this inequality yield the desired inequality.

Corollary A.5. Under the hypotheses of the previous lemma,

ρ(σ_{0}(s), σ_{1}(t)) ≥ (t − t_{0}) + (s − t_{0}) + ρ(σ_{0}(t_{0}), σ_{1}(t_{0})) − δ,

for all s, t ≥ t_{0} (for which σ_{0}(s) and σ_{1}(t) are defined).

Proof. Use the triangle inequality and the previous lemma.

The next theorem presents a characteristic property of geodesic rays in a negatively curved space, its proof being essentially that of [3, Theorem 2.19], except that the proof there assumes (without so stating) that the constant δ is greater than \frac{1}{2}.

Theorem A.6 (Exponential Divergence of Geodesics). Let σ_{0} and σ_{1} be arclength parameterized geodesic rays in X based at x_{0} and suppose that the ρ-distance between σ_{0}(t_{0}) and σ_{1}(t_{0}) is greater than δ, for some parameter value t_{0}. Then for each nonnegative integer n and each path γ from σ_{0}(t_{0} + nδ) to σ_{1}(t_{0} + nδ) in the complement of the open ball B_{ρ}(x_{0}, t_{0} + nδ), the ρ-length of γ satisfies

ℓ_{ρ}(γ) ≥ 2^{n−1}δ.

The Gromov boundary. There are two equivalent approaches to the Gromov boundary and its topology in the literature — in terms of Gromov’s hyperbolic inner product and equivalence classes of sequences that are convergent at infinity (see [21]) and, alternately, in terms of equivalence classes of fellow travelling geodesic rays and Cannon’s combinatorial half spaces (see [13]). The former has the advantage of often times providing very clean proofs of convergence results while the latter has the advantage of providing good, accurate geometric intuition. We present an approach that has the advantages of both Gromov’s and Cannon’s above and, at the same time, is very concise in its description and confirmation that it defines a topology. This approach uses Cannon’s preference in [13] for describing the boundary in terms of equivalence classes of fellow travelling geodesic rays, but describes the topology by prescribing precisely when a sequence of such classes converges. Any readers familiar with the two standard descriptions of the boundary will see immediately that our description defines the same topology as the former ones. We shall restrict our attention to the setting in which the metric, in addition to being negatively curved, is also proper, in which case the boundary provides a compactification \overline{X} = X ∪ ∂X.

A geodesic ray is an isometric embedding of the interval [0, ∞) into X, and two geodesic rays σ_{0} and σ_{1} are asymptotic, denoted as σ_{0} ∼ σ_{1}, if the Hausdorff distance between their images is finite, meaning that each is contained in the nneighborhood of the other, for some positive constant n. In this case, it is easy to see that in fact they (ϱ + 2n)-fellow travel, where ϱ is the ρ-distance between σ_{0}(0) and σ_{1}(0); this means that the ρ-distance between σ_{0}(t) and σ_{1}(t) is at most (ϱ+2n) for every parameter value t. We say that the ray σ is based at σ(0) and its trace is the image |σ| = σ([0, ∞)). In our context in which (X, ρ) has δ-inscribed triangles, Lemma A.4 implies that when two asymptotic rays σ_{0} and σ_{1} are both based at the common point x_{0}, they 2δ-fellow travel. We use the notation [σ] to denote the equivalence class of the ray σ under the equivalence relation of being asymptotic, and ∂X to denote the set of such equivalence classes. For each geodesic ray σ, extend its domain to the extended interval [0, ∞] by defining σ(∞) to be the point [σ] of the boundary ∂X. We then say that σ is a geodesic segment from σ(0) to σ(∞) = [σ].

For each point c in the boundary, there is a geodesic ray σ based at x_{0} such that c = [σ]. To see this, let τ be a ray for which c = [τ] and, for each positive integer n, let σ_{n} be a geodesic segment from x_{0} to τ(n). Use the fact that ρ is proper in conjunction with a diagonal argument to show that a subsequence of the segments σ_{n} converges to a geodesic ray σ. Use thin triangles to show that σ and τ are asymptotic. We use the phrase ∂X is parameterized from x_{0} to indicate a context in which all geodesic rays representing any point of the boundary are based at x_{0}. Notice that we may write

∂X = {σ(∞): σ is based at x_{0}}.

Let \overline{X} denote the union X ∪ ∂X, and define a sequence of points c_{n} in \overline{X} to converge to the point c of \overline{X} in the following way, depending on whether or not c is a boundary point. When c is in X, c_{n} → c means that there exists a positive integer N such that the sequence {c_{n}: n ≥ N} is contained in X and converges to c with respect to the metric ρ. When c is a boundary point, c_{n} → c means that for every R ≥ 0, there exists a positive integer N such that

(i) the ρ-ball B_{ρ}(x_{0}, R) does not contain c_{n} whenever n ≥ N, and (ii) for each n ≥ N, there exist segments σ_{n} from x_{0} to c_{n} and σ from x_{0} to c

that 6δ-fellow travel on the interval [0, R]. Easily, limits of convergent sequences are unique and subsequences of a convergent sequence converge to the limit of the sequence.

Exercise. Use Lemma A.4 to show that the convergent sequences and their limits remain unchanged if item (ii) is replaced by the statement: for each n ≥ N, all segments σ_{n} from x_{0} to c_{n} and σ from x_{0} to c 6δ-fellow travel on the interval [0, R].

Exercise. Convergence of points of \overline{X} to a boundary point is defined with reference to a basepoint x_{0}. Use thin triangles and a diagonal argument to verify that the definition does not depend on the basepoint.

Define a subset of \overline{X} to be closed if it contains all its limit points, where the point c of \overline{X} is a limit point of a set C if there is a sequence of points c_{n} in C that converges to c. It is an easy exercise to verify that this defines a topology on \overline{X}; that the union of two closed sets is closed uses the observation that limits are preserved by subsequences. Throughout the paper proper, \overline{X} carries this topology and ∂X carries the subspace topology it inherits from \overline{X}. Obviously, the subspace topology X inherits from \overline{X} is exactly the ρ-metric topology, and it is easy to see that X is open in \overline{X}. Moreover, the diagonal argument alluded to above for constructing rays from sequences of segments using the properness of the metric shows quickly that \overline{X} is sequentially compact. That \overline{X} is metrizable is proved in [16, 20] and, coupled with the sequential compactness, shows that \overline{X} is compact as well as its closed subspace ∂X. Thus, \overline{X} is a compactification of X and, for each geodesic ray σ in X, the extended ray gives an embedding of the extended interval [0, ∞] into \overline{X}, where, of course, [0, ∞] has the usual topology making it an arc.

One of the most important properties of the Gromov boundary is that quasiisometries between proper, negatively curved metric spaces extend continuously to boundaries. This in turn follows from the fact that quasi-geodesic rays, i.e., quasi-isometries of the half-line [0, ∞) into X, fellow travel actual geodesic rays. This may be proved with the aid of [3, Proposition 3.3], and a consequence is that quasi-isometric, proper, negatively curved metric spaces have homeomorphic boundaries.

References

[1] A.D. Aleksandrov, V.N. Berestovskii, and I.G. Nikolaev, Generalized Riemannian spaces, Russian Math. Surveys 41 (1986), 1–54.

[2] A.D. Aleksandrov and V.A. Zalgaller, Intrinsic Geometry of Surfaces, Transl. of Math. Monographs 15, Amer. Math. Soc., Providence, RI, 1967.

[3] J. Alonso, T. Brady, D. Cooper, T. Delzant, M. Lustig, M. Mihalik, M. Shapiro, H. Short, and A. N. Other, Notes on word hyperbolic groups, in Group Theory from a Geometrical Viewpoint (E. Ghys, A. Haefliger, A. Verjovsky, eds., World Scientific, 1991), 3–63.

[4] A. Ancona, Positive harmonic functions and hyperbolicity, in Potential Theory, Surveys and Problems, Lecture Notes in Math. 1344 (J Král et al., eds., Springer-Verlag, 1988), 1–23.

[5] A.F. Beardon and K. Stephenson, The uniformization theorem for circle packings, Indiana U. Math. J. 39 (1990), 1383–1425.

[6] L.M. Blumenthal, Theory and Application of Distance Geometry, 2nd Ed., Chelsea Pub., 1970; reprint of 1953 edition.

[7] and K. Menger, Studies in Geometry, W.H. Freeman and Co., 1970.

[8] B.H. Bowditch, Notes on Gromov’s hyperbolicity criterion for path-metric spaces, in Group Theory from a Geometrical Viewpoint (E. Ghys, A. Haefliger, A. Verjovsky, eds., World Scientific, 1991), 64–167.

[9] P.L. Bowers and K. Stephenson, Combinatorial half-planes, discrete harmonic measure, and type, in preparation.

[10] M. Bridson and A. Haefliger, book in preparation.

[11] H. Busemann, Spaces with nonpositive curvature, Acta Math. 48 (1948), 259–310.

[12] , The Geometry of Geodesics, Academic Press, 1955.

[13] J.W. Cannon, The theory of negatively curved spaces and groups, in Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces (T. Bedford, M. Keane, C. Series, eds., Oxford Univ. Press, 1991), 315–369.

[14] , The combinatorial Riemann mapping theorem, Acta Math. 173 (1994), 155–234.

[15] , W.J. Floyd, and W.R. Parry, Squaring rectangles: the finite Riemann mapping theorem, Contemporary Math. 169 (1994), 133–212.

[16] M. Coornaert, T. Delzant, and A. Papadopoulus, Notes sur les groupes hyperboliques de Gromov, Lecture Notes in Math. 1441, Springer-Verlag, 1990.

[17] P.G. Doyle and J.L. Snell, Random Walks and Electric Networks, Carus Math. Monographs 22, Math. Assoc. Amer., Washington, DC, 1984.

[18] T. Dubejko, Recurrent random walks, Liouville’s Theorem, and circle packings, Math. Proc. Camb. Phil. Soc., to appear.

[19] R.J. Duffin, The extremal length of a network, J. Math. Ana. Appl. 5 (1962), 200–215.

[20] E. Ghys and P. de la Harpe (editors), Sur les groupes hyperboliques d’après Mikhael Gromov, Progress in Math. 83, Birkhäuser. 1990.

[21] M. Gromov, Hyperbolic groups, in Essays in Group Theory (S.M. Gersten, ed., Springer-Verlag, 1987), 75–263.

[22] Z-X. He and O. Schramm, Fixed points, Koebe uniformization and circle packings, Ann. Math. 137 (1993), 369–406.

[23] and , Hyperbolic and parabolic packings, Discrete and Comp. Geo. 14 (1995), 123–149.

[24] V.A. Kaimanovich, Dirichlet norms, capacities, and generalized isoperimetric inequalities for Markov operators, Potential Anal. 1 (1992), 61–82.

[25] and W. Woess, The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality, Prob. Theory and Related Fields 91 (1992), 445–466.

[26] M. Kanai, Rough isometries and combinatorial approximations of geometries of non-compact Riemannian manifolds, J. Math. Soc. Japan 37 (1985), 391–419.

[27] , Rough isometries and the parabolicity of Riemannian manifolds, J. Math. Soc. Japan 38, (1986), 227–238.

[28] G.J. McCaughan, Some results on circle packings, PhD Thesis, University of Cambridge, 1996.

[29] S. Northshield, Geodesics and bounded harmonic functions on infinite planar graphs, Proc. Amer. Math. Soc. 113 (1991), 229–233.

[30] , Circle boundaries of planar graphs, Potential Anal. 2 (1993), 299–314.

[31] O. Schramm, Rigidity of infinite circle packings, J. Amer. Math. Soc. 4 (1991), 127–149.

[32] , Square tilings with prescribed combinatorics, Israel J. Math. 84 (1993), 97–118.

[33] S. Willard, General Topology, Addison-Wesley, Reading, Mass., 1970.

[34] W. Woess, Random walks on infinite graphs and groups — a survey of selected topics, Bull. London Math. Soc. 26 (1994), 1–60.

Department of Mathematics, The Florida State University, Tallahassee, FL 32306-3027

   E-mail address: bowers@@math.fsu.edu