BUSEMANN POINTS OF INFINITE GRAPHS

CORRAN WEBSTER AND ADAM WINCHESTER

Abstract. We provide a geometric condition which determines whether or not every point on the metric boundary of a graph with the standard path metric is a Busemann point, that is it is the limit point of a geodesic ray. We apply this and a related condition to investigate the structure of the metric boundary of Cayley graphs. We show that groups such as the braid group and the discrete Heisenberg group have boundary points of the Cayley graph which are not Busemann points when equipped with their usual generators.

The metric compactification of a metric space was introduced by Gromov [6], but was little studied. Recently, this compactification has proven of use in the study of certain metrics on state spaces of C*-algebras [10].

Let G be a countable discrete group, and ℂ_{c}(G) the convolution algebra of functions with finite support. If π_{l} is the usual *-representation of ℂ_{c}(G) on ℓ^{2}(G) coming from the left-regular representation, the reduced group C*-algebra C_{r}^{∗}(G) is the closure of π_{l}(ℂ_{c}(G)) in B(ℓ^{2}(G)). Given a length function ℓ on the group, Connes [4] considers as a “Dirac” operator the unbounded operator M_{ℓ} on ℓ^{2}(G) given by multiplication by ℓ. The commutators [M_{ℓ}, π_{l}(f)] are bounded for f ∈ ℂ_{c}(G), and thus define a seminorm L_{ℓ}(f) = ∥[M_{ℓ}, π_{l}(f)]∥ on this dense *-subalgebra of C_{r}^{∗}(G). This in turn defines a dual metric

ρ_{L_{ℓ}}(φ, ψ) = sup{|φ(f) − ψ(f)| : f ∈ ℂ_{c}(G), L_{ℓ}(f) ≤ 1}

on the state space S(C_{r}^{∗}(G)) of C_{r}^{∗}(G).

Rieffel [10] asks whether these seminorms are in fact Lip-norms, as defined in his earlier papers [8, 9]. A seminorm such as L_{ℓ} is a Lip-norm if the topology given by the dual metric ρ_{L_{ℓ}} on the state space coincides with the weak-* topology. His principal examples have ℓ as a word-length on ℤ^{d} given by a set of generators, or coming from embedding ℤ^{d} in ℝ^{d} and obtaining a length function from a norm, and Rieffel shows that in these cases the seminorms are in fact Lip-norms. His method relies on the fact that the group’s action on the boundary of the metric compactification is amenable (as studied by Anantharaman-Delaroche [2, 3]), as well as finiteness conditions on the orbits of the action on the boundary.

There are a number of obstacles to this approach, however, not least of which is understanding the boundary of the metric compactification in concrete terms. The easiest definition of the metric compactification is as the primitive ideal space of a certain subalgebra of the C*-algebra of continuous, bounded functions on G via Gelfand’s theorem, but Rieffel shows that one can find the points on the boundary as limits of weakly-geodesic rays. In some cases, such as for finitely generated free groups, all the boundary points occur as the limits of rays satisfying a stronger condition. Rieffel calls such points Busemann points, and they play a significant role in his discussion of the action of ℤ^{d} on the metric boundary. Rieffel raises the question of when all points on the boundary of the metric compactification are Busemann points.

Date: 28th July, 2003.

1991 Mathematics Subject Classification. Primary 20F65; Secondary 46L87, 53C23.

Key words and phrases. Busemann point, Cayley graph, group C*-algebra, quantum metric space.

In this paper, we look into this question in the setting of path metrics on infinite graphs, with a particular interest in Cayley graphs. By considering conditions under which minimal paths between triples of vertices eventually meet, we are able to give a geometric condition which determines whether or not all metric boundary points are Busemann points. More precisely, every point on the metric boundary is a Busemann point if and only if given any pair of vertices, there are minimal paths from each to any distant third vertex which eventually share a tail.

We then turn to look specifically at Cayley graphs of finitely generated groups. We provide an example which shows that even for finitely presented groups, there are Cayley graphs which have boundary points which are not Busemann points. We give a second if and only if condition for a Cayley graph to have boundary points which are not Busemann points. This condition is easier to check than the general condition, and we apply it to a number of examples. We show that every metric boundary point is a Busemann point for finitely generated groups G ≅ F_{k}/N where N is also finitely generated. Finally, we use the conditions to show that the Cayley graphs of groups such as the braid groups and the discrete Heisenberg groups, when given standard sets of generators, have boundary points which are not Busemann points.

This paper came from an undergraduate research project between the authors. The authors would like to thank Michelle Schultz for organizing the undergraduate research seminar at UNLV, and Marc Rieffel for his suggestion that this area would be a fruitful topic for undergraduate research and for his helpful comments on preliminary versions of this paper.

1. The Metric Compactification and Busemann Points

Following Rieffel [10], let (X, d) be a complete, locally compact metric space. Let C_{b}(X) be the commutative, unital C*-algebra of bounded, continuous functions on X with the uniform norm ∥ · ∥_{∞}, and C_{∞}(X) the closed subalgebra of functions which vanish at infinity. We define functions φ_{y,z} : X → ℝ by

φ_{y,z}(x) = d(x, y) − d(x, z).

It is immediate from the triangle equality that

∥φ_{y,z}∥_{∞} ≤ d(y, z),

and so φ_{y,z} ∈ C_{b}(X).

We let G(X, d) be the closed subalgebra generated by C_{∞}(X), the constant functions, and the functions {φ_{y,z}|y, z ∈ X}. Then G(X, d) is a commutative, unital C*-algebra, so Gelfand’s theorem tells us that G(X, d) ≅ C_{b}(\overline{X}_{d}), where \overline{X}_{d} is the maximum ideal space (or equivalently, the set of pure states) of G(X, d). The topological space \overline{X}_{d} is compact and contains X as a dense, open subset in a natural way, so we call \overline{X}_{d} the metric compactification of (X, d). The set \overline{X}_{d} \ X can be naturally thought of as the boundary at infinity of the compactification, so we will call the set ∂_{d}X = \overline{X}_{d} \ X the metric boundary of X.

Rieffel showed that if we fix some base point z_{0}, and define φ_{y} = φ_{z_{0},y}, then G(X, d) is generated by C_{∞}(X), the constant functions, and the functions {φ_{y}|y ∈ X}, because φ_{y,z} = φ_{z} − φ_{y}. Note that this does not depend on the choice of z_{0}.

A more concrete definition of this boundary is of interest. To that end, the following concepts are introduced:

Definition 1.1. Let (X, d) be a metric space, and T an unbounded subset of ℝ^{+} containing 0, and let γ : T → X. We say that

(1) γ is a geodesic ray if

d(γ(s), γ(t)) = |s − t|

for all s, t ∈ T.

(2) γ is an almost-geodesic ray if for every ε > 0 there is an integer N such

that

|d(γ(t), γ(s)) + d(γ(s), γ(0)) − t| < ε

for all t, s ∈ T with t ≥ s ≥ N.

(3) γ is a weakly-geodesic ray if for every y ∈ X and every ε > 0 there is an integer N such that

|d(γ(t), γ(0)) − t| < ε

and

|d(γ(t), y) − d(γ(s), y) − (t − s)| < ε

for all t, s ∈ T with t, s ≥ N.

It is immediate that every geodesic ray is an almost-geodesic ray. Rieffel showed that every almost-geodesic ray is a weakly-geodesic ray. The significance of weaklygeodesic rays is that their limits are the points of the metric compactification in most cases. Recall that a metric is proper if every closed ball of finite radius is compact.

Theorem 1.1 (Rieffel). Let (X, d) be a complete, locally compact metric space, and let γ : T → X be a weakly geodesic ray in X. Then

lim_{t→∞} f(γ(t))

exists for every f ∈ G(X, d), and defines an element of ∂_{d}X. Conversely, if d is proper and if (X, d) has a countable base, we have every point of ∂_{d}X is determined as above by a weakly-geodesic ray.

We will not reproduce the entire proof of the theorem, but the construction involved in the last part will be of use to us later, so we will reproduce that here. The proof requires one additional result from Rieffel’s paper:

Proposition 1.2 (Rieffel). Let (X, d) be a complete locally compact metric space. If the topology of X has a countable base, then so do the topologies of \overline{X}_{d} and ∂_{d}X.

With this in hand we can prove the last part of the theorem:

Proof (Theorem 1.1). Let ω ∈ ∂_{d}X. Proposition 1.2 tells us that \overline{X}_{d} has a countable base, so we can find a sequence w_{n} ∈ X which converges to ω in \overline{X}_{d}. Since ω ∉ X, and d is proper, w_{n} is unbounded. So we can find a subsequence w_{n_{k}} (with w_{n_{0}} = w_{0}) so that if k > l, then d(w_{n_{k}}, w_{0}) > d(w_{n_{l}}, w_{0}). Let T = {d(w_{n_{k}}, w_{0}) : k = 0, 1, …}, and define γ : T → X by letting γ(t) = w_{n_{k}} where t = d(w_{n_{k}}, w_{0}). Clearly

lim_{t→∞} γ(t) = ω,

so we need only show that γ is weakly geodesic.

By construction, d(γ(t), γ(0)) = t, so γ satisfies the first condition of Definition 1.1.3 for all ε > 0. Use γ(0) as the base point for functions φ_{y} for y ∈ X. Given any one of these functions we know that

lim_{t→∞} φ_{y}(γ(t)) = φ_{y}(ω),

and so given any ε > 0, there is some N such that for all s, t ∈ T with s, t ≥ N then |φ_{y}(γ(s)) − φ_{y}(γ(t))| < ε. But then

|d(γ(t), y) − d(γ(s), y) − (t − s)| = |d(γ(t), y) − d(γ(s), y)
− d(γ(t), γ(0)) + d(γ(s), γ(0)))|
= |φ_{y}(γ(t)) − φ_{y}(γ(s))| < ε,

so the second condition for weakly-geodesic rays is satisfied. □

Note that this theorem and the above construction mean that given any weaklygeodesic ray we can find a weakly-geodesic ray which has the same limit in the metric boundary, but for which d(γ(t), γ(0)) = t, and the ray comes from a sequence of points.

Rieffel defines any point ∂_{d}X which is the limit of an almost-geodesic ray to be a Busemann point, and poses the following question:

Question 1. Given a metric space (X, d), is every point of ∂_{d}X a Busemann point?

Rieffel’s interest in the metric compactification came from looking at metrics on infinite discrete groups. The most natural metrics on discrete groups are those which come from the standard graph metric on a Cayley graph of the group. So a natural class of metric spaces to investigate are graph metrics.

2. Graph Metrics

If Γ = (V, E) is a connected graph with vertices V and edges E, then the standard metric d on V is defined by letting d(x, y) be the minimum length of a path from x to y. Given vertices x and y, we will use the notation [x, y] for an unspecified, but fixed, minimal path from x to y.

It is immediate that this metric gives V the discrete topology, so every function on V is continuous, (V, d) is automatically complete, and is locally compact. Furthermore (V, d) has a countable base if and only if V is countable, and d is proper if and only if the closed ball of radius 1 about every vertex is a finite set, or equivalently, if and only if every vertex has finite valence.

These restrictions on the graph are not very onerous at all. In particular most interesting Cayley graphs satisfy these restrictions:

Example 2.1. Let G be a finitely generated group with generating set S = S^{−1}. Then the Cayley graph of Γ_{G} = (G, E) corresponding to this generating set is a connected graph, with G countable, and every vertex has valence at most |S|. Hence (G, d) is a complete, locally compact, proper metric space with a countable base.

Because the metric takes on only integer values, we can make certain simplifying assumptions. We first note that the functions φ_{v} can only take integer values, and hence if γ is a weakly-geodesic ray which converges to some point ω ∈ ∂_{d}V,

φ_{v}(ω) = lim_{t→∞} φ_{v}(γ(t)) ∈ ℤ.

Moreover, if γ′ is another weakly-geodesic ray it converges to ω if and only if for every v ∈ V, φ_{v}(γ′(t)) = φ_{v}(γ(t)) eventually.

Also it is easy to see that if γ : T → V is a geodesic ray, then T ⊆ ℤ^{+}, and we can in fact extend the domain to all of ℤ^{+}: if T = {t_{0} = 0, t_{1}, t_{2}, …}, we simply find minimal paths [0, t_{1}], [t_{1}, t_{2}], [t_{2}, t_{3}],… and let γ(n) be the (n − t_{k−1})th point on the kth path for t_{k−1} < n < t_{k}.

Furthermore, it turns out that for these metrics, every Busemann point is in fact the limit of a geodesic ray.

Lemma 2.1. Let Γ = (V, E) be a connected graph, and d the usual graph metric. Then if ω ∈ ∂_{d}V is a Busemann point, there is a geodesic ray γ : T → V which converges to ω.

Proof. Let γ′ : T′ → V be an almost-geodesic ray which converges to ω. We can find an N such that for all s, t ∈ T′ with t ≥ s ≥ N, we have

|d(γ′(t), γ′(s)) + d(γ′(s), γ′(0)) − t| < 1/3.

In particular, |d(γ′(t), γ′(0)) − t| < 1/3. We let t_{0} = t′_{0} = 0, and find t_{n} ∈ ℕ and t′_{n} ∈ T′ so that t_{n} > t_{n−1}, t′_{n} ≥ N and d(γ′(t′_{n}), γ′(0)) = t_{n}. Let T = {t_{0}, t_{1}, t_{2}, …}, and define γ : T → V by γ(t_{n}) = γ′(t′_{n}). This implies that |t_{n}−t′_{n}| = |d(γ′(t_{n}), γ′(0)) − t′_{n}| < 1/3, and so t_{n} ≥ t′_{n} − 1/3.

Now for any t_{n}, t_{m} ∈ T, with n ≥ m, we have that

|d(γ(t_{n}), γ(t_{m})) − (t_{n} − t_{m})| ≤ |d(γ(t_{n}), γ(t_{m})) + t_{m} − t′_{n}| + 1/3

≤ |d(γ′(t′_{n}), γ′(t′_{m})) + d(γ′(t′_{m}), γ′(0)) − t′_{n}| + 1/3

≤ 2/3 < 1.

But both d(γ(t_{n}), γ(t_{m})) and (t_{n} − t_{m}) are integers, so

d(γ(t_{n}), γ(t_{m})) = |t_{n} − t_{m}|

and we conclude that γ is a geodesic ray. □

In particular, this lemma tells us that if we wish to show that a point on the boundary is not a Busemann point, it is sufficient to show that it is not the limit of any geodesic ray. The following simple example uses this fact to show that we cannot hope to answer Question 1 in the affirmative for general graphs.

Example 2.2. Let Γ = (V, E) be the graph where V = ℕ × {−1, 0, 1}, and there are edges joining

• (k, 1) and (k + 1, 1) for k ∈ ℕ,

• (k, −1) and (k + 1, −1) for k ∈ ℕ,

• (k, 1) and (k, 0) for k ∈ ℕ,

• (k, −1) and (k, 0) for k ∈ ℕ. This graph is illustrated in Figure 1.

[figure: (1, 1); (2, 1); (3, 1); (4, 1); (5, 1); (1, 0); (2, 0); (3, 0); (4, 0); (5, 0); (1, −1); (2, −1); (3, −1); (4, −1); (5, −1); ⋯; ⋯; ⋯]

Figure 1. The graph of Example 2.2

Simple calculations show that with (1, 0) as the base point and l > k, we have:

φ_{(k,1)}(x) = \begin{cases}k & for x = (l, 1) \\ k & for x = (l, 0) \\ k − 2 & for x = (l, −1) \end{cases} ,

φ_{(k,0)}(x) = k − 1,

φ_{(k,−1)}(x) = \begin{cases}k − 2 & for x = (l, 1) \\ k & for x = (l, 0) \\ k & for x = (l, −1) \end{cases} .

Hence the functions in G(V, d) which do not vanish at infinity are, for each j ∈ {1, 0, −1}, eventually constant for (l, j) as l goes to infinity, although the constants are different for different j.

Hence the metric boundary consists of just 3 points given by the following three weakly-geodesic rays:

(1) γ_{1} : ℕ → Γ, where γ_{1}(n) = (n, 1),

(2) γ_{0} : ℕ → Γ, where γ_{0}(0) = (1, 1), and γ_{0}(n) = (n, 0),
(3) γ_{−1} : ℕ → Γ, where γ_{−1}(n) = (n, −1).

Notice that γ_{1} and γ_{−1} are in fact geodesic rays; but γ_{0} is not.

In fact there is no geodesic ray which gives the same limit at infinity as γ_{0}, since points on any geodesic ray must eventually be either of the form (k, 1) or (k, −1). Hence lim_{n→∞} γ_{0}(n) is not a Busemann point.

It is perhaps of interest that all triangles this example are 2-slim (as in [1], for example), so this is a hyperbolic metric space.

Note that in the above example, there is no commonality in the minimal paths from (1, 1) to γ_{0}(n) and the minimal paths from (1, −1) to γ_{0}(n). Our key result is that this sort of situation precisely characterizes when there are metric boundary points which are not Busemann points.

Before proceeding, we make the following definition:

Definition 2.1. Let Γ = (V, E) be a connected graph and d the graph metric. The perimeter of a triple of vertices {a, b, c} is d(a, b) + d(b, c) + d(c, a).

In the example, we have a pair of vertices a and b for which we can find a sequence of vertices c_{n} such that the perimeters of the triples {a, b, c_{n}} get arbitrarily large, and there are no minimal paths from a and b to c_{n} which share a tail. The following theorem tells us that if there is such a pair of points, then this guarantees the existence of boundary points which are not Busemann points.

Theorem 2.2. Let Γ = (V, E) be a connected graph where V is countable and every vertex has finite valence, such that there is a pair of vertices a, b such that for every n ∈ ℕ, there is a vertex c_{n} ∈ V such that the triple {a, b, c} has perimeter m ≥ n, and no minimal paths [a, c] and [b, c] share a tail. Then there is a point in ∂_{d}V which is not a Busemann point.

Proof. Without loss of generality, we may assume that a is the base point for the functions φ_{v}.

The vertices c_{n} are a sequence in \overline{X}_{d}, which is compact, so there is a convergent subsequence c_{n_{k}}. Since the perimeters are getting bigger, the points c_{n_{k}} must head to infinity, and hence the limit point of c_{n_{k}} is an element ω of ∂_{d}V. By the same argument as Theorem 1.1, we can find a weakly-geodesic ray γ : T → V, corresponding to a subsequence of c_{n_{m}}, which converges to that point on the boundary. Without loss of generality, we may assume that γ(0) = a.

Now assume that ω is a Busemann point, so we can find a geodesic ray γ′ : ℕ → V with γ′(0) = a which converges to ω. For all v ∈ V, we must therefore have

lim_{t→∞} φ_{v}(γ(t)) = lim_{t→∞} φ_{v}(γ′(t)) = φ_{v}(ω).

But since φ_{v}(ω) takes on integer values only, for each v we can find some N_{v} such that for all t ∈ T with t ≥ N_{v},

φ_{v}(γ(t)) = φ_{v}(γ′(t)) = φ_{v}(ω).

In particular, for v = b, let y = φ_{b}(ω). Then for all t ≥ N_{b}

d(γ′(t), b) = d(γ′(t), a) − φ_{b}(γ′(t)) = t − y.

But we also have for such t that

d(γ(t), b) = d(γ(t), a) − φ_{b}(γ(t)) = t − y.

Now, fix a particular s ≥ N_{b} and consider v = γ′(s). Then for every t ∈ T with t ≥ s and t ≥ N_{γ′(s)},

φ_{γ′(s)}(γ(t)) = φ_{γ′(s)}(γ′(t))
= d(γ′(t), a) − d(γ′(t), γ′(s)) = t − (t − s) = s.

But this means that for such t,

d(γ(t), γ′(s)) = d(γ(t), a) − φ_{γ′(s)}(γ(t)) = t − s,

and so

d(γ(t), γ′(s)) + d(γ′(s), a) = (t − s) + s = d(γ(t), a).

In other words, there is a minimal path from a to γ(t) which goes through γ′(s). But also

d(γ(t), γ′(s)) + d(γ′(s), b) = (t − s) + (s − y) = t − y = d(γ(t), b).

So there is a minimal path from b to γ(t) which goes through γ′(s). So we have constructed two minimal paths which contradict our assumption for some c_{n} = γ(t). □

We now show that this condition is sharp: if the perimeter of bad triples like these is bounded for every pair of points, we can guarantee that all boundary points are Busemann points.

Theorem 2.3. Let Γ = (V, E) be a connected graph with V countable and each vertex has finite valence, and where for each pair of vertices a, b there is some number M_{a,b} such that if c is any vertex for which no minimal path from a to c shares a tail with a minimal path from b to c, then the perimeter of {a, b, c} is less than M_{a,b}. Then every point on the metric boundary is a Busemann point.

Proof. Let ω ∈ ∂_{d}V, and let γ : T → V be a weakly geodesic ray which converges to ω. Without any loss of generality (using the construction from Theorem 1.1) we can assume that T ⊆ ℕ and that d(γ(t), γ(0)) = t. We seek a geodesic ray which converges to ω.

Since V is countable, let {v_{k} : k ∈ ℕ} be an enumeration of V. Without loss of generality, we may assume that v_{0} = γ(0).

For each n we will inductively find a number m_{n}, a vertex w_{m_{n}} and a subsequence T_{n} of T with the following properties:

(1) d(w_{m_{n}}, γ(0)) = m_{n}.

(2) for all t ∈ T_{n}, and all v_{k} for k ≤ n, there exists a minimal path from v_{k} to γ(t) which passes through w_{m_{n}}.

(3) if n ≥ 1, then for all t ∈ T_{n}, there is a minimal path from w_{m_{n−1}} to γ(t) which passes through w_{m_{n}}.

Let m_{0} = 0, w_{0} = γ(0) and T_{0} = T. All conditions are trivially satisfied in this case.

Given m_{n}, w_{m_{n}} and T_{n}, let l = d(γ(0), v_{n+1}), let

M′ > (M_{w_{mn} ,v_{n+1}} − d(v_{n+1}, w_{m_{n}}))/2

be a whole number, and let m_{n+1} = m_{n} + M′ + l.

For each t ∈ T_{n} with t > m_{n+1}, three applications of the triangle inequality, using γ(0) as the third point in each case, tell us that d(v_{n+1}, w_{m_{n}}) ≤ m_{n} + l, d(v_{n+1}, γ(t)) ≥ m_{n+1} − l and d(w_{m_{n}}, γ(t)) ≥ m_{n+1} − m_{n}. Therefore

d(v_{n+1}, γ(t)) + d(w_{m_{n}}, γ(t)) ≥ 2m_{n+1} − m_{n} − l = 2M′ + m_{n} + l > M_{w_{mn} ,v_{n+1}}.

So by the hypotheses there is some vertex z_{t} where minimal paths from v_{n+1} to γ(t) and from w_{m_{n}} to γ(t) join, and we can assume that d(z_{t}, γ(0)) ≤ m_{n+1}, since otherwise {w_{m_{n}}, v_{n+1}, z_{t}} is a triple with perimeter greater than M_{w_{mn} ,v_{n+1}}, and we can find a closer point where the minimal paths join.

By following the minimal paths out to distance m_{n+1} from γ(0), we can have d(z_{t}, γ(0)) = m_{n+1} without loss of generality. In fact, z_{t} must be on a minimal path from every element of {v_{0}, v_{1}, …, v_{n+1}} ∪ {w_{m_{0}}, w_{m_{1}}, …, w_{m_{n}}} to γ(t), since we can find a minimal path from points v_{k} or w_{m_{k}} to γ(t) which passes through w_{m_{n}}, so we simply replace the tail of that path with the path from w_{m_{n}} to γ(t) which passes through z_{t}.

Now these points z_{t} may be different for different t ∈ T_{n}, but since each of these points lies in

S_{m_{n+1}}(γ(0)) = {v ∈ V : d(γ(0), v) = m_{n+1}},

and this is a finite set since d is proper, there must be at least one point w_{m_{n+1}} ∈ S_{m_{n+1}}(γ(0)) such that w_{m_{n+1}} = z_{t} for infinitely many t. Let T_{n+1} = {t : w_{m_{n+1}} = z_{t}}.

By construction, m_{n+1}, w_{m_{n+1}} and T_{n+1} satisfy all three conditions.

We claim that γ′ : T′ → V, where T′ = {m_{n} : n ∈ ℕ} and γ′(m_{n}) = w_{m_{n}} is a geodesic ray. This follows immediately from that fact that, by construction, given any s, t ∈ T′, with t > s, there is a minimal path from γ(0) to w_{t} which passes through w_{s}, and so

d(w_{t}, w_{s}) = d(w_{t}, γ(0)) − d(w_{s}, γ(0)) = t − s.

Finally, we claim that this geodesic ray converges to ω. Given any v_{n} ∈ V, we know that for t ∈ T′ with t > m_{n}, there is a minimal path from v_{n} to w_{t} which passes through w_{m_{n}}, and a minimal path from γ(0) to w_{t} which passes through w_{m_{n}}, and so

φ_{v_{n}}(w_{t}) = d(w_{t}, γ(0)) − d(w_{t}, v_{n})
= d(w_{t}, w_{m_{n}}) + d(w_{m_{n}}, γ(0)) − (d(w_{t}, w_{m_{n}}) + d(w_{m_{n}}, v_{n}))
= d(w_{m_{n}}, γ(0)) − d(w_{m_{n}}, v_{n}).

Hence

lim_{t→∞} φ_{v_{n}}(w_{t}) = d(w_{m_{n}}, γ(0)) − d(w_{m_{n}}, v_{n}).

On the other hand, given t ∈ T_{n}, there is a minimal path from γ(0) to γ(t) which passes through w_{m_{n}} and a minimal path from v_{n} to γ(t) which passes through w_{m_{n}}, and so

φ_{v_{n}}(γ(t)) = d(γ(t), γ(0)) − d(γ(t), v_{n})
= d(γ(t), w_{m_{n}}) + d(w_{m_{n}}, γ(0)) − (d(γ(t), w_{m_{n}}) + d(w_{m_{n}}, v_{n}))
= d(w_{m_{n}}, γ(0)) − d(w_{m_{n}}, v_{n}).

Since T_{n} is a subsequence of T,

φ_{v_{n}}(ω) = lim_{t∈T_{n}} φ_{v_{n}}(γ(t)) = d(w_{m_{n}}, γ(0)) − d(w_{m_{n}}, v_{n}),

and so φ_{v_{n}} does not separate the limits of the two sequences.

Since this happens for every v_{n}, we have that

ω = lim_{n→∞} w_{m_{n}}.

Hence ω is a Busemann point. □

It is perhaps worth noting that the proof of these result extends to the slightly more general case of weighted graph metrics with edge weights in ℕ, or in fact, λℕ for any λ > 0.

Example 2.3. Let Γ = (V, E) be a tree. Since the only way that the unique minimal paths [a, c], and [b, c] can fail to share a tail is if c is on the unique minimal path [a, b], we conclude that if d(a, b) = n, then the minimal paths must share a tail if the perimeter of the triple {a, b, c} is greater than 2n. Hence every metric boundary point of a tree is a Busemann point.

Example 2.4. Consider the integer lattice V = ℤ^{d} ⊂ ℝ^{d} as the set of vertices, with edges joining vertices which differ by ±e_{k}, where e_{k} is a standard basis vector in ℝ^{d}, so Γ = (V, E) is the Cayley graph of ℤ^{d} with the standard generators. Here there are many possible minimal paths between points, in general. Given a fixed pair of points a and b, and any point c, the only way that there can be no minimal path [a, c] which shares a tail with a minimal path [b, c] is if c lies on some minimal path [a, b]. So once again these minimal paths must share a tail if the perimeter of {a, b, c} is greater than 2n. Hence every metric boundary point of such a lattice is a Busemann point.

An obvious question arises concerning the way in which boundaries of related graphs may be related. For example, two metric spaces (X_{1}, d_{1}) and (X_{2}, d_{2}) are Lipschitz equivalent, if there is a bijection T : X_{1} → X_{2} and constants λ_{1}, λ_{2} > 0 such that for all a and b ∈ X_{1} with a ≠ b

\frac{d_{2}(T (a), T (b))}{d_{1}(a, b)} ≤ λ_{1}  and  \frac{d_{1}(a, b)}{d_{2}(T (a), T (b))} ≤ λ_{2}.

It is known from Rieffel’s work that Lipschitz equivalent metric spaces may have different metric boundaries (even for graph metrics), and as the following example shows, even if the metric boundaries are naturally homeomorphic, which points are Busemann points may vary.

Example 2.5. Let Γ_{1} be the graph of Example 2.2, and let Γ_{2} be the same graph, but with additional edges from (k, 0) to (k+1, 0). The metric boundary of this second graph is homeomorphic to the metric boundary of the first graph and the boundary points are the limits of corresponding weakly-geodesic rays, but every metric boundary point of Γ_{2} is a Busemann point. However, the identity map on the vertices gives a Lipschitz equivalence between the two metric spaces, with

\frac{d_{2}(a, b)}{d_{1}(a, b)} ≤ 1  and  \frac{d_{1}(a, b)}{d_{2}(a, b)} ≤ 3.

3. Cayley Graphs

Our primary motivation is in the Cayley graphs of groups. Recall that G = ⟨S|R⟩ is a presentation of a group if S is a set of symbols, R is a set of reduced words in S, and if G is isomorphic to the group of equivalence classes of words in S ∪ S^{−1} where two words are equivalent if you can change one word to another by adding and removing subwords of the form ss^{−1} for s ∈ S ∪ S^{−1}, and subwords of the form r or r^{−1} for r ∈ R. If this is the case, then G ≡ F_{|S∪S^{−1}|}/N, where F_{k} is the free group on k generators, and N is the normal subgroup of the free group generated by R. A presentation is finite if both S and R are finite sets.

Even in the case of Cayley graphs of finitely presented groups, we can have metric boundary points which are not Busemann points.

Example 3.1. Consider the group G = ⟨a, b, c, d|aba^{−1}dcd^{−1}⟩. Then the only minimal path from a to ab^{n}a^{−1} is b^{n}a^{−1}, and the only minimal path from d to ab^{n}a^{−1} = dc^{n}d^{−1} is c^{n}d^{−1}.

So {a, ab^{n}a^{−1}, d} is a triple with perimeter 2n + 2, and so we have a metric boundary point which is not a Busemann point by Theorem 2.2.

On the other hand, the Cayley graph of a finitely generated free group with the standard generating set is a tree, so by Example 2.3 we have that every metric boundary point is a Busemann point. Similarly the Cayley graph of the free Abelian group ℤ^{d} with its standard generating set gives the graph of Example 2.4, so we have that every metric boundary point is a Busemann point.

Since Cayley graphs have a lot more symmetry than arbitrary graphs, we introduce the following definition which is easier to verify than the condition of the previous section.

[figure: x; y; z; x; y; z]

Figure 2. Rigid and Non-rigid Triples

Definition 3.1. Let Γ = (V, E) be a graph. A rigid triple is a set of 3 vertices such that if x is any one of these vertices, and y and z are the other two, then there are no minimal paths [x, y] and [x, z] which share a vertex other than x.

Figure 2 illustrates the intuitive difference between rigid and non-rigid triples. In the Example 2.2, the sets {(1, 1), γ_{0}(n), (−1, 1)} are rigid triples, with one

side having length 2, and the perimeter of these triples is 2n + 2, so we have an infinite family of rigid triples of increasing perimeter but with one side of bounded length. The following two propositions show that this sort of situation cannot occur in some important cases.

The utility of rigid triples is that if the only way they can have large perimeter is if all the sides get large, we are guaranteed that all boundary points are Busemann points.

Proposition 3.1. Let Γ = (V, E) be a graph where for every n there is an M_{n} such that every rigid triple {x, y, z} with d(x, y) = n has perimeter bounded above by M_{n}. Then if {a, b, c} is any triple of points with d(a, b) = n and

d(a, c) + d(b, c) > n + max{M_{k} : k = 1, …, n},

there are minimal paths [a, c] and [b, c] which share a tail.

Proof. Assume that there are no such minimal paths.

Let [a, b], [a, c], [b, c] be minimal paths which maximize the total number of edges in common between [a, b] and [a, c], and between [b, a] and [b, c]. The total number of edges that [a, b] shares with the other two paths is at most n − 1, since if it were n then every edge of [a, b] would coincide with an edge from one of the other two paths, meaning that either c lies on [a, b], or [a, c] and [b, c] must meet before c. The first case cannot occur, since then d(a, c) + d(b, c) = n, contradicting the hypotheses, and the second would imply that there are minimal paths from a to c and b to c which share a tail. Let x be the last vertex in common between [a, b] and [a, c], and y the last vertex in common between [b, a] and [b, c].

It is clear that {x, y, c} is a rigid triple, otherwise we could either find more common edges, or find minimal paths [a, c] and [b, c] which share a tail. Let d(x, y) = k ≤ n. The perimeter of the triple is

d(x, c) + d(y, c) + d(x, y) = (d(a, c) − d(a, x)) + (d(b, c) − d(b, x))+
(d(a, b) − d(a, x) − d(b, y))
= (d(a, c) + d(b, c)) + d(a, b) − 2(d(a, x) + d(b, y))
> M_{k} + n + n − 2(n − 1) > M_{k}

Hence {x, y, c} cannot be a rigid triple, and we have a contradiction. □

Corollary 3.2. Let Γ = (V, E) be a graph where for every n there is an M_{n} such that every rigid triple {x, y, z} with d(x, y) = n has perimeter bounded above by M_{n}. Then every point on the metric boundary is a Busemann point.

For Cayley graphs of groups, this is again a precise characterization of the situation where all boundary points are Busemann points.

Proposition 3.3. Let G be a finitely generated group, with generating set S. If for the corresponding Cayley graph, there is some n such that for all m there is a rigid triple {x, y, z} with d(x, y) = n and perimeter greater than m, then there is a point on the metric boundary which is not a Busemann point.

Proof. Without loss of generality, since this is a Cayley graph, for each m we can find rigid triples {e, y_{m}, z_{m}} with d(e, y_{m}) = n such that the perimeter is greater than m. Since the valence of each vertex of the graph is finite, the ball of radius n contains a finite number of points, and so there must be some particular y with d(e, y) = n such that y = y_{m} for infinitely many m, and the minimal paths [e, z_{m}], [y, z_{m}] clearly do not share a tail. Thus e and y are a pair of vertices which satisfy the conditions of Theorem 2.2. Hence the metric boundary of the graph contains a point which is not a Busemann point. □

This proposition will also hold in the setting of an arbitrary graph of finite valence with an automorphism group which acts transitively on the vertices.

We can use this last proposition to prove the following:

Proposition 3.4. Let G be a group presented by a finite set of generators S = S^{−1} with |S| = k such that G ≅ F_{k}/N, where N is the normal subgroup of elements of the free group generated by S which map to e. Let N be finitely generated with generating set R, and let M be the maximum length of an element of R in F_{S}.

If Γ is the Cayley graph of G with generating set S, no rigid triple has perimeter greater than 3M/2, and so every metric boundary point is a Busemann point.

Proof. Assume that there is a rigid triple whose perimeter P is greater than 3M/2. We first note that from the triangle inequality the distance between any two of the vertices is at most P/2, and that the distance between at least one pair of vertices must be greater than or equal to P/3.

Without loss of generality, we may assume that one vertex is the identity e of G. Let x and y be the other two vertices, and we can assume that d(e, x) ≥ P/3.

Let w_{x}, w_{x^{−1}y} and w_{y^{−1}} be minimal words representing x, x^{−1}y and y^{−1}. Let w be the concatenation of w_{x}, w_{x^{−1}y} and w_{y^{−1}} in F_{k} and observe that w projects onto a loop which is the concatenation of minimal paths [e, x], [x, y] and [y, e] in G. Since the triple {e, x, y} is rigid, there can be no cancellation within w, and so w is a reduced word in F_{k}. Moreover, since the image of w in G is e, so w ∈ N. But l(w) > M, so w cannot be a generator of N, and so we can write w = g_{1}g_{2} … g_{n}, where g_{k} ∈ R, and so l(g_{k}) ≤ M.

Pushing the g_{k} down to G, we can see that each g_{k} is a loop in the Cayley graph which starts and ends at e. Moreover, x must lie on at least one of these loops, say the loop corresponding to g_{k}. But since this loop has length at most M, d(e, x) ≤ M/2.

So we have d(e, x) ≥ P/3 > M/2 ≥ d(e, x), which is a contradiction. Hence no rigid triple has perimeter greater than 3M/2. □

Not every finitely generated group has a finitely generated group of relations. Nevertheless, in some cases even when the defining set of relations is infinite, there is a limit on the size of rigid triples. For example, ℤ^{n} with the standard generators can be easily seen to have no rigid triples.

As might be expected, having an absolute bound on the size of rigid triples is an exceptional situation, even for very nice presentations of groups.

Example 3.2. Let G be the subgroup of ℂ generated by e^{kπi/3} for k = 0, 1, …, 5. G is isomorphic to ℤ^{2}, but the Cayley graph consists of the vertices and edges of a tessellation of the plane by equilateral triangles of side length 1.

Triples of the form {0, k, ke^{πi/3}} are rigid for all k, so we have rigid triples of arbitrarily large perimeter. However, one can see that if the distance between two points is n, then the maximum size of a rigid triple is 3n, and so every boundary point is a Busemann point.

We conclude with some more examples.

Example 3.3. The free product group G = ℤ_{2}∗ℤ_{3} is generated by a, a^{−1}, b and b^{−1}, and the relations a^{2} = e, b^{3} = e. The largest rigid triples are the triples {a, ab, ab^{2}}, which have perimeter 3. Hence by Proposition 3.1, every metric boundary point is a Busemann point.

Similar analysis shows that for any finite free product ∗F_{k} of finite groups F_{k}, k = 1, …, n, with generators the disjoint union S = ⋃_{k=1}^{n} S_{k} where S_{k} generates F_{k}, the Cayley graph has rigid triples of size at most max |F_{k}|, and so every metric boundary point is a Busemann point.

Example 3.4. The braid group on n strands, B_{n}, is given by generators {σ_{k}, σ_{k}^{−1} : k = 1, …, n − 1} and relations σ_{k}σ_{k+1}σ_{k} = σ_{k+1}σ_{k}σ_{k+1} for k = 1, …, n − 2, and σ_{j}σ_{k} = σ_{k}σ_{j} for |j − k| > 1.

Considering B_{3}, we note that the relations imply that σ_{1}σ_{2}σ_{1}^{−1} = σ_{2}^{−1}σ_{1}σ_{2}, and so σ_{1}σ_{2}^{n}σ_{1}^{−1} = σ_{2}^{−1}σ_{1}^{n}σ_{2}.

Exactly as in Example 3.1, we have that the triples {σ_{1}, σ_{2}^{−1}, σ_{1}σ_{2}^{n}σ_{1}^{−1}} satisfy the conditions of Theorem 2.2, and so this braid group has a non-Busemann point in its metric boundary. By the same idea, we see that the families of triples {σ_{1}, σ_{2}^{−1}, σ_{1}σ_{2}^{−n}σ_{1}^{−1}}, {σ_{1}^{−1}, σ_{2}, σ_{1}^{−1}σ_{2}^{n}σ_{1}}, and {σ_{1}^{−1}, σ_{2}, σ_{1}^{−1}σ_{2}^{−n}σ_{1}} satisfy Theorem 2.2, so we have at least 4 distinct sets of non-Busemann points.

The same construction will work for any pair of generators σ_{k} and σ_{k+1} of a braid group B_{n}.

We comment here that if we add a generator b = σ_{1}σ_{2}σ_{1}^{−1}, then just as in Example 2.5 we get a new metric which is Lipschitz equivalent to the original metric, but for which this particular non-Busemann point becomes a Busemann point. Hence even in the special setting of Cayley graphs, Lipschitz equivalence

[figure: e; x; c_{j}; k; m; n]

Figure 3. Cayley Graph of the Heisenberg Group

does not preserve whether or not a boundary point is a Busemann or non-Busemann point.

It is unclear whether or not the existence of non-Busemann points for Cayley graphs is invariant under Lipschitz equivalence; or even under change of finite generating set. It would be interesting to know the answer to this question, but we conjecture based on Example 2.5 that for some groups at least, the existence of non-Busemann points on the boundary will depend upon the generating set.

Example 3.5. The discrete Heisenberg group is the following multiplicative subgroup of GL_{3}

H_{d}^{3} = \{[\begin{matrix}1 & m & n \\ 0 & 1 & k \\ 0 & 0 & 1 \end{matrix}] : m, n, k ∈ ℤ\} .

Let

a = [\begin{matrix}1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]  and  b = [\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}] .

Then S = {a, b, a^{−1}, b^{−1}} is a generating set for H_{d}^{3}. The Cayley graph of this group with this generating set is illustrated in Figure 3.

Triples {e, x = aba^{−1}b, c_{j} = b^{j−1}ab} have perimeter 4 + 2(j + 1), and there is a unique minimal path b^{j−1}ab from e to b^{n−1}ab, and a unique minimal path b^{j}a from aba^{−1}b to b^{j−1}ab. These minimal paths share no common tail, so by Theorem 2.2, there is a non-Busemann point on the metric boundary of the Cayley graph.

Indeed, there are many non-Busemann points. Triples of the form

{e, x, b^{j+1}a^{−1}b}

are also rigid and give distinct non-Busemann points from the above cases. The group action by multiplication on the left give yet more examples, as do the triples formed by the inverses of these. Another class of examples are triples of the form

{b, b^{−1}, b^{k}a^{−k}b^{−k}a^{k} = b^{−k}a^{k}b^{k}a^{−k}},

as well as left translates and inverses of these.

There are some Busemann points, however. The functions γ_{n,k}^{v,±} : ℕ → H_{d}^{3}

γ_{n,k}^{v,±}(t) = [\begin{matrix}1 & ±t & n \\ 0 & 1 & k \\ 0 & 0 & 1 \end{matrix}]

are geodesic rays for fixed choice of n and k, + or −. Similarly the functions γ_{m,n,j}^{±} : ℕ → H_{d}^{3} given by

γ_{m,n}^{h,±}(t) = [\begin{matrix}1 & m & n ± tm \\ 0 & 1 & ±t \\ 0 & 0 & 1 \end{matrix}]

are geodesic rays for fixed choice of n, k and + or −. All of these geodesic rays give distinct Busemann points.

The discrete Heisenberg group is of some significance, since it is amenable, and hence has an amenable action on its metric boundary. It therefore may be susceptible to the sort of analysis that Rieffel used in his discussion of ℤ^{d}. This would require finding enough boundary points with finite orbits under the left action of the group on the boundary. Unfortunately, all the boundary points described above have infinite orbits.

However, we have certainly not exhausted all possible boundary points in this example. For example, if we let ω_{n,k}^{v,+} be the boundary point corresponding to the geodesic ray γ_{n,k}^{v,+}, we conjecture that there is a boundary point or points of the form

ω = lim_{t→∞} ω_{n_{t},k_{t}}^{v,+}

where n_{t} → ∞ and k_{t} → ∞ as t → ∞, with n_{t} ≥ αk_{t} eventually for any α, and that this point or points are fixed points of the action on the boundary.

Finally, it is common to consider

c = [\begin{matrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}]

as a generator of H_{d}^{3} as well, and if this vertex is added to S, many of the examples above remain rigid in the new metric. It may be that this metric is more amenable to study. Of course we would like to be able to find the metric boundary for arbitrary finite generating sets, but this problem seems difficult in general.

References

[1] J. M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, and H. Short (Editor). Notes on word hyperbolic groups. In Group theory from a geometrical viewpoint (Trieste, 1990), pages 3–63. World Sci. Publishing, 1991.

[2] C. Anantharaman-Delaroche and J. Renault. Amenable Groupoids, volume 36 of Monographies de L’Enseignement Mathmatique. L’Enseignement Mathmatique, Geneva, 2000.

[3] Claire Anantharaman-Delaroche. Amenability and exactness for dynamical systems and their C*-algebras. Trans. Amer. Math. Soc., 354:4153–4178, 2002, arXiv:math.OA/0005014.

[4] A. Connes. Compact metric spaces, Fredholm modules and hyperfiniteness. Ergodic Theory Dynamical Systems, 9(2):207–220, 1989.

[5] Mike Develin. Cayley compactifications of Abelian groups. Annals of Combinatorics, 6:295– 312, 2002.

[6] M. Gromov. Hyperbolic manifolds, groups and actions. In Riemann surfaces and related topics: Proceedings of the 1978 Stony Brook Conference, pages 182–213. Princeton University Press, 1981.

[7] W. Ledermann. Introduction to Group Theory. Longman Scientific & Technical, 1973.

[8] Marc A. Rieffel. Metrics on states from actions of compact groups. Doc. Math., 3:215–229, 1998, arXiv:math.OA/9807084.

[9] Marc A. Rieffel. Metrics on state spaces. Doc. Math., 4:559–600, 1999, arXiv:math.OA/9906151.

[10] Marc A. Rieffel. Group C*-algebras as compact quantum metric spaces. Doc. Math., 7:605– 651, 2002, arXiv:math.OA/0205195.

Department of Mathematical Sciences, University of Nevada Las Vegas, Las Vegas, NV 89154

E-mail address: cwebster@unlv.nevada.edu