FINITE PRESENTATIONS OF SUBGROUPS OF GRAPH GROUPS

Joshua Levy, Cameron Parker, and Leonard VanWyk

Abstract. Given a finite simple graph Γ, the graph group GΓ is the group with generators in one–to–one correspondence with the vertices of Γ and with relations in one–to–one correspondence with the edges of Γ: two generators commute if and only if their associated vertices are adjacent in Γ. Let ϕ: GΓ → ℤ be a homomorphism which maps each generator to 0 or 1. We derive an explicit presentation for ker ϕ, and give a condition, dependent on Γ and ϕ, which guarantees the finite presentation of ker ϕ.

1. Introduction. Free partially commutative (FPC) monoids were first introduced by P. Cartier and D. Foata [2] in order to study combinatorial problems involving rearrangements of words. The corresponding FPC groups are known as graph groups.

Various properties of graph groups have already been determined. The word and conjugacy problems for groups were shown to be solvable by C. Wrathall [16, 17] and independently by H. Servatius [11]. Graph groups were shown to satisfy quadratic isoperimetric and linear isodiametric inequalities by J. Meier [8]. They were shown to be biautomatic by the third author [14] and independently by S. Hermiller and J. Meier [5] using the more general notion of a “graph product” of groups. C. Droms [3, 4, 12], H. Servatius [12], B. Servatius [12] and J. Meier and the third author [9] have studied various subgroups of graph groups.

The focus of this paper is the kernels of homomorphisms from graph groups to the infinite cyclic group ⟨t⟩ in which each generator is mapped to t or 1. In [9], necessary and sufficient conditions were given for a generalization of such kernels to be finitely generated. Here, the Reidemeister–Schreier method is used to find presentations for these kernels and a sufficient condition for their finite presentation is given. Although not apparent at first, this condition on the constructibility of Γ will force the “living subgraph” to be connected and a dominating subgraph of Γ, as in [9].

The main result of this paper, the corollary to Theorem 1, is a condition based on the constructibility of the graph Γ–partitioned according to the mapping of the vertices under the homomorphism — from a single vertex using two types of operations to add edges and vertices. This constructive condition can be phrased in terms of simple homotopic expansions of the simplicial complexes spanned by the representative graphs of the graph groups, as we show in the last section.

Bestvina and Brady [1] have established the existence of groups of homological type F P_{2} which are not finitely presented. The group presentations derived here are applicable to such groups.

2. Preliminaries. Given a graph Γ, we will denote the set of vertices of Γ by V (Γ) and the set of edges, consisting of unordered pairs of elements of V (Γ), by E(Γ). A simple graph is a graph with no loops or multiple edges.

A finite simple graph Γ induces a presentation of a group GΓ:

⟨V (Γ); xy = yx for all {x, y} ∈ E(Γ)⟩.

A group G is called a graph group provided there exists some finite simple graph Γ such that G ≃ GΓ. Given any graph group, we will assume the above presentation and identify the set of generators of GΓ with the vertex set V (Γ).

Following [7], we will denote the Tietze transformations adjunction of relators, deletion of relators, adjunction of generators, and deletion of generators by (T1), (T2), (T3), and (T4), respectively. It is shown in [7] that given any two presentations of a group G, one can be obtained from the other by repeated applications of these four transformations.

Given a presentation of a group G and suitable information about a subgroup H ≤ G, the Reidemeister–Schreier method enables one to obtain a presentation for H. In [6], it is shown that if ⟨X; R⟩ is a presentation for G, π: F (X) → G is the canonical epimorphism, T is a Schreier transversal for π^{−1}(H) in F (X), and Φ: F (X) → T is the function which maps each element to its coset representative, then Y = {txΦ(tx)^{−1} : t ∈ T, x ∈ X, tx ∉ T } corresponds to a set of generators for H. Furthermore, if τ: π^{−1}(H) → F (Y) is the function in [6] which rewrites each w ∈ π^{−1}(H) in terms of the generators Y and S = {τ(trt^{−1}) : t ∈ T, r ∈ R}, then ⟨Y; S⟩ is a presentation for H.

The reader is directed to [6] or [7] for details of Tietze transformations and the Reidemeister–Schreier rewriting procedure.

3. The Subgroups. Let Γ be a finite simple graph and GΓ its corresponding graph group. Partition V (Γ) into two sets, A = {a_{0}, a_{1}, …, a_{r}} and B = {b_{1}, b_{2}, …, b_{s}} and define the homomorphism ϕ: GΓ → ⟨t⟩ by ϕ(a_{i}) = t and ϕ(b_{i}) = 1 for all indices i. Throughout this paper, we will assume A ≠ ∅. Following [9], we will refer to the vertices not mapped to 1 — in this case, the elements of A — as live, and denote the full subgraph spanned by these vertices as L = L(ϕ), the living subgraph of Γ. For a Schreier transversal for ker ϕ in GΓ, take T = {a_{0}^{n} : n ∈ ℤ} and recall that Φ: GΓ → T sends each element to its coset representative. A set of generators of ker ϕ is then {txΦ(tx)^{−1} : t ∈ T, x ∈ X, tx ∉ T }, which we denote by

\begin{aligned}α(i, n) & = a_{0}^{n}a_{i}a_{0}^{−(n+1)}, \\ β(j, n) & = a_{0}^{n}b_{j}a_{0}^{−n} \end{aligned}

for i = 1, 2, …, r, j = 1, 2, …, s, and n ∈ ℤ. We now obtain the defining set of relations for ker ϕ by rewriting the set {trt^{−1} : t ∈ T, r ∈ R}, where R = {xyx^{−1}y^{−1} : {x, y} ∈ E(Γ)}, in terms of these generators. For convenience, we define α(0, n) = 1 for all n ∈ ℤ. Straightforward computations show that each {a_{i}, a_{j}} ∈ E(Γ) yields the family of relations

α(i, n)α(j, n + 1)α(i, n + 1)^{−1}α(j, n)^{−1} = 1, n ∈ ℤ,

while each {a_{i}, b_{j}} ∈ E(Γ) yields the family

α(i, n)β(j, n + 1)α(i, n)^{−1}β(j, n)^{−1} = 1, n ∈ ℤ,

and each {b_{i}, b_{j}} ∈ E(Γ) yields the family

β(i, n)β(j, n)β(i, n)^{−1}β(j, n)^{−1} = 1, n ∈ ℤ.

Thus, ker ϕ can be presented using the above generators together with the relations

\{ \begin{matrix}α(i, n)α(j, n + 1) = α(j, n)α(i, n + 1), & for \{a_{i}, a_{j}\} ∈ E(Γ), n ∈ ℤ, \\ α(i, n)β(j, n + 1) = β(j, n)α(i, n), & for \{a_{i}, b_{j}\} ∈ E(Γ), n ∈ ℤ, \\ β(i, n)β(j, n) = β(j, n)β(i, n), & for \{b_{i}, b_{j}\} ∈ E(Γ), n ∈ ℤ. \end{matrix} (1)

Note that every element of V (Γ) − {a_{0}} corresponds to a countable family of generators and every element of E(Γ) corresponds to a countable family of relations in this presentation for ker ϕ.

4. Some Lemmas. We are now ready to prove the following lemmas, which will aid us in our goal of finding sufficient conditions for the finite presentation of ker ϕ.

\underline{Lemma 1}. Let Γ be a finite simple graph and let V (Γ) be partitioned into two sets A and B. Define the homomorphism ϕ: GΓ → ⟨t⟩ so that ϕ(x) = t for every x ∈ A and ϕ(x) = 1 for every x ∈ B. Let Γ̂ be the graph constructed from Γ by adding a vertex c and an edge {c, a} for some a ∈ A. If ϕ̂: GΓ̂ → ⟨t⟩ is a homomorphism that agrees with ϕ on V (Γ) and maps c to either t or 1, then there exist presentations for ker ϕ and ker ϕ̂ of the form ⟨X; R⟩ and ⟨X ∪ {γ}; R⟩, respectively, for some generating symbol γ independent of X.

\underline{Proof}. We will use the presentation for ker ϕ calculated in the previous section and denote it by ⟨X; R⟩. The vertices of Γ̂ may be partitioned into two subsets, Â and B̂, such that ϕ̂ maps every element of Â to t and every element of B̂ to 1. Since exactly one vertex and one edge have been added to Γ, ker ϕ̂ may be presented using the generators X and relators R together with one additional family of generators and one additional family of relations. We denote the family of generators corresponding to the vertex a by α_{n} and the family of generators corresponding to c by γ_{n} for n ∈ ℤ.

We first consider the case where c ∈ Â. With our new notation, the first family in (1) becomes

α_{n}γ_{n+1} = γ_{n}α_{n+1}, n ∈ ℤ.  (2)

Straightforward induction shows (2) is equivalent to

γ_{n} = \{ \begin{matrix}[α_{0}α_{1} ⋯ α_{n−1}]^{−1}γ_{0}[α_{1}α_{2} ⋯ α_{n}], & n > 0, \\ [α_{n}α_{n+1} ⋯ α_{−1}]γ_{0}[α_{n+1}α_{n+2} ⋯ α_{0}]^{−1}, & n < 0. \end{matrix}  (3)

By the Tietze transformations (T1) and (T2), the family of relations (2) can be replaced by the family (3). Since for all nonzero integers n, γ_{n} has been written in terms of γ_{0} and elements of X, by (T4) we can eliminate every relation in the family (3) and every generator γ_{n} for n ≠ 0. The generators γ_{n} for n ≠ 0 do not appear in any of the relations in R, so ⟨X ∪ {γ_{0}}; R⟩ is a presentation for ker ϕ̂.

Next, we consider the case where c ∈ B̂. The second family of relations in (1) gives

α_{n}γ_{n+1} = γ_{n}α_{n}, n ∈ ℤ.  (4)

Proceeding as in the first case, we replace (4) by

γ_{n} = \{ \begin{matrix}[α_{0}α_{1} ⋯ α_{n−1}]^{−1}γ_{0}[α_{0}α_{1} ⋯ α_{n−1}], & n > 0, \\ [α_{n}α_{n+1} ⋯ α_{−1}]γ_{0}[α_{n}α_{n+1} ⋯ α_{−1}]^{−1}, & n < 0. \end{matrix}  (5)

and eliminate every relation in (5) and all the generators γ_{n} for n ≠ 0. So we again see that ⟨X ∪ {γ_{0}}; R⟩ is a presentation for ker ϕ̂, concluding our proof.

\underline{Lemma 2}. Let Γ be a finite simple graph and let V (Γ) be partitioned into two sets A and B. Define the homomorphism ϕ: GΓ → ⟨t⟩ so that ϕ(x) = t for every x ∈ A and ϕ(x) = 1 for every x ∈ B. Let Γ̂ be the graph constructed from Γ by adding an edge that joins two vertices that are both adjacent to the same vertex a ∈ A. If ϕ̂: GΓ̂ → ⟨t⟩ is the homomorphism that agrees with ϕ on V (Γ), then there exists presentations for ker ϕ and ker ϕ̂ of the form ⟨X; R⟩ and ⟨X; R ∪ {r}⟩, respectively, for some relation r not derivable from R.

\underline{Proof}. We will use the same presentation ⟨X; R⟩ for ker ϕ as in Lemma 1. There are three possible cases for the two vertices joined by the new edge: either both are elements of A, one is in A and one is in B, or both are elements of B.

For the first case, suppose these two vertices, say a′ and a′′, are both contained in A. Using our established generators and relations, we see the vertices a, a′, and a′′ are associated with three families of generators, which we will call α_{n}, α′_{n}, and α′′_{n}, respectively, where n ∈ ℤ, and that the edges {a, a′} and {a, a′′} correspond to the two sets of relations contained in R,

α_{n}α′_{n+1} = α′_{n}α_{n+1}, n ∈ ℤ,  (6)
α_{n}α′′_{n+1} = α′′_{n}α_{n+1}, n ∈ ℤ.  (7)

The added edge {a′, a′′} introduces the new relations

α′_{n}α′′_{n+1} = α′′_{n}α′_{n+1}, n ∈ ℤ.  (8)

However, we can use only the relation for n = 0,

α′_{0}α′′_{1} = α′′_{0}α′_{1},  (9)

together with the families (6) and (7) to derive the entire family (8) as follows. We start with (9) and induct on n in both the positive and the negative directions. Suppose

α′_{k}α′′_{k+1} = α′′_{k}α′_{k+1}  (10)

for a particular k ∈ ℤ. Rewriting every symbol in (10) using the two relations

\begin{aligned}α′_{k} & = α_{k}α′_{k+1}α_{k+1}^{−1}, \\ α′′_{k} & = α_{k}α′′_{k+1}α_{k+1}^{−1}, \end{aligned}

from (6) and (7) yields

α′_{k+1}α′′_{k+2} = α′′_{k+1}α′_{k+2},

completing our induction in the positive direction. For the negative direction, we again use two substitutions derived from (6) and (7) to rewrite (10) as

α′_{k−1}α′′_{k} = α′′_{k−1}α′_{k}.

We have now shown that (8) can be derived from (9) and relations in R. Hence, (T2) can be used to delete all relations in (8) except the single relation (9), allowing ker ϕ̂ to be presented by ⟨X; R ∪ {α′_{0}α′′_{1} = α′′_{0}α′_{1}}⟩, as promised.

For the second case, we suppose one vertex a′ is contained in A and one vertex b′ is in B and denote their corresponding generators by α′_{n} and β′_{n} for n ∈ ℤ. The added edge {a′, b′} introduces the relations

α′_{n}β′_{n+1} = β′_{n}α′_{n}, n ∈ ℤ.  (11)

Again, the relation for n = 0,

α′_{0}β′_{1} = β′_{0}α′_{0},  (12)

and the relations of the edges {a, b′} and {a, a′} can be used to derive each of the relations of (11). The same induction technique is used, with one pair of substitutions to increment the indices on the generators and one pair to decrement them. Hence, (T2) can be used to delete all the new relations except for (12), giving the presentation ⟨X; R ∪ {α′_{0}β′_{1} = β′_{0}α′_{0}}⟩.

Finally, we consider the case where both vertices b′ and b′′ are elements of B. Once again, we wish to eliminate the family of relations in the sets of generators β′_{n} and β′′_{n} introduced by the new edge {b′, b′′},

β′_{n}β′′_{n} = β′′_{n}β′_{n}, n ∈ ℤ.  (13)

The special case β′_{0}β′′_{0} = β′′_{0}β′_{0}, together with the families of relations corresponding to the edges {a, b′} and {a, b′′} yield (13) by an induction similar to the previous two cases, so a single relation can take the place of the infinite set, giving ker ϕ̂ the presentation ⟨X; R ∪ {β′_{0}β′′_{0} = β′′_{0}β′_{0}}⟩.

Thus, we have shown that in each case there exists a relation r such that ker ϕ̂ = ⟨X; R∪{r}⟩. We also know that r is not derivable from R, for if it were, we would have ker ϕ = ker ϕ̂. But the word xyx^{−1}y^{−1} represents the trivial element in ker ϕ̂ but not in ker ϕ, where x, y ∈ V (Γ) are the two vertices joined by the new edge.

\underline{Example}. Consider the three graphs

where ϕ: GΓ → ⟨t⟩ satisfies ϕ(a) = ϕ(a′) = ϕ(a′′) = t and ϕ(b) = 1. Let ϕ_{1} and ϕ_{2} be the homomorphisms corresponding to Γ_{1} and Γ_{2}, respectively, with the same vertex mappings as ϕ. Repeated use of Lemma 1 shows ker ϕ is the free group on three letters. However, ker ϕ_{1} is not finitely presented [13]. On the other hand, since Γ_{2} can be constructed from Γ by two applications of Lemma 2 (first adding the edge {a, a′′}, and then adding the edge {a′′, b} ), it follows from Lemma 2 that ker ϕ_{2} admits a presentation with three generators and two relations.

\underline{Lemma 3}. Let G, G_{1}, and G_{2} be groups with presentations ⟨X; R⟩, ⟨X ∪ {γ}; R⟩, and ⟨X; R∪{r}⟩, respectively, for a generating symbol γ independent of X and a relation r not derivable from R. If G admits a second presentation ⟨X′; R′⟩, then G_{1} ≃ ⟨X′ ∪{γ′}; R′⟩ and G_{2} ≃ ⟨X′; R′ ∪{r′}⟩, where γ′ is a generating symbol independent of X′ and r′ is not derivable from R′.

\underline{Proof}. Since none of the relations of R involve γ,

G_{1} ≃ ⟨X ∪ {γ}; R⟩ ≃ ⟨X; R⟩ ∗ ⟨γ⟩ ≃ ⟨X′; R′⟩ ∗ ⟨γ⟩ ≃ ⟨X′ ∪ {γ′}; R′⟩.

For the third group, G_{2} ≃ G/N, where N is the normal subgroup of G generated by the group element g corresponding to r [7]. Thus, if π: F (X) → G_{2} and π′: F (X′) → G_{2} are the canonical epimorphisms, G_{2} ≃ G/N ≃ ⟨X′; R′ ∪ {r′}⟩, where r′ satisfies g = π(r) = π′(r′). Since r is not derivable from R by hypothesis, r′ is not derivable from R′.

5. A Condition for Finite Presentation. The first two lemmas provide a method for adding vertices and edges to our graph while allowing us to keep track of the generators and relations of the kernel. Specifically, we have found two operations which may be used to modify the graph and homomorphism so that either one generator or one relation is added to a certain presentation for the kernel. With our first theorem, we use Lemma 3 to generalize this method, applying it to any presentation of the kernel.

\underline{Theorem 1}. Let Γ be a finite simple graph and let V (Γ) be partitioned into two sets A and B. Define the homomorphism ϕ: GΓ → ⟨t⟩ so ϕ(x) = t for every x ∈ A and ϕ(x) = 1 for every x ∈ B. Construct a graph Γ̂ from Γ by either

(i) adding a vertex c and an edge {c, a}, where a ∈ A; or (ii) adding an edge joining two vertices which are both adjacent to the same vertex

a ∈ A, and let ϕ̂: GΓ̂ → ⟨t⟩ be a homomorphism that maps every element of V (Γ̂) to either t or 1 and agrees with ϕ on V (Γ). Suppose ⟨X′; R′⟩ is any presentation for ker ϕ. Then in the first case, ker ϕ̂ admits the presentation ⟨X′ ∪ {γ}; R′⟩, for some generating symbol γ independent of X′, and in the second case, ker ϕ̂ admits the presentation ⟨X′; R′ ∪ {r′}⟩, where r′ is a relation not derivable from R′.

\underline{Proof}. In construction (i) of Γ̂, Lemma 1 shows there exists a presentation ⟨X ∪ {γ}; R⟩ for ker ϕ̂, where ⟨X; R⟩ is a presentation for ker ϕ and γ is independent of X. Since ⟨X; R⟩ and ⟨X′; R′⟩ both present the same group, Lemma 3 shows that ⟨X′ ∪ {γ′}; R′⟩ presents ker ϕ̂. For construction (ii), by Lemma 2 there exist presentations for ker ϕ and ker ϕ̂ of the form ⟨X; R⟩ and ⟨X; R ∪ {r}⟩, respectively, where r is not derivable from R. From Lemma 3, we see ker ϕ̂ admits the presentation ⟨X′; R′ ∪ {r′}⟩, where r′ is not derivable from R′.

Henceforth, we will refer to the above constructions as operations of type (i) and (ii).

\underline{Corollary}. Let Γ be a finite simple graph and let V (Γ) be partitioned into two sets A and B. Define the homomorphism ϕ: GΓ → ⟨t⟩ so that ϕ(x) = t for every x ∈ A and ϕ(x) = 1 for every x ∈ B. Then ker ϕ admits a finite presentation if Γ can be constructed from a single vertex in A by applying a sequence of type (i) and type (ii) operations. Moreover, one such finite presentation of ker ϕ is ⟨X_{f}; R_{f}⟩, where |X_{f}| = |V (Γ)| − 1, |R_{f}| = |E(Γ)| − |V (Γ)| + 1. In particular, if Γ is a tree and can be so constructed, then ker ϕ is free on |V (Γ)| − 1 letters.

\underline{Proof}. We induct on the number of steps taken to create the graph. The base case is where Γ consists of the graph on one vertex a_{0} ∈ A so that V (Γ) = 1, E(Γ) = 0, and ker ϕ = {1}.

Proceeding inductively, assume Γ is a partitioned graph constructed in the above manner and ϕ is its corresponding homomorphism, and assume there exists a presentation ⟨X_{f}; R_{f}⟩ for ker ϕ such that |X_{f}| = |V (Γ)| − 1 and |R_{f}| = |E(Γ)| − |V (Γ)| + 1.

For the type (i) operation, |V (Γ̂)| = |V (Γ)| + 1 and |E(Γ̂)| = |E(Γ)| + 1. From Theorem 1, we know there exists a generating symbol γ independent of X_{f} such that ⟨X_{f} ∪ {γ}; R_{f}⟩ is a presentation for ker ϕ̂, which meets our requirements, since |X_{f} ∪ {γ}| = |V (Γ̂)| − 1 and |R_{f}| = |E(Γ̂)| − |V (Γ̂)| + 1.

For the type (ii) operations, |V (Γ̂)| = |V (Γ)| and |E(Γ̂)| = |E(Γ)| + 1. Again from Theorem 1, we know there exists a relation r′ not derivable from R_{f} such that ⟨X; R_{f} ∪{r′}⟩ presents ker ϕ̂. This presentation again meets our requirements, since |X_{f}| = |V (Γ̂)| − 1 and |R_{f} ∪ {r′}| = |E(Γ̂)| − |V (Γ̂)| + 1. So by induction, the statement holds for all graphs that can be built by this method.

The last assertion of the corollary is immediate, since |V (T)| = |E(T)| + 1 for a tree T.

6. Connections. Whitehead [15] defines elementary deformations of simplicial complexes so that if K_{0} and K_{1} are simplicial complexes with K_{1} = K_{0} + aC, where C is a closed simplex such that aĊ ⊆ K_{0} and C ⊈ K_{0}, then the transformation K_{0} → K_{1} is called an elementary expansion of order dim(aC), and the transformation K_{1} → K_{0} is called an elementary contraction of order dim(aC).

If instead of restricting ourselves to the graph Γ, we consider the 2–skeleton Γ^{(2)} of the simplicial complex spanned by Γ, then an operation of type (i) corresponds to an elementary simplicial expansion K_{0} → K_{0} + ax of order 1, where a ∈ A and x ∈ V (Γ), while an operation of type (ii) above corresponds to an elementary simplicial expansion K_{0} → K_{0} + ae of order 2, where a ∈ A and e ∈ E(Γ). Thus, we are building a subcomplex of Γ^{(2)}, starting with a single live vertex of A and performing elementary simplicial expansions of orders 1 and 2 in which the cone vertex a in each expansion is live.

By [15], if Γ can be constructed from a single live vertex a_{0} ∈ A, by a sequence of operations of types (i) and (ii), then Γ can be constructed as {a_{0}}⟶^{(i)}T ⟶^{(ii)}Γ, where ⟶^{(i)} and ⟶^{(ii)} denote a sequence of operations of type (i) and type (ii), respectively, and T is a tree. Since operations of type (ii) add no new vertices, T is a spanning tree for Γ. Notice the elementary expansions of orders 1 and 2 corresponding to {a_{0}}⟶^{(i)}T ⟶^{(ii)}Γ yield a contractible subcomplex of Γ^{(2)} which contains all the edges of Γ.

The definition of a type (i) operation implies that each vertex b ∈ B has degree 1 in T. Also, for each b ∈ B, there exists a vertex a ∈ A which is adjacent to b in T. Finally, if we let T_{A} ⊆ T be the subtree spanned by the vertex set A, then T_{A} is connected by construction since there exists a (unique) path from any vertex a ∈ A to a_{0} containing only live vertices.

For our next lemma, recall that a subgraph C of a graph Γ is dominating if every vertex in V (Γ) − V (C) is adjacent to a vertex in C.

\underline{Lemma 4}. Let Γ be a finite simple graph with V (Γ) partitioned into two sets A and B, and let L be the full subgraph spanned by A. Then L is a connected and dominating subgraph of Γ if and only if for all a ∈ A, there exists a spanning tree T of Γ such that {a}⟶^{(i)}T.

\underline{Proof}. (⇒) Let a ∈ A and let T_{A} be a connected spanning tree for L. Since T_{A} consists of live vertices, there exists a sequence of type (i) operations {a}⟶^{(i)}T_{A}.

Since L is dominating, there exists a function λ: B → A that maps each vertex b ∈ B to a vertex in A which is adjacent to b in Γ. Thus, λ can be used to define a sequence of type (i) operations T_{A}⟶^{(i)}T, where T is a spanning tree for Γ.

(⇐) By the previous paragraphs, the live subtree T_{A} is a connected and dominating subgraph of the spanning tree T of Γ. Because T_{A} is a spanning tree for L, we know L is a connected and dominating subgraph of Γ.

Theorem 6.1 of [9] states that any nontrivial homomorphism χ: GΓ → ⟨t⟩ has a finitely generated kernel if and only if L(χ) – the full subgraph spanned by {v ∈ V (Γ) : χ(v) ≠ 1} — is a connected and dominating subgraph of Γ. This implies our next result.

\underline{Theorem 2}. Let Γ be a finite simple graph and let V (Γ) be partitioned into two sets A and B. Define the homomorphism ϕ: GΓ → ⟨t⟩ so ϕ(x) = t for every x ∈ A and ϕ(x) = 1 for every x ∈ B. Then ker ϕ is finitely generated if and only if for all a ∈ A, there exists a spanning tree T of Γ such that {a}⟶^{(i)}T.

Hence, the finite generation of ker ϕ is encoded in the operations of type (i) from any live vertex of Γ to a spanning tree for Γ. However, the operations of type (i) alone do not provide enough information to determine the finite presentation of ker ϕ, as Example 1 shows. It follows that the finite presentation is encoded in the expansions of type (ii) in the sequence {a_{0}}⟶^{(i)}T ⟶^{(ii)}Γ.

In [3], Droms proved a graph group GΓ is coherent — that is, each of its finitely generated subgroups is finitely presented — if and only if each circuit of Γ of length greater than three has a chord. Hence, if Γ is chordal and for all a ∈ A, there exists a spanning tree T of Γ such that {a}⟶^{(i)}T, then ker ϕ is finitely presented.

\underline{Proposition}. Let Γ be a finite simple graph with V (Γ) partitioned into two sets A and B and suppose for all a ∈ A there exists a spanning tree T of Γ such that {a}⟶^{(i)}T. Then if Γ is chordal, it can be constructed from any live vertex a ∈ A by a sequence of type (i) and type (ii) operations.

\underline{Proof}. Let a ∈ A and T be the corresponding spanning tree. Let Γ′ be a graph with the maximal number of edges which contains T and that can be constructed by a sequence of type (i) and type (ii) operations from {a}. Since Γ′ contains T, V (Γ′) = V (Γ).

Suppose Γ′ ≠ Γ. For each e = {x, y} ∈ E(Γ) − E(Γ′), define l(e) to be the length of a minimal circuit in the graph Γ′ ∪ {e} consisting of live vertices, with the possible exception of x and y. Such a circuit exists since Γ′ contains T. Let e_{0} ∈ E(Γ) − E(Γ′) be minimal with respect to this length.

Since e_{0} ∉ E(Γ′), we must have l(e_{0}) > 3, since otherwise e_{0} could be constructed from Γ′ by a type (ii) operation, contradicting the maximality of Γ′. Let c be any minimal length circuit for e_{0} as above. Then by hypothesis, c has a chord e′, and e′ divides c into two circuits, each of length less than c. By minimality of c, e′ ∉ E(Γ′). But then l(e′) < l(e_{0}), contradicting the minimality of l(e_{0}). Thus Γ′ = Γ and hence, Γ can be constructed by a sequence of type (i) and type (ii) operations from {a}.

The converse of this proposition is false; the construction of Corollary 1 gives finitely presented subgroups of graph groups which are not based on chordal graphs, such as the case where Γ is the cone on a square and the cone vertex is an element of A.

This work is the result of NSF grant number DMS 9322328, an NSF–funded Research Experiences for Undergraduates project at Hope College of the first two authors under the direction of the third.

\underline{References}

1. M. Bestvina and N. Brady, “Morse Theory and Finiteness Properties of Groups,” Invent. Math., (to appear).

2. P. Cartier and D. Foata, Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Math., Vol. 85, Springer–Verlag, Berlin and New York, 1969.

3. C. Droms, “Graph Groups, Coherence, and Three–Manifolds,” J. Algebra, 106 (1987), 484–489.

4. C. Droms, “Subgroups of Graph Groups,” J. Algebra, 110 (1987), 518–522.

5. S. Hermiller and J. Meier, “Algorithms and Geometry for Graph Products of Groups,” J. Algebra, 171 (1995), 230–257.

6. R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, 89, Springer–Verlag, Berlin and New York, 1977.

7. W. Magnus, A. Karrass, and D. Solitar, Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, 2nd rev. ed., Dover, New York, 1976.

8. J. Meier, “The Topology of Graph Products of Groups,” Proc. Edin. Math. Soc., 37 (1994), 539–544.

9. J. Meier and L. VanWyk, “Bieri–Neumann–Strebel Invariants for Graph Groups,” Proc. London Math. Soc., 71 (1995), 263–280.

10. J. Meier and L. VanWyk, On the Higher ∑–Invariants of Graph Groups, preprint, 1996.

11. H. Servatius, “Automorphisms of Graph Groups,” J. Algebra, 126 (1989), 34– 60.

12. H. Servatius, C. Droms, and B. Servatius, “Surface Subgroups of Graph Groups,” Proc. Am. Math. Soc., 106 (1989), 573–578.

13. J. R. Stalling, “A Finitely Presented Group Whose Three–Dimensional Integral Homology is Not Finitely Generated,” Am. J. of Math., 85 (1963), 541–543.

14. L. VanWyk, “Graph Groups are Biautomatic,” J. Pure and Applied Algebra, 94 (1994), 341–352.

15. J. H. C. Whitehead, “Simplicial Spaces, Nucleii, and m–Groups,” Proc. London Math. Soc., 45 (1939), 243–327.

16. C. Wrathall, The Word Problem for Free Partially Commutative Groups, NSF grant number CCR–8706976, 1987.

17. C. Wrathall, The Conjugacy Problem for Free Partially Commutative Groups Can be Solved in Linear Time, NSF grant number CCR–8706976, 1988.

Joshua Levy Department of Mathematics Hope College Holland, MI 49422 email: levy@cs.hope.edu

Cameron Parker Department of Mathematics University of Redlands Redlands, CA 92373 email: 97cparke@ultrix.uor.edu

Leonard VanWyk Department of Mathematics Lafayette College Easton, PA 18042 email: vanwyk@cs.lafayette.edu