Generalising some results about right-angled Artin groups to graph products of groups

Derek F. Holt^{a}, Sarah Rees^{b,∗}

aMathematics Institute, University of Warwick, Coventry CV4 7AL, UK

bSchool of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK

Abstract

We prove three results about the graph product G = G(Γ; G_{v}, v ∈ V (Γ)) of groups G_{v} over a graph Γ. The first result generalises a result of Servatius, Droms and Servatius, proved by them for right-angled Artin groups; we prove a necessary and sufficient condition on a finite graph Γ for the kernel of the map from G to the associated direct product to be free (one part of this result already follows from a result in S. Kim’s Ph.D. thesis). The second result generalises a result of Hermiller and S̆unić, again from right-angled Artin groups; we prove that, for a graph Γ with finite chromatic number, G has a series in which every factor is a free product of vertex groups. The third result provides an alternative proof of a theorem due to Meier, which provides necessary and sufficient conditions on a finite graph Γ for G to be hyperbolic.

Keywords: groups, graph product, hyperbolic groups

1. Introduction

Given a simplicial graph Γ, and vertex groups G_{v} for each v ∈ V (Γ), we use the notation G(Γ; G_{v}, v ∈ V (Γ)) to denote the associated graph product of groups. Where there is no ambiguity in the choice of the vertex groups G_{v}, we may abbreviate this to G(Γ).

The group G(Γ) is the ‘largest’ group generated by the vertex groups such that G_{u} and G_{v} commute whenever u and v are joined by an edge in Γ. More precisely, it is the quotient of the free product of the groups G_{v} by the normal closure of the set of all commutators [g_{u}, g_{v}] with g_{u} ∈ G_{u}, g_{v} ∈ G_{v} and u ∼ v. The right-angled Artin groups, also known as graph groups, are precisely the graph products in which all vertex groups are infinite cyclic groups, while the right-angled Coxeter groups arise from vertex groups of order 2.

∗Corresponding author

Email addresses: D.F.Holt@warwick.ac.uk (Derek F. Holt), Sarah.Rees@ncl.ac.uk (Sarah Rees)

Preprint submitted to Journal of Algebra August 24, 2012

In this article we prove three results about the graph product G = G(Γ; G_{v}, v ∈ V (Γ)) of groups G_{v} over a graph Γ. The first result, found in Theorem 3.1 and Theorem 3.2, generalises a result of Servatius, Droms and Servatius, proved for right-angled Artin groups in [10]; we prove a necessary and sufficient condition on a finite graph Γ for the kernel of the map from G to the associated direct product to be free. Part of this result was already known, proved in [15]. The second result, Theorem 4.1, generalises a result of Hermiller and S̆unić [12] again from right-angled Artin groups; we prove that, for a graph Γ with finite chromatic number, G has a series in which every factor is a free product of vertex groups. The third result, Theorem 5.1, provides an alternative proof of a theorem due to Meier [18], which provides necessary and sufficient conditions on a finite graph Γ for G to be hyperbolic.

While the graph product construction might seem merely to be a generalisation of direct and free products, it has produced some groups with rather interesting properties, including a group (a subgroup of a right-angled Artin group) that has FP but is not finitely presented [1] and a group (F_{2}×F_{2}) with insoluble subgroup membership problem [19]. Right-angled Artin groups [2] and Coxeter groups have been particularly studied; their actions on CAT(0) cubical complexes give them interesting geometrical properties.

Graph products were introduced by Green in her PhD thesis [9], where in particular a normal form was developed and the graph product construction was shown to preserve residual finiteness; this work was extended by Hsu and Wise in [13], where right-angled Artin groups were shown to embed in right-angled Coxeter groups and hence to be linear. The preservation of semihyperbolicity, automaticity (as well as asynchronous automaticity and biautomaticity) and the possession of a complete rewrite system under graph products is proved in [11], necessary and sufficient conditions for the preservation of hyperbolicity in [18], the question of when the group is virtually free in [16], of preservation of orderability in [5]. The representation of the group as a graph product of directly indecomposable groups was shown to be unique in [21]. Automorphisms and the structure of centralisers for graph products of groups have been the subject of recent study, and in particular graph products defined over random graphs have provoked some interest for their applications [6, 4, 3].

2. Notation and basic properties

We use standard notation from graph theory. So for v, w ∈ V (Γ) we say that v, w are adjacent if {v, w} is an edge, and write v ∼ w. If v, w are non-adjacent we write v ≁ w.

A normal form for elements of graph products is developed in [9]. Each element g ∈ G(Γ) can be written as a product g_{1} ⋯ g_{k} with each g_{i} in a vertex group G_{v_{i}}. We shall call such a product an expression for g, and the elements g_{i} the syllables of the expression. The expression is reduced if the syllable length k is minimal among all such expressions for g. Note that the identity element of G has syllable length 0.

The operation of replacing g_{i}g_{i+1} by g_{i+1}g_{i} within an expression, when v_{i} ∼ v_{i+1}, is called a shuffle. We need the following technical result.

Proposition 2.1. [9, Theorem 3.9] For g ∈ G(Γ), any expression for g can be transformed to any reduced expression for g by a succession of shuffles and group multiplications within the vertex groups.

Now suppose that, for each vertex v of Γ, X_{v} is a generating set for G_{v}, and that X = ∪_{v∈V (Γ)}X_{v}. The next result is a consequence of Proposition 2.1.

Proposition 2.2. For g ∈ G(Γ) a non-geodesic word for g over X can be reduced to a shorter representative by a succession of shuffles followed by a replacement of a subword over X_{v} by a shorter such word, for some vertex v of Γ.

Proof: Suppose that w is a non-geodesic word over X representing g. We can write w as a concatenation w_{1} ⋯ w_{k} of maximal subwords over the generating sets X_{v} and hence find an expression g_{1} ⋯ g_{k} for g for which g_{i} is an element of a vertex group G_{v_{i}}, represented by the subword w_{i}.

We prove the result by induction on k.

If the expression is reduced, then one of the subwords w_{i} must be non-geodesic, and hence can be replaced by a shorter subword. This includes the case where k = 1.

Otherwise, the expression can be transformed to a reduced expression by a succession of shuffles and multiplications within vertex groups. The first such multiplication must be applied to an expression represented by a word that can be derived from w by a series of shuffles only. The expression resulting from that multiplication, which is represented by the same word, has shorter syllable length, and the result now follows by induction. □

3. Generalising Servatius, Droms and Servatius

In this section we generalise two theorems of Servatius, Droms and Servatius.

In [10, Theorem 1] the following is proved:

Let G be the right-angled Artin group defined by the n-cycle C_{n} with n ≥ 3. Then G′ has a subgroup isomorphic to the fundamental group of the orientable surface of genus 1 + (n − 4)2^{n−3}.

We generalise this to prove the same statement for a graph product of groups, namely:

Theorem 3.1. Let G = G(Γ; G_{v}, v ∈ V (Γ)) be a graph of non-trivial groups, for which Γ is a cycle of length n with n ≥ 3. Then the kernel of the natural map from G to G_{v_{1}} ×⋯×G_{v_{n}} contains the fundamental group of the orientable surface of genus 1 + (n − 4)2^{n−3}.

In fact this result was already known for n ≥ 5 (and it is straightforward to prove for n=3,4); however our proof is short and elementary. For n ≥ 5 the result is proved in Sang-hyun Kim’s 2007 thesis [15, Theorem 3.6] using Van Kampen diagrams, and for n ≥ 6 another quite different proof is provided in [14, Corollary 1.3].

In [10, Theorem 2] the following is proved:

Let G be the right-angled Artin group defined by a finite graph Γ. Then G′ is free if and only if Γ does not contain C_{n} as an induced subgraph for any n ≥ 4.

We generalise this in the following result.

Theorem 3.2. Let G = G(Γ; G_{v}, v ∈ V (Γ)) be a graph product of non-trivial groups with V (Γ) = {v_{1}, …, v_{n}} finite. Then the kernel of the natural map from G to G_{v_{1}} × ⋯ × G_{v_{n}} is free if and only if Γ does not contains a cycle of length 4 or more as an induced subgraph.

From now on we shall use the notation K(G) for the kernel of that natural map that appears in both theorems.

Proof of Theorem 3.1: This proof closely follows and generalises the proof of [10, Theorem 1]. We have modified the notation and terminology in places.

We begin with a technical lemma.

Lemma 3.3. Suppose that Γ is a graph, Δ an induced subgraph of Γ, and that G_{v}, v ∈ V (Γ), H_{v}, v ∈ V (Δ) are groups with H_{v} ⊆ G_{v} for all v ∈ V (Δ). Suppose that G = G(Γ; G_{v}(v ∈ V (Γ))) and H = G(Δ; G_{v}(v ∈ V (Δ))). Then (1) H embeds naturally in G as the subgroup ⟨H_{v} : v ∈ V (Δ)⟩, and

(2) K(H) = K(G) ∩ H.

Proof: The natural embedding of H in G as a subgroup follows from [9, Proposition 3.31], and the rest is then immediate. □

Applying Lemma 3.3 in the case where Δ = Γ and the H_{v}’s are cyclic subgroups of the G_{v}’s, we see that it is sufficient to prove the result of the theorem in the case where the vertex groups are non-trivial cyclic. In that case, the kernel is simply G′.

We choose generators x_{v} (v ∈ V (Γ)) for the cyclic groups G_{v} and suppose that x_{v} has order k_{v} ∈ ℕ ∪ {∞}, with k_{v} > 1.

The group G has the presentation

⟨x_{v}, (v ∈ V (Γ)) | x_{v}^{k_{v}}, [x_{v}, x_{u}] (v ∈ V (Γ), u ∼ v)⟩.

We define X_{G} to be the associated presentation complex of G, which has a single 0-cell, a 1-cell for each x_{i} and a 2-cell for each relator, attached along the appropriate sequence of 1-cells. Each relator is either a commutator of generators or a power of a generator, and we call the two kinds of associated 2-cells commutator cells and power cells.

We write K for K(G) = G′ and define X_{G/K} to be the presentation complex of G/K, using the presentation

⟨x_{v} (v ∈ V (Γ)) | x_{v}^{k_{v}}, [x_{v}, x_{u}] (v, u ∈ V (Γ))⟩.

Clearly X_{G} embeds in X_{G/K}.

We define X̃_{G/K} to be the universal cover of X_{G/K}, and then Z to be the subcomplex of X̃_{G/K} obtained from it by deleting the lifts of all 2-cells of X_{G/K} that correspond to commutators not present in the presentation of G. Then Z covers X_{G} and has K as its fundamental group.

Now let w be a word in the generators x_{v} representing the identity in G. Then it is a consequence of Proposition 2.1 (using an argument similar to the proof of Proposition 2.2), that w can be transformed to the empty word ϵ by a combination of the following moves:

M1 delete a subword x_{v}x_{v}^{−1} or x_{v}^{−1}x_{v},

M2 delete a subword of the form x_{v}^{k_{v}} or x_{v}^{−k_{v}},

M3 replace a subword x_{v}^{±1}x_{u}^{±1} by x_{u}^{±1}x_{v}^{±1}, where u ∼ v.

Since the 1-skeleton of X̃_{G/K} can be identified with the Cayley graph of G/K, and is also equal to the 1-skeleton of Z, the edges in the 1-skeleton of Z can be oriented and labelled by the generators x_{v} of G. Suppose that p is a path in Z that is homotopic to the trivial loop, and let w be the label of p. Then w represents the identity of G, and there is a sequence of words w = w_{1}, w_{2}, …, w_{k} = ϵ, such that each w_{i} transformed into w_{i+1} by a move of type M1, M2 or M3, and a corresponding sequence of loops

p = p_{1} → p_{2} → ⋯ → p_{k},

with p_{k} the trivial loop, where p_{i} is labelled by w_{i}. Then p_{i+1} is contained within p_{i} if the move has type M1 or M2, or within p_{i} ∪ F, where F is a face of Z intersecting p_{i} in 2 consecutive edges, if the move has type M3.

So now if Y is a subcomplex of Z such that (1) Y contains any power cell of Z of which it contains the 1-skeleton and (2) Y contains any commutator cell of Z (and its incident vertices and

edges) of which it contains two adjacent edges,

then the natural embedding of Y in Z induces an embedding of π_{1}(Y) as a subgroup of π_{1}(Z).

Both conditions are satisfied by the following subcomplex Y. Fix a vertex v of Z. Then Y consists of all the vertices and edges of Z on paths from v labelled by words x_{v_{1}} ⋯ x_{v_{k}} with all v_{j} distinct, together with all 2-cells of Z whose 1-skeletons are in Y. Intuitively Y is the intersection of the unit cube with Z; note that Y contains no power cells, and so this is the same subcomplex as in [10]; hence Condition (1) (which does not arise in [10]) holds vacuously.

Just as in [10] we observe that Y is an orientable surface of Euler characteristic (4 − n)2^{n−2} and hence genus 1 − \frac{1}{2}χ(Y) = 1 + (n − 4)2^{n−3}. □

The remainder of this section is devoted to the proof of Theorem 3.2. The ‘only if’ part of the theorem follows from Theorem 3.1 and Lemma 3.3. Then the ‘if’ part is an immediate consequence of the following result.

Proposition 3.4. Let Γ be a finite graph that does not contain a cycle of length 4 or more as an induced subgraph, let G_{v}, for v ∈ V (Γ), be arbitrary groups, and let G = G(Γ; G_{v}, v ∈ V (Γ)). Then K(G) is free.

The proof of Proposition 3.4 follows closely and generalises the proof of [10, Theorem 2].

Proof of Proposition 3.4: Write K = K(G). If Γ is the complete graph, then G is the direct product of the vertex groups and K is the identity subgroup, so the result holds.

The proof is by induction on the number n of vertices, the case n = 1 being covered by the above.

For n > 1 and Γ not complete, it follows from [17, Solution to Problem 9.29b] (as explained in the proof of the lemma in [8]) that Γ can be written as the union of proper subgraphs Γ_{1} and Γ_{2}, whose intersection Γ_{12} is either complete, or empty (if Γ is disconnected). Then G ≅ G_{1} ∗_{G_{12}} G_{2}, where G_{1} = G(Γ_{1}; G_{v}, v ∈ V (Γ_{1})), G_{2} = G(Γ_{2}; G_{v}, v ∈ V (Γ_{2})), and G_{12} = G(Γ_{12}; G_{v}, v ∈ V (Γ_{12})). Now by Lemma 3.3, K(G_{1}) = K ∩ G_{1}, K(G_{2}) = K ∩ G_{2} and K(G_{12}) = K ∩ G_{12}. By the induction hypothesis, K(G_{1}) and K(G_{2}) are free and, since Γ_{12} is complete, K(G_{12}) is the identity subgroup, and hence so is K ∩ G_{12}. Now, as an amalgamated free product, G is the fundamental group of a graph of groups (as defined in [7]), for the graph consisting of a single edge, with vertex groups G_{1}, G_{2} and edge group G_{12}. Since K ∩ G_{12} and hence also (by the normality of K) the intersections of K with all conjugates of G_{12} are trivial, we can apply [7, Theorem I.7.7] to deduce that K is a free product of a free group F with subgroups of conjugates of the vertex groups K(G_{1}) and K(G_{2}). So K is free as claimed. □

4. Generalising Hermiller and S̆unić

Theorem 4.1. Suppose that Γ is a graph with finite chromatic number chr(Γ), and G = G(Γ; G_{v}, v ∈ V (Γ)) a graph of groups. Then there is a series

G = G_{0} ▷ G_{1} ▷ ⋯ ▷ G_{chr(Γ)} = 1,

such that each factor G_{i−1}/G_{i} is the free product of copies of vertex groups G_{v}.

Proof: The proof is based on the proof of [12, Theorem A], which deals with the special case where G is a right-angled Artin group. We use induction on chr(Γ). If chr(Γ) = 1 then there are no edges, and so G is a free product of the vertex groups G_{v}.

Now suppose that chr(Γ) > 1. Then given a colouring of the graph with chr(Γ) colours, we define the subset D of the vertices to be all those of one particular colour, and put L = V (Γ)\D. (This follows the notation of [12], where D and L are referred to as the dead and living vertices.) Let Γ_{L} be the induced subgraph with vertex set L, and define G_{L} := G(Γ_{L}; G_{v}, v ∈ L). For each vertex v, we let ⟨X_{v} | S_{v}⟩ be a presentation for G_{v}; and we let ⟨X_{L} | S_{L}⟩ be a presentation for G_{L}, where X_{L} = ∪_{l∈L}X_{l} and S_{L} is the union of S_{l} (l ∈ L) and the commutator relations derived from Γ_{L}.

The result holds for G_{L} by the induction hypothesis. Hence we can prove the result by showing that G is isomorphic to a split extension of the form H ⋊ G_{L}, where H is a free product of vertex groups.

We define H := ∗_{d∈D}H_{d} to be the free product of groups H_{d}, for d ∈ D, where the H_{d} are defined as follows. For each d ∈ D, we define T_{d} to be the set of all those elements t ∈ G_{L} for which there is no reduced expression starting with an element of G_{v} with v ∼ d; note that 1 ∈ T_{d}. Then we define H_{d} := ∗_{t∈T_{d}}G_{d,t} to be a free product of copies G_{d,t} of G_{d}, which are indexed by the elements of T_{d}.

For each d ∈ D, we shall now define an action of G_{L} on T_{d}. This induces an action of G_{L} on H_{d} by permuting the free factors, and this in turn induces an action of G_{L} on H, which will be used to define the semidirect product H ⋊G_{L}.

We start by defining an action of each G_{l} on T_{d}. For each element a of some G_{l} (l ∈ L), we define a map α_{d,a} : T_{d} → T_{d}, by:

tα_{d,a} := \{ \begin{matrix}ta, & ta ∈ T_{d} \\ t, & ta ∉ T_{d} \end{matrix}

Using (without modification) the argument in the proof of [12, Theorem A], we find that

(∗) if t ∈ T_{d} and 1 ≠ a ∈ G_{l}, then ta ∉ T_{d} if and only if d ∼ l and all the syllables in any reduced expression for t are from vertex groups G_{v} with v ∼ l.

Hence if a, b are non-identity elements of the same vertex group G_{l}, and t ∈ T_{d}, then either t is fixed by both α_{d,a} and α_{d,b} or t is fixed by neither of α_{d,a} and α_{d,b}. It follows from this observation that for any a, b ∈ G_{l} (including the identity) α_{d,a}α_{d,b} = α_{d,ab}. So for each vertex group G_{l} with l ∈ L, a ↦ α_{d,a} defines an action of G_{l} on T_{d}.

Exactly as in the proof of [12, Theorem A] we that, if a ∈ G_{l} and b ∈ G_{m} with l ∼ m, then α_{d,a}α_{d,b} = α_{d,b}α_{d,a}.

Hence we can extend our actions of the vertex groups of L on T_{d} to an action of G_{L} on T_{d} by defining α_{d,a_{1}...a_{k}} to be the composite α_{d,a_{1}} ⋯ α_{d,a_{k}}, where each a_{i} is in some vertex group.

We also observe that

(∗∗) if t is in the subset T_{d} ⊆ G_{L} and τ is a reduced expression for t, then every prefix of τ is also a reduced expression for an element of T_{d}, and hence 1α_{d,t} = t.

Now for t ≠ 1 we let θ_{d,t} be an isomorphism from G_{d,1} to G_{d,t}, and we identify G_{d,1} with G_{d}. Then, for each x ∈ G_{L}, we define an isomorphism β_{x} of H that permutes the free factors G_{d,t} of each of the free factors H_{d} of H by defining, for g ∈ G_{d,t}:

gβ_{x} := gθ_{d,t}^{−1}θ_{d,tα_{d,x}}.

Hence x ↦ β_{x} defines an action of G_{L} on H, and we define the associated semidirect product H ⋊ G_{L}.

Our proof is complete once we have shown that H ⋊ G_{L} is isomorphic to G.

For each d ∈ D, we define X_{d,1} := X_{d} to be our given generating set of G_{d,1} = G_{d} and, for each 1 ≠ t ∈ T_{d}, let X_{d,t} = {xθ_{d,t} | x ∈ X_{d}} be the associated generating set of G_{d,t}. Then

H ⋊ G_{L} = ⟨X_{L} ∪ ⋃_{d∈D} ⋃_{t∈T_{d}} X_{d,t} | S_{L} ∪ ⋃_{d∈D}(S_{d} ∪ R_{d})⟩
where R_{d} = ⋃_{t∈T_{d}}{g^{x} = gβ_{x} : g ∈ X_{d,t}, x ∈ X_{L}}.

For each t in ⋃_{d∈D} T_{d}, choose a word ρ(t) over X_{L} that represents t. We deduce from our observation (∗∗) above that, for g ∈ G_{d,1} and t ∈ T_{d}, we have gβ_{t} = gθ_{d,t} and hence (by the definition of the semidirect product using the action defined by β_{t}) g^{ρ(t)} = gθ_{d,t}. We use these expressions to eliminate from the presentation all the generators in the sets X_{d,t}, for each d ∈ D and 1 ≠ t ∈ T_{d}. Let g^{x} = gβ_{x} be a relator from R_{d} with g ∈ X_{d,t}. Then, if t ≠ 1, g rewrites as g_{1}^{ρ(t)}, where g_{1} = gθ_{d,t}^{−1} ∈ X_{d}, and we put g_{1} = g if t = 1. So

g^{x} rewrites (or remains when t = 1) as g_{1}^{ρ(t)x}, while gβ_{x} becomes g_{1}^{ρ(tx)} when tx ∈ T_{d} or g_{1}^{ρ(t)} when tx ∉ T_{d}. In the first case, ρ(tx) =_{G_{L}} ρ(t)x, and the relation is a consequence of relations of G_{L}, and so can be omitted.

So our presentation simplifies to

H ⋊ G_{L} = ⟨X_{L} ∪ ⋃_{d∈D} X_{d} | S_{L} ∪ ⋃_{d∈D}(S_{d} ∪ R′_{d})⟩
where R′_{d} = {g^{ρ(t)x} = g^{ρ(t)} : g ∈ X_{d}, t ∈ T_{d}, x ∈ X_{L}, tx ∉ T_{d}}.

Now we know from (∗) that whenever g, x, t satisfy the conditions in the definition of R′_{d}, then x and t must commute, and x ∈ X_{l} with l ∼ d. Since x, t ∈ G_{L}, xt = tx must be a consequence of the relations in S_{L}, and hence the corresponding relation g^{ρ(t)x} = g^{ρ(t)} can be replaced by g^{x} = g. So we can replace R′_{d} by

R′′_{d} = {g^{x} = g : g ∈ X_{d}, x ∈ X_{l}, l ∼ d}.

that is by the set of commutator relations implied by those edges of Γ between vertices in L and vertices in D, and we see that

H ⋊ G_{L} = ⟨X_{L} ∪ ⋃_{d∈D} X_{d} | S_{L} ∪ ⋃_{d∈D}(S_{d} ∪ R′′_{d})⟩,

which we recognise as a presentation for G(Γ). □

The following immediate consequence is already known [5].

Corollary 4.2. If G_{v}, v ∈ V (Γ) are right orderable groups, then for any graph Γ with finite chromatic number, the graph group G(Γ; G_{v}, v ∈ V (Γ)) is right orderable.

Proof: Let G = G(Γ). We find a series

G = G_{0} ▷ G_{1} ▷ ⋯ ▷ G_{chr(Γ)} = 1

for G, where each factor G_{i−1}/G_{i} is a free product of groups G_{v}. The result now follows from the fact that the set of right orderable groups is closed under free products and extensions. □

5. When is a graph product of groups hyperbolic?

In this section, we provide a alternative proof of the following theorem, which is the main result of [18]. Our proof makes use of the result proved in [20] that a group is (word-)hyperbolic if and only if geodesic bigons in its Cayley graph are uniformly thin, and is otherwise elementary.

Theorem 5.1. Let G = G(Γ; G_{v}, v ∈ V (Γ)) be a graph product of non-trivial groups with V (Γ) = {v_{1}, …, v_{n}} finite. Then G is hyperbolic if and only if all the following conditions hold.

(i) Each vertex group G_{v} is hyperbolic.

(ii) No two vertices of Γ with infinite vertex groups are adjacent.

(iii) If G_{v} is infinite for some vertex v, then any two vertices that are adjacent

to v are adjacent to each other. (iv) Γ has no cycle of length 4 as an induced subgraph.

Proof: For each vertex v of Γ we choose a finite symmetric generating set X_{v} of G_{v}, equal to G_{v} \ {1} if G_{v} is finite. Then we let X = ∪_{v∈V (Γ)}X_{v}. We denote by v(x) the vertex of Γ such that x ∈ X_{v(x)}.

Suppose first that G is hyperbolic. Then geodesic triangles in the Cayley graph C(G, X) are uniformly thin. It follows from Proposition 2.2 that, for any v ∈ X_{v}, words labelling geodesics within C(G_{v}, X_{v}) remain geodesic within C(G, X) and so geodesic triangles within C(G_{v}, X_{v}) are also uniformly thin. Hence each G_{v} is hyperbolic, that is Condition (i) holds. Just as in the proof in [18], we see easily that if any of the Conditions (ii)–(iv) fails, then G contains a subgroup isomorphic to ℤ^{2}, and so cannot be hyperbolic.

This completes the ‘only if’ part of the result. The ‘if’ part is a consequence of the following result together with the main result of [20]. □

Proposition 5.2. Let G = G(Γ, G_{v}, v ∈ V (Γ)) be a graph product as in Theorem 5.1 and such that the Conditions (i)–(iv) are satisfied. Then geodesic bigons in C(G, X) are uniformly thin.

Before embarking on the proof of this proposition, we prove two technical lemmas, which will be used repeatedly.

We first clarify our notation. We let n = |V (Γ)|. If α is a word over a generating set X then, for x ∈ X, x ∈ α will mean that x or x^{−1} occurs in the word α.

Lemma 5.3. Let α be a word over X. Suppose that a sequence of shuffles of |α_{2}| letters to the right hand end transforms α to α_{1}α_{2}. Then α and α_{1}α_{2} fellow travel at distance at most 2 min(|α_{1}|, |α_{2}|).

Proof: We prove by induction on |α_{2}| that α and α_{1}α_{2} fellow travel at distance at most 2|α_{2}|. If |α_{2}| = 1 then there are words α_{11}, α_{12} with α = α_{11}α_{2}α_{12} and α_{1} = α_{11}α_{12} such that α_{2} commutes with all letters in α_{12}. It is then easily verified that α = α_{11}α_{2}α_{12} and α_{1}α_{2} = α_{11}α_{12}α_{2} 2-fellow travel. For |α_{2}| > 1, first shuffle the last letter of α_{2} to the end of the word. Then the result follows from the case |α_{2}| = 1 and the inductive hypothesis. By a similar argument, α and α_{1}α_{2} fellow travel at distance at most 2|α_{1}|, and the result follows. □

Lemma 5.4. For x ∈ X_{v}, suppose that α is a geodesic word over X, but αx is non-geodesic. Then α has a suffix β, with first letter in X_{v}, and all other letters either in X_{v} or in X_{w} with w ∼ v, such that βx is non-geodesic. If G_{v} is finite, then we can choose β so that only its first letter is in X_{v}.

Proof: We choose β to be the shortest suffix of α such that βx is not geodesic, and let β = zγ with z ∈ X. Now we apply Proposition 2.2 to see that we can replace βx by a G-equivalent shorter subword by first shuffling generators from commuting vertex groups, and then replacing a word from the generators in one of the vertex groups G_{u} by a G_{u}-equivalent shorter word. If u ≠ v, then we could carry out those shuffles that do not involve x in β and shorten β, contradicting the geodesity of β. So we must have u = v, and similarly u = v(z), so v(z) = v as claimed. Furthermore, the word over X_{u} that is shortened must start with z and end with x.

Let y ∈ β with v(y) ≠ v. If v(y) ≁ v, then y would remain between z and x after the shuffles, and so it would not be possible to create a subword over X_{v} starting with z and ending with x; hence we must have v(y) ∼ v.

The final statement now follows immediately from the facts that the choice of generating set for a finite vertex group ensures that geodesic words in that group have length at most 1. □

The remainder of the section is devoted to the proof of Proposition 5.2.

We need to prove the uniform thinness of geodesic bigons. From the Condition (i) that vertex groups are hyperbolic we deduce the existence of a constant k such that for each vertex v bigons over X_{v} are uniformly k-thin.

The endpoints of geodesic bigons in C(G, X) may be at vertices or on edges of C(G, X) but it is sufficient to prove their uniform thinness in two situations: when both endpoints of the bigon lie on vertices of C(G, X), and when one endpoint lies at a vertex and the other lies at the midpoint of an edge. In other words, we have to prove that there exist constants K, K′ such that:

(a) If α_{1}, α_{2} are geodesic words over X with α_{1} =_{G} α_{2} than α_{1} and α_{2} K-fellow travel;

(b) If α_{1}, α_{2} are geodesic words over X with |α_{1}| = |α_{2}| and α_{1}x =_{G} α_{2} for some x ∈ X, then α_{1} and α_{2} K′-fellow travel.

In fact we can reduce consideration of Case (b) easily to Case (a), as follows.

Suppose that α_{1}, α_{2}, x are as in (b), and let α_{1} = ηβ, where β is the suffix of α_{1} arising from Lemma 5.4. Let v = v(x). Now suppose that shuffling all the letters of X_{v} to the right hand end transforms β to β′_{v}β_{v}, where β is a maximal suffix over X_{v}. It follows from Lemma 5.4 that β_{v}x is non-geodesic, and hence equal in G_{v} to some word γ over X_{v} with |γ| = |β_{v}|.

If |G_{v}| is finite, then |β_{v}| = |γ| = 1, and this fact together with Lemma 5.3 ensures that βx and β′_{v}γ 2-fellow travel.

If |G_{v}| is infinite then the Conditions (ii) and (iii) imply that the vertex groups G_{u} containing the letters of β′_{v} are finite and commute with each other. Then geodesity of β′_{v} implies that for any vertex u at most one letter of β′_{v} comes from X_{u}, and so |β′_{v}| ≤ n, and we can apply Lemma 5.3 to see that βx 2n-fellow travels with β′_{v}β_{v}x. Since β_{v}x and γ k-fellow travel, it follows that βx and β′_{v}γ (2n + k)-fellow travel.

In either case, we see that α_{1}x = ηβx and ηβ′_{v}γ (2n + k)-fellow travel and so, since ηβ′_{v}γ is a geodesic equal in G to α_{2}, (b) would follow from (a).

So now assume that α_{1} and α_{2} are as in (a). We shall prove by induction on |α_{1}| that they fellow travel at distance K = 4n + k. This is clear when |α_{1}| = 0, so assume that |α_{1}| > 0. Let α_{1} = η_{1}γ_{1} and α_{2} = η_{2}γ_{2}, where, for i = 1, 2, γ_{i} is the maximal suffix of α_{i} all of whose letters come from commuting vertex groups. Geodesity of α_{i} implies that γ_{i} can contain at most one letter from each finite vertex group.

Suppose first that at least one of the words γ_{i}, say γ_{1}, contains a letter from an infinite vertex group, G_{v}.

Let y be the last such letter in γ_{1}. Then y can be shuffled to the end of γ_{1} and so α_{2}y^{−1} is not geodesic. We apply Lemma 5.4 to α_{2} and y^{−1}, and let β be the resulting suffix of α_{2}. By Conditions (ii) and (iii), for each z ∈ β, either v(z) = v or G_{v(z)} is finite, and any two such vertices are adjacent in Γ. So β is a suffix of γ_{2}, and hence γ_{2} also contains a letter from X_{v}. From Condition (ii), we see that G_{v} is the unique infinite vertex group with letters in γ_{1} or γ_{2}.

[figure: η_{1}; γ_{1}; α_{1}; η_{2}; γ_{2}; α_{2}; γ′_{1,v}; γ′_{,2,v}; γ_{1,v}; γ_{2,v}; K; k; 2|V |]

Figure 1: Infinite vertex group in tails

For i = 1, 2, let γ_{i,v} and γ′_{i,v} be the words obtained from γ_{i} by deleting all letters not in X_{v}, or in X_{v}, respectively. Conditions (ii) and (iii) ensure that |γ′_{i,v}| ≤ n, and hence by Lemma 5.3 γ_{i} =_{G} γ′_{i,v}γ_{i,v}, and γ_{i} 2n-fellow travels with γ′_{i,v}γ_{i,v}.

We claim that γ_{1,v} =_{G} γ_{2,v}. For if not, assume without loss that |γ_{2,v}| ≤ |γ_{1,v}|, and let α be a geodesic word over X_{v} for γ_{2,v}γ_{1,v}^{−1}. Then η_{2}γ′_{2,v}α =_{G} η_{1}γ′_{1,v} with |η_{2}γ′_{2,v}α| > |η_{1}γ′_{1,v}| and we can apply Lemma 5.4 again to the shortest non-geodesic prefix of η_{2}γ′_{2,v}α and conclude that γ′_{2,v} contains a letter from X_{v}, a contradiction.

Hence γ_{1,v} =_{G} γ_{2,v}, and so (since α_{1} =_{G} α_{2}), we also have η_{1}γ′_{1,v} =_{G} η_{2}γ′_{2,v}. Since γ_{1,v} and γ_{2,v} are geodesic they must have the same length. We know them to be non-trivial, and hence the words η_{1}γ′_{1,v} and η_{2}γ′_{2,v} both have length less that |α_{1}|, and we can apply the induction hypothesis to see that they K-fellow travel.

The situation is displayed in Fig. 1. We deduce that α_{1} and α_{2} K-fellow travel, as claimed.

So now we may suppose that γ_{1} and γ_{2} only involve letters from finite vertex groups, and hence that |γ_{i}| ≤ n for i = 1, 2. We consider two cases.

First suppose that some vertex group G_{v} is involved in both γ_{1} and γ_{2}; that is, for some x, y ∈ G_{v}, x ∈ γ_{1}, y ∈ γ_{2}. Then by a similar argument to that in the previous paragraph, we can use Lemma 5.4 to prove that x = y and, for i = 1, 2, we have α_{i} =_{G} η_{i}γ′_{i,v}x, where γ′_{i,v} is the result of deleting the single occurrence of x from γ_{i}. By the inductive hypothesis, η_{1}γ′_{1,v} and η_{2}γ′_{2,v} K-fellow travel, and since |γ_{i}| ≤ n, we see that α_{1} and α_{2} must do too. See Fig. 2.

[figure: η_{1}; γ_{1}; α_{1}; η_{2}; γ_{2}; α_{2}; γ′_{1,v}; γ′_{,2,v}; x; K]

Figure 2: Common finite vertex group in tails

It remains to consider, and eliminate the case where no vertex group contains letters in both γ_{1} and γ_{2}. If η_{1} or η_{2} is empty, then |α_{i}| ≤ n and the result follows immediately, so let z_{1}, z_{2} be the final letters of η_{1} and η_{2}, respectively.

We shall now show that v(z_{2}) ∼ v(x) for every x ∈ γ_{1}, and v(z_{1}) ∼ v(y) for every y ∈ γ_{2}.

For suppose that x ∈ γ_{1}. By definition of γ_{1},z_{1} ∉ G_{v(x)}, so v(z_{1}) ≠ v(x). Since x can be shuffled to the end of γ_{1}, α_{2}x^{−1} is not geodesic. We apply Lemma 5.4 to α_{2} and x^{−1} and let β be the resulting suffix of α_{2}; then β starts with a letter from X_{v(x)}. Since v(x) ≠ v(y) for all y ∈ γ_{2}, γ_{2} must be a proper suffix of β, and hence, by Lemma 5.4, for each letter y ∈ γ_{2}, v(x) ∼ v(y). Hence v(x) ≠ v(z_{2}), and so z_{2}γ_{2} is also a proper suffix of β and thus v(x) ∼ v(z_{2}). Similarly, if y ∈ γ_{2} then v(y) ∼ v(z_{1}).

Note that it follows from the above that v(z_{1}) ≠ v(z_{2}), since the maximality of γ_{1} as a suffix of α_{1} of letters from commuting vertex groups ensures that we cannot have v(z_{1}) ∼ v(x) for all x ∈ γ_{1}.

Next we show that v(z_{1}) ∼ v(z_{2}). For if we multiply α_{1} by each of the letters of γ_{2}^{−1} in turn, then Lemma 5.4 ensures that each such letter shuffles past the suffix z_{1}γ_{1} of α_{1} and merges with an earlier letter in η_{1}. We end up with a geodesic word α′_{1} with α′_{1} =_{G} η_{2}, where α′_{1} still has z_{1}γ_{1} as a suffix. Then α′_{1}z_{2}^{−1} is not geodesic, and Lemma 5.4 now implies that v(z_{1}) ∼ v(z_{2}).

So now, we can choose x ∈ γ_{1} with v(z_{1}) ≁ v(x) and y ∈ γ_{2} with v(z_{2}) ≁ v(y), and then the subgraph of Γ induced on v(z_{1}), v(y), v(x), v(z_{2}) is a cycle of length 4, and Condition (iv) is violated.

Hence this final case cannot occur, and the proofs of Proposition 5.2 and Theorem 5.1 are complete.

Acknowledgments

The second author would like to thank the Mathematics Department of the University of Neuchâtel, Switzerland, for its generous hospitality and support during the period of research for this article, and the EPSRC for financial support through the grant EP/F014945/1, Quantum Computation: Foundations, Security, Cryptography and Group Theory.

References

[1] M. Bestvina and N. Brady, Morse theory and finiteness properties of groups, Invent. Math. 129 (1997) 445–470.

[2] R. Charney, An introduction to right-angled Artin groups, Geom. Dedicata 127 (2007) 141–158.

[3] R. Charney and M. Farber, Random groups arising as graph products, preprint

[4] R. Charney, K. Ruane, N. Stambaugh, A. Vijayan, the automorphism group of a graph product with no SIL, Illinois J. Math 54 (2010) 249–262.

[5] I. Chiswell, Ordering graph products of groups, preprint.

[6] A. Costa and M. Farber, Topology of random right-angled Artin groups, preprint 2009

[7] W. Dicks and M.J. Dunwoody, “Groups acting on graphs”, Cambridge studies in advanced mathematics 17, Cambridge University Press, 1989.

[8] C. Droms, Subgroups of graph groups, J. Algebra 110 (1987), 519–522.

[9] E. Green, Graph products of groups, Ph.D. thesis, University of Leeds, 1990.

[10] H. Servatius, C. Droms and B. Servatius, Surface subgroups of graph groups, Proc. Amer. Math. Soc. 106 (1989), 573–578.

[11] S. Hermiller and J. Meier, Algorithms and geometry for graph products of groups, J. Alg. 171 (1995), 230–257.

[12] S. Hermiller and Z. S̆unić, Poly-free constructions for right-angled Artin groups, J. Group Theory 10 (2007), 117–138.

[13] T. Hsu and D. Wise, On linear and residual properties of graph products, Michigan Math. J. 46 (1999) 251–259.

[14] D. Futer and A. Thomas, Surface quotients of hyperbolic buildings, Int Math Res Notices (2011), doi:10.1093/imrn/rnr028

[15] S. Kim, Hyperbolic surface subgroups of right-angled Artin groups and graph products of groups, Ph.D thesis, Yale 2007.

[16] M. Lohrey and G. Senizergues, When is a graph product of groups virtually free? Comm. Alg 35 (2007) 617–621.

[17] L. Lovasz, “Combinatorial Problems and Exercises”, North Holland, Amsterdam 1979.

[18] J. Meier, When is the graph product of hyperbolic groups hyperbolic?, Geom. Dedicata 61 (1996), 29-41.

[19] K.A. Mihailova, The occurrence problem for direct products of groups (Russian), Dokl. Akad. Nauk. SSSR 119 (1958) 1103-1105.

[20] P. Papasoglu, Strongly geodesically automatic groups are hyperbolic, Invent. Math. 121 (1995), 323-334.

[21] D. Radcliffe, Rigidity of graph products of groups, Alg. Geom. Top 3 (2003) 1979-1088.