NOTES ON THE STRUCTURE OF PΣ_{n}

Erin Corman, Rebecca Dolphin, and Leonard VanWyk

Abstract. The pure symmetric automorphism group, PΣ_{n}, consists of those automorphisms of the free group on n generators that take each standard generator to a conjugate of itself. We give presentations for kernels of homomorphisms PΣ_{n} → ℤ where each standard generator is sent to either 0 or 1, and provide explicit generators (as words in the standard generators) when those kernels are finitely generated. In addition, we provide recursive constructions of the defining graphs of the graph groups associated with PΣ_{n}.

1. Introduction. The pure symmetric automorphism group, PΣ_{n}, consists of those automorphisms of the free group on n generators, F_{n}, that take each standard generator to a conjugate of itself. Such automorphisms have also been referred to as basis-conjugating automorphisms of free groups.

Just as each braid group, B_{n}, can be interpreted as a group of motions of n distinct points in the plane, so PΣ_{n} can be interpreted as a group of motions of n unknotted, unlinked circles in ℝ^{3}. The fundamental group of the link complement of this trivial link is F_{n}, with each of the n standard generators corresponding to a meridian of one of the circles. PΣ_{n} is then realized as the group of motions generated by those motions for which the ith circle is passed through the jth circle, with all others remaining fixed. See Goldsmith [7] or Brownstein and Lee [4] for details.

McCool [13], using generators described by Humphries [9], derived a finite presentation for PΣ_{n}. Gutiérrez and Krstić [8] have discovered normal forms for the more general symmetric automorphism group of F_{n} (those that send each standard generator to a conjugate of itself or another standard generator) that form a regular language. Orlandi-Korner [16] has computed the first Σ-invariant for PΣ_{n}. Brady et al. [3] have shown that the PΣ_{n} are duality groups.

Since two of the three types of relators in McCool’s presentation for PΣ_{n} are commutators of his generators, there is an associated graph group or right-angled Artin group associated with each PΣ_{n}; PΣ_{n} is the quotient of this graph group by the normal subgroup generated by the other relators. Graph groups have been studied extensively, and have proven to be an interesting yet accessible class of groups. See [2, 5, 6, 10, 14, 15, and 17] for some results about graph groups.

The focus of this paper is threefold. First, we derive a presentation for kernels of homomorphisms θ: PΣ_{n} → ⟨t⟩ (where ⟨t⟩ is the infinite cyclic group) in which each generator is mapped to t or 1. (Kernels from graph groups to < t > provided the first example of groups that satisfy homological finiteness condition FP_{2} but which were not finitely presented [2].) These kernels necessarily contain the commutator subgroup of PΣ_{n}. Secondly, we study the structure of the underlying graph of the graph group associated with PΣ_{n}. Lastly, we provide and explicit finite generating set for those homomorphisms θ for which ker θ is finitely generated.

This work is the result of an NSF-funded Research Experiences for Undergraduates project at James Madison University of the first two authors under the direction of the third. We thank John Meier for suggesting this project and Joshua Levy for his help in improving the presentation of this material.

2. Preliminaries. Let F_{n} be the free group with basis X = {x_{1}, x_{2}, …, x_{n}}. The pure symmetric automorphism group of F_{n}, denoted by PΣ_{n}, is the subgroup of Aut(F_{n}) that sends each x_{i} to a conjugate of itself.

In [13], McCool provides a finite presentation of PΣ_{n}. The generators are the maps ϕ_{i,j}: F_{n} → F_{n} (i ≠ j) given by

ϕ_{i,j}(x_{k}) = \{ \begin{matrix}x_{j}^{−1}x_{i}x_{j} & if k = i \\ x_{k} & otherwise \end{matrix}

and the relations fall into three categories:

\{ \begin{matrix}[ϕ_{i,j}, ϕ_{k,j}] = 1 & for all distinct i, j and k \\ [ϕ_{i,j}, ϕ_{k,l}] = 1 & for all distinct i, j, k and l \\ [ϕ_{i,j}, ϕ_{i,k}ϕ_{j,k}] = 1 & for all distinct i, j and k. \end{matrix}  (1)

We call the first class of relators Type C; these are relations in which automorphisms with common conjugates commute. The second class is Type D; these are relations in which automorphisms with disjoint subscripts commute. The third class is Type E; these can be thought of as edge relations, where a single vertex commutes with a pair of common conjugates (as defined by the equation above) that correspond to an edge in the underlying graph group defined below.

Since the relators of Types C and D are commutators of generators, the group formed from the presentation above minus the relators of Type E is a graph group or right-angled Artin group.

Following [12], 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 [12] 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 [11] 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 [11] 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 [11] or [12] for details of Tietze transformations and the Reidemeister-Schreier rewriting procedure.

3. A Presentation for the Subgroups. Let PΣ_{n} have the presentation given in Section 2, with generating set X = {ϕ_{i,j} | 1 ≤ i, j ≤ n, i ≠ j} and relators given in Equation 1 of Types C, D, and E. Let θ: PΣ_{n} → ⟨t⟩ be a homomorphism that maps each generator ϕ_{i,j} to either t or 1. We seek a presentation for ker θ.

Following [1] and [10], we will refer to those generators mapped to t as “live” and those mapped to 1 as “dead.”

Since there will always be at least one live generator, and the presentation of PΣ_{n} is symmetric, we will always assumeϕ_{1,2} is live.

For a Schreier transversal for π^{−1}(ker θ) in F (X), take T = {ϕ_{1,2}^{m} | m ∈ ℤ} and recall that Φ: F (X) → T sends each element to its coset representative. A set of generators for ker θ is then {txΦ(tx)^{−1} | t ∈ T, x ∈ X, tx ∉ T }. Just as in [1] and [10], a straightforward calculation yields the following families of generators:

\{ \begin{matrix}λ(i, j, m) = ϕ_{1,2}^{m} ϕ_{i,j} ϕ_{1,2}^{−(m+1)} & for each live ϕ_{i,j} and for each m ∈ ℤ \\ δ(i, j, m) = ϕ_{1,2}^{m} ϕ_{i,j} ϕ_{1,2}^{−m} & for each dead ϕ_{i,j} and for each m ∈ ℤ. \end{matrix}

Notice we use λ(i, j, m) for each family of generators corresponding to a live automorphism and δ(i, j, m) for those corresponding to a dead automorphism. Also notice that λ(1, 2, m) = 1 for all m ∈ ℤ.

We now obtain the relations for ker θ by rewriting the set {trt^{−1} | t ∈ T, r ∈ R} in terms of these generators,where R consists of the relators in Equation 1. For the following, we will denote the live generators of PΣ_{n} by l_{i,j} and the dead generators of PΣ_{n} by d_{i,j}, i.e.,

ϕ_{i,j} = \{ \begin{matrix}l_{i,j} & if θ(ϕ_{i,j}) = t \\ d_{i,j} & if θ(ϕ_{i,j}) = 1. \end{matrix}

Once again, straightforward calculations yield the following relations for ker θ; each holds for all m ∈ ℤ:

(1) Relations derived from Type C relations of PΣ_{n}. (a) From each relation of the form [l_{i,j}, l_{k,j}] = 1:

λ(i, j, m)λ(k, j, m + 1)λ(i, j, m + 1)^{−1}λ(k, j, m)^{−1} = 1

(b) From each relation of the form [l_{i,j}, d_{k,j}] = 1:

λ(i, j, m)δ(k, j, m + 1)λ(i, j, m)^{−1}δ(k, j, m)^{−1} = 1

(c) From each relation of the form [d_{i,j}, d_{k,j}] = 1:

δ(i, j, m)δ(k, j, m)δ(i, j, m)^{−1}δ(k, j, m)^{−1} = 1

(2) Relations derived from Type D relations of PΣ_{n}. (a) From each relation of the form [l_{i,j}, l_{k,l}] = 1:

λ(i, j, m)λ(k, l, m + 1)λ(i, j, m + 1)^{−1}λ(k, l, m)^{−1} = 1

(b) From each relation of the form [l_{i,j}, d_{k,l}] = 1:

λ(i, j, m)δ(k, l, m + 1)λ(i, j, m)^{−1}δ(k, l, m)^{−1} = 1

(c) From each relation of the form [d_{i,j}, d_{k,l}] = 1:

δ(i, j, m)δ(k, l, m)δ(i, j, m)^{−1}δ(k, l, m)^{−1} = 1

(3) Relations derived from Type E relations of PΣ_{n}. (a) From each relation of the form [l_{i,j}, l_{i,k} l_{j,k}] = 1:

λ(i, j, m)λ(i, k, m+1)λ(j, k, m+2)λ(i, j, m+2)^{−1}λ(j, k, m+1)^{−1}λ(i, k, m)^{−1} = 1 (b) From each relation of the form [l_{i,j}, l_{i,k} d_{j,k}] = 1: λ(i, j, m)λ(i, k, m+1)δ(j, k, m+2)λ(i, j, m+1)^{−1}δ(j, k, m+1)^{−1}λ(i, k, m)^{−1} = 1 (c) From each relation of the form [l_{i,j}, d_{i,k} l_{j,k}] = 1:

λ(i, j, m)δ(i, k, m)λ(j, k, m + 1)λ(i, j, m + 1)^{−1}λ(j, k, m)^{−1}δ(i, k, m)^{−1} = 1 (d) From each relation of the form [l_{i,j}, d_{i,k} d_{j,k}] = 1:

λ(i, j, m)δ(i, k, m + 1)δ(j, k, m + 1)λ(i, j, m)^{−1}δ(j, k, m)^{−1}δ(i, k, m)^{−1} = 1 (e) From each relation of the form [d_{i,j}, l_{i,k} l_{j,k}] = 1: δ(i, j, m)λ(i, k, m)λ(j, k, m + 1)δ(i, j, m + 2)^{−1}λ(j, k, m + 1)^{−1}λ(i, k, m)^{−1} = 1 (f) From each relation of the form [d_{i,j}, l_{i,k} d_{j,k}] = 1: δ(i, j, m)λ(i, k, m)δ(j, k, m + 1)δ(i, j, m + 1)^{−1}δ(j, k, m + 1)^{−1}λ(i, k, m)^{−1} = 1 (g) From each relation of the form [d_{i,j}, d_{i,k} l_{j,k}] = 1:

δ(i, j, m)δ(i, k, m)λ(j, k, m)δ(i, j, m + 1)^{−1}λ(j, k, m)^{−1}δ(i, k, m)^{−1} = 1 (h) From each relation of the form [d_{i,j}, d_{i,k} d_{j,k}] = 1:

δ(i, j, m)δ(i, k, m)δ(j, k, m)δ(i, j, m)^{−1}δ(j, k, m)^{−1}δ(i, k, m)^{−1} = 1 Note that every generator ϕ_{i,j} of PΣ_{n} (except for ϕ_{1,2}) corresponds to a count-

able family of generators for ker θ, and every relation of PΣ_{n} corresponds to a countable family of relations for ker θ.

4. The Structure of the Underlying Graphs of PΣ_{n}. Recall [13] that PΣ_{n} admits a finite presentation with generators

{ϕ_{i,j} | 1 ≤ i, j ≤ n, i ≠ j}

and relations given in Equation 1 of Types C, D, and E.

Since the relators of Types C and D are commutators of generators, each group given by removing a subset of the relations containing all Type E relations is a graph group. Each such group has a defining graph whose vertices are the generators ϕ_{i,j} and whose edges connect (distinct) generators that commute.

\underline{Definition 1}. Let C(PΣ_{n}) [resp. D(PΣ_{n})] denote the defining graph of the graph group whose generators consist of the ϕ_{i,j} and whose relations consist of all Type C [resp. Type D] relations. Similarly, let CD(PΣ_{n}) denote the defining graph of the graph group whose generators consist of the ϕ_{i,j} and whose relations consist of all Type C and all Type D relations.

Recall a graph Γ is k-regular provided the degree of every vertex in Γ is k. Also recall that the link of ϕ_{i,j}, lk(ϕ_{i,j}), is the full subcomplex generated by all vertices adjacent to ϕ_{i,j}, while the star of ϕ_{i,j}, st(ϕ_{i,j}), is the cone of ϕ_{i,j} over lk(ϕ_{i,j}). Throughout this section, since we are only concerned with the underlying graphs, we will take lk(ϕ_{i,j}) and st(ϕ_{i,j}) to be the 1-skeleta of the topological link and star.

\underline{Proposition 1}. In C(PΣ_{n}), st(ϕ_{i,j}) is a copy of the complete graph K_{n−1}.

\underline{Proof}. Every pair of vertices of the form ϕ_{k,j} and ϕ_{l,j} with 1 ≤ l, k ≤ n (l, j, k distinct) are connected by an edge of Type C.

\underline{Proposition 2}. C(PΣ_{n}) is (n − 2)-regular, D(PΣ_{n}) is (n − 2)(n − 3)-regular, and CD(PΣ_{n}) is (n − 2)^{2}-regular.

\underline{Proof}. There is an edge of Type C between ϕ_{i,j} and ϕ_{k,j} if and only if k ≠ i, j. Thus, C(PΣ_{n}) is (n − 2)-regular. There is an edge of Type D between ϕ_{i,j} and ϕ_{k,l} if and only if i, j, k,and l are distinct. Thus, D(PΣ_{n}) is (n−2)(n−3)-regular. Since (n − 2) + (n − 2)(n − 3)=(n − 2)^{2}, it follows that CD(PΣ_{n}) is (n − 2)^{2}-regular.

Notice that the proof of Proposition 2 shows that for every i and j, lk(ϕ_{i,j}) = lk(ϕ_{j,i}) in the graph D(PΣ_{n}). Also notice it follows that all links of vertices in CD(PΣ_{n}) [resp. C(PΣ_{n}), D(PΣ_{n})] are isomorphic.

\underline{Corollary 1}. The link of any vertex of D(PΣ_{n+2}) is isomorphic to D(PΣ_{n}).

\underline{Proof}. The vertex ϕ_{n+1,n+2} is connected to the vertex ϕ_{l,m}(l ≠ m) by a Type D edge if and only if 1 ≤ l ≤ n, 1 ≤ m ≤ n, and l ≠ m. Thus, lkϕ_{n+1,n+2} = D(PΣ_{n}). The result follows from Proposition 2.

\underline{Proposition 3}. The link of any vertex of CD(PΣ_{n+1}) is isomorphic to a full subgraph of CD(PΣ_{n}).

\underline{Proof}. By definition, lk(ϕ_{n+1,j}) is a full subgraph of CD(PΣ_{n+1}). Since ϕ_{n+1,j} is not adjacent to any vertices of the form ϕ_{n+1,k} or ϕ_{k,n+1}, all vertices take the form ϕ_{l,m} where neither l nor m is equal to n + 1. Thus, lk(ϕ_{n+1,j}) is a full subgraph of CD(PΣ_{n}). It follows from Proposition 2 that the link of any vertex of CD(PΣ_{n+1}) is isomorphic to a full subgraph of CD(PΣ_{n}).

\underline{Proposition 4}. CD(PΣ_{n+1}) is obtained from CD(PΣ_{n}) by adding 2n vertices of the form ϕ_{i,n+1} and ϕ_{n+1,i}, together with 3n(n − 1)/2 edges of Type C and 2n(n − 1)(n − 2) edges of Type D.

\underline{Proof}. Clearly the only vertices that need to be added to CD(PΣ_{n}) are the 2n vertices of the form ϕ_{i,n+1} and ϕ_{n+1,i}.

By Proposition 1, for each i (1 ≤ i ≤ n) there are n − 1 edges of Type C between ϕ_{n+1,i} and the copy of K_{n−1} spanned by the vertices ϕ_{j,i} of CD(PΣ_{n}). Since the vertices of the form ϕ_{i,n+1} also form a copy of K_{n}, there are n(n − 1)/2 edges of Type C connecting these vertices to each other. Thus,

n(n − 1) + \frac{n(n − 1)}{2} = \frac{3n(n − 1)}{2}

additional edges of Type C are needed when constructing CD(PΣ_{n+1}) from CD(PΣ_{n}). Also, for each i, there are (n − 1)(n − 2) edges connecting each ϕ_{n+1,i} and ϕ_{i,n+1} to vertices in CD(PΣ_{n}) of the form ϕ_{j,k} with j, k, i, and n + 1 distinct. Thus, 2n(n − 1)(n − 2) additional edges of Type D are needed when constructing CD(PΣ_{n+1}) from CD(PΣ_{n}).

\underline{Definition 2}. Let ϕ_{i,j}, ϕ_{k,l} ∈ PΣ_{n}. The distance between ϕ_{i,j} and ϕ_{k,l}, denoted d(ϕ_{i,j}, ϕ_{k,l}), is the distance between those two vertices in CD(PΣ_{n}).

\underline{Proposition 5}. For each n ≥ 4, the diameter of CD(PΣ_{n}) is 2.

\underline{Proof}. Let n ≥ 4, and let ϕ_{i,j} ∈ CD(PΣ_{n}). We first show that each vertex ϕ_{k,l} in CD(PΣ_{n}) lies a distance at most 2 from ϕ_{i,j}. By ϕ_{a,b} C_{⟷} ϕ_{c,d} and ϕ_{a,b} D_{⟷} ϕ_{c,d}, we mean that the vertex ϕ_{a,b} is connected to the vertex ϕ_{c,d} by an edge of type C and D, respectively. There are six possible forms for ϕ_{k,l}:

(1) ϕ_{k,j} (k ≠ i, j). Then ϕ_{i,j} C_{⟷} ϕ_{k,j}.

(2) ϕ_{k,l} (i, j, k, l distinct). Then ϕ_{i,j} D_{⟷} ϕ_{k,l}.

(3) ϕ_{j,k} (k ≠ i, j). Then ϕ_{j,k} C_{⟷} ϕ_{l,k} D_{⟷} ϕ_{i,j}, where l ≠ i, j, k.

(4) ϕ_{i,k} (k ≠ i, j). Then ϕ_{i,k} C_{⟷} ϕ_{l,k} D_{⟷} ϕ_{i,j}, where l ≠ i, j, k.

(5) ϕ_{k,i} (k ≠ i, j). Then ϕ_{k,i} D_{⟷} ϕ_{l,j} C_{⟷} ϕ_{i,j}, where l ≠ i, j, k.

(6) ϕ_{j,i}. Then ϕ_{j,i} D_{⟷} ϕ_{l,k} C_{⟷} ϕ_{i,j}, where i, j, k, l are distinct.

Since ϕ_{i,j} and ϕ_{j,i} are not adjacent, the diameter of CD(PΣ_{n}) is 2.

5. A Finite Generating Set for ker θ. In [16], Orlandi-Korner computed Σ_{1}(PΣ_{n}), the first BNS-invariant of PΣ_{n}. As an immediate corollary of her main theorem, we have

\underline{Corollary 2}. (Orlandi-Korner) Let θ: PΣ_{n} → ⟨t⟩ be as in Section 3. Then ker θ is not finitely generated if and only if for some i and j, ϕ_{i,j} and ϕ_{j,i} are the only live generators under θ.

In this section, we calculate a set of finite generators for ker θ when the negation of the above condition holds. Since at least one generator must be live for ker θ ≠ PΣ_{n}, we will assume ϕ_{1,2} is live throughout this section, as in Section 3. (Recall that ϕ_{1,2} was chosen as our “transversal generator” in that section. The actual choice of a tranversal generator would depend on which generators are live and dead. Fortunately, the symmetry of McCool’s presentation of PΣ_{n} allows us to renumber accordingly.)

\underline{Definition 3}. Let ϕ_{i,j}, ϕ_{k,l} ∈ PΣ_{n}, with ϕ_{i,j} live. By a live path from ϕ_{i,j} to ϕ_{k,l}, we mean a path in CD(PΣ_{n}) in which all intermediate generators are live.

The following is immediate from Lemma 1 of [10].

\underline{Corollary 3}. (Levy et al.) If there exists a live path from ϕ_{1,2} to ϕ_{i,j}, then the family of generators of ker θ corresponding to ϕ_{i,j} can be reduced to one generator, namely {ϕ_{i,j}} or {ϕ_{i,j} ϕ_{1,2}^{−1}}, depending on whether ϕ_{i,j} is dead or live, respectively.

\underline{Theorem}. Let θ: PΣ_{n} → ⟨t⟩ be as in Section 3 with n ≥ 4, and assume it is not true that the only live generators are ϕ_{1,2} and ϕ_{2,1}. Then for each ϕ_{i,j}, the family of generators of ker θ corresponding to ϕ_{i,j} can be reduced to at most two generators. Specifically, if ϕ_{i,j} is live, it contributes {ϕ_{i,j} ϕ_{1,2}^{−1}} or {ϕ_{i,j} ϕ_{1,2}^{−1}, ϕ_{1,2} ϕ_{i,j} ϕ_{1,2}^{−2}}, while if ϕ_{i,j} is dead, it contributes {ϕ_{i,j}} or {ϕ_{i,j}, ϕ_{1,2} ϕ_{i,j} ϕ_{1,2}^{−1}}.

\underline{Proof}. Let ϕ_{i,j} ∈ PΣ_{n}. If there exists a live path from ϕ_{1,2} to ϕ_{i,j}, then Corollary 3 applies. It follows that ϕ_{i,j} contributes {ϕ_{i,j} ϕ_{1,2}^{−1}} to the generating set for ker θ if it is live and {ϕ_{i,j}} if it is dead. On the other hand, if there is no live path from ϕ_{1,2} toϕ_{i,j}, then ϕ_{i,j} does not commute with ϕ_{1,2}. By Proposition 5, d(ϕ_{1,2}, ϕ_{i,j}) = 2; consequently ϕ_{i,j} must be one of four forms: ϕ_{1,k}, ϕ_{k,1}, ϕ_{2,k} or ϕ_{2,1}, where k is neither 1 nor 2.

\underline{Case I}. ϕ_{i,j} takes the form ϕ_{1,k}, where k ≠ 2.

\underline{Subcase IA}. ϕ_{1,k} is live.

If ϕ_{k,2} is live, the relation [ϕ_{1,k}, ϕ_{1,2} ϕ_{k,2}] = 1 yields the family of relations

λ(1, k, m)λ(1, 2, m + 1)λ(k, 2, m + 2) = λ(1, 2, m)λ(k, 2, m + 1)λ(1, k, m + 2) (2)

for all m ∈ ℤ from Section 3, Case 3a. Since λ(1, 2, m + 1) = λ(1, 2, m) = 1 and the relation [ϕ_{1,2}, ϕ_{k,2}] = 1 yields the family λ(k, 2, m + 2) = λ(k, 2, m + 1) = λ(k, 2, 0) (Case 1a), Equation 2 can be rewritten as

λ(1, k, m + 2) = λ(k, 2, 0)^{−1}λ(1, k, m)λ(k, 2, 0).

Straightforward induction shows

λ(1, k, m) = \{ \begin{matrix}λ(k, 2, 0)^{−m/2}λ(1, k, 0)λ(k, 2, 0)^{m/2} & m even \\ λ(k, 2, 0)^{−(m−1)/2}λ(1, k, 1)λ(k, 2, 0)^{(m−1)/2} & m odd. \end{matrix}

Hence, λ(1, k, m) can be expressed in terms of λ(k, 2, 0) and λ(1, k, 0), or λ(k, 2, 0) and λ(1, k, 1). Thus, ϕ_{1,k} contributes {ϕ_{1,k} ϕ_{1,2}^{−1}, ϕ_{1,2} ϕ_{1,k} ϕ_{1,2}^{−2}} to the generating set of ker θ. Similarly, if ϕ_{k,2} is dead, ϕ_{1,k} contributes {ϕ_{1,k} ϕ_{1,2}^{−1}}.

\underline{Subcase IB}. ϕ_{1,k} is dead.

If ϕ_{k,2} is live, the relation [ϕ_{1,k}, ϕ_{1,2} ϕ_{k,2}] = 1 yields the family of relations in Case 3e. As in I.A., straightforward induction shows that δ(1, k, m) can be expressed in terms of λ(k, 2, 0) and δ(1, k, 0), or λ(k, 2, 0) and δ(1, k, 1). As in I.A. it follows that ϕ_{1,k} contributes {ϕ_{1,k}, ϕ_{1,2} ϕ_{1,k} ϕ_{1,2}^{−1}} to the generating set of ker θ. Similarly, if ϕ_{k,2} is dead, it follows that ϕ_{1,k} contributes {ϕ_{1,k}}.

\underline{Case II}. ϕ_{i,j} takes the form ϕ_{k,1}, where k ≠ 2. The techniques in this case are essentially identical to those of Case I.

\underline{Subcase IIA}. ϕ_{k,1} is live.

If ϕ_{k,2} is live, the relation [ϕ_{k,1}, ϕ_{k,2} ϕ_{1,2}] = 1 yields the family of relations in Case 3a, which can be used to show ϕ_{k,1} contributes {ϕ_{k,1} ϕ_{1,2}^{−1}, ϕ_{1,2} ϕ_{k,1} ϕ_{1,2}^{−2}} to the generating set of ker θ. Similarly, if ϕ_{k,2} is dead,ϕ_{k,1} contributes {ϕ_{k,1} ϕ_{1,2}^{−1}}.

\underline{Subcase IIB}. ϕ_{k,1} is dead.

If ϕ_{k,2} is live, the relation [ϕ_{k,1}, ϕ_{k,2} ϕ_{1,2}] = 1 yields the family of relations in Case 3a, which can be used to show ϕ_{k,2} contributes {ϕ_{k,1}, ϕ_{1,2} ϕ_{k,1} ϕ_{1,2}^{−1}}. Similarly, if ϕ_{k,2} is dead, ϕ_{k,1} contributes {ϕ_{k,1}}.

\underline{Case III}. ϕ_{i,j} takes the form ϕ_{2,k}, where k ≠ 1.
\underline{Subcase IIIA}. ϕ_{2,k} is live.

If ϕ_{1,k} is live, the relation [ϕ_{1,2}, ϕ_{1,k} ϕ_{2,k}] = 1 yields the family of relations in Case 3a. Straightforward induction shows that λ(2, k, m) can be expressed in terms of λ(1, k, 0), or λ(1, k, 0) and λ(1, k, 1) (depending on whether ϕ_{k,2} is live or dead), and λ(2, k, 1). In either case, it follows that ϕ_{2,k} contributes {ϕ_{1,2} ϕ_{2,k} ϕ_{1,2}^{−2}}.

If ϕ_{1,k} is dead, the relation [ϕ_{1,2}, ϕ_{1,k} ϕ_{2,k}] = 1 yields the family of relations in Case 3c. Again, straightforward induction shows that λ(2, k, m) can be expressed in terms of λ(2, k, 0). It follows that ϕ_{2,k} contributes {ϕ_{2,k} ϕ_{1,2}^{−1}}.

\underline{Subcase IIIB}. ϕ_{2,k} is dead.

If ϕ_{1,k} is live, the relation [ϕ_{1,k}, ϕ_{1,2} ϕ_{k,2}] = 1 yields the family of relations in Case 3b. Straightforward induction shows that δ(2, k, m) can be expressed in terms of λ(1, k, 0), or λ(1, k, 0) and λ(1, k, 1) (depending on whether ϕ_{k,2} is live or dead), and δ(2, k, 1). In either case, it follows that ϕ_{2,k} contributes {ϕ_{1,2} ϕ_{2,k} ϕ_{1,2}^{−1}}.

If ϕ_{1,k} is dead, the relation [ϕ_{1,k}, ϕ_{1,2} ϕ_{k,2}] = 1 yields the family of relations in Case 3d. Straightforward induction shows that δ(2, k, m) can be expressed in terms of δ(1, k, 0), or δ(1, k, 0) and δ(1, k, 1) (depending on whether ϕ_{k,2} is live or dead), and δ(2, k, 0). In either case, it follows that ϕ_{2,k} contributes {ϕ_{2,k}}.

\underline{Case IV}. ϕ_{i,j} takes the form ϕ_{2,1}.

\underline{Subcase IVA}. ϕ_{2,1} is live.

\underline{Subcase IVA1}. ϕ_{k,1} is live.

The relation [ϕ_{k,1}, ϕ_{2,1}] = 1 yields the family of relations in Case 1a. By induction, λ(2, 1, m) can be expressed in terms of λ(k, 2, 0), λ(k, 1, 0) andλ(2, 1, 0). It follows that ϕ_{2,1} contributes {ϕ_{2,1} ϕ_{1,2}^{−1}}.

\underline{Subcase IVA2}. ϕ_{2,k} is live.

If ϕ_{1,k} is live, the relation [ϕ_{2,1}, ϕ_{2,k} ϕ_{1,k}] = 1 yields the family of relations in Case 3a. By induction, λ(2, 1, m) can be expressed in terms of λ(2, 1, 0), λ(2, 1, 1), λ(2, k, 0), λ(1, k, 0) and λ(k, 2, 0) (Note the results are the same using δ(k, 2, 0)). It follows that ϕ_{2,1} contributes {ϕ_{2,1} ϕ_{1,2}^{−1}, ϕ_{1,2} ϕ_{2,1} ϕ_{1,2}^{−2}}. Similarly, if ϕ_{1,k} is dead, ϕ_{2,1} contributes {ϕ_{2,1} ϕ_{1,2}^{−1}}.

\underline{Subcase IVA3}. ϕ_{k,2} is live.

If ϕ_{k,1} is live, refer to Case IVA1. If ϕ_{k,1} is dead, the relation [ϕ_{k,2}, ϕ_{k,1} ϕ_{2,1}] = 1, yields the family of relations in Case 3e. By induction, λ(2, 1, m) can be expressed in terms of λ(k, 2, 0), δ(k, 1, 0) and λ(2, 1, 0). It follows that ϕ_{2,1} contributes {ϕ_{2,1} ϕ_{1,2}^{−1}}.

\underline{Subcase IVA4}. ϕ_{1,k} is live.

If ϕ_{2,k} is live, refer to Case IVA2. If ϕ_{2,k} is dead, the relation [ϕ_{2,1}, ϕ_{2,k} ϕ_{1,k}] = 1, yields the family of relations in Case 3c. By induction, λ(2, 1, m) can be expressed in terms of λ(2, 1, 0), δ(2, k, 0), λ(1, k, 0), λ(1, k, 1) and λ(k, 2, 0). It follows that ϕ_{2,1} contributes {ϕ_{2,1} ϕ_{1,2}^{−1}}.

\underline{Subcase IVB}. ϕ_{2,1} is dead.

\underline{Subcase IVB1}. ϕ_{k,2} is live.

The relation [ϕ_{k,2}, ϕ_{k,1} ϕ_{2,1}] = 1 yields the family of relations in Case 3d. By induction, δ(2, 1, m) can be expressed in terms of λ(k, 2, 0), δ(k, 1, 0) and δ(2, 1, 0). It follows that ϕ_{2,1} contributes {ϕ_{2,1}}.

\underline{Subcase IVB2}. ϕ_{k,2} is dead, but ϕ_{1,k} and ϕ_{2,k} are live.

The relation [ϕ_{2,1}, ϕ_{2,k} ϕ_{1,k}] = 1 yields the family of relations in Case 3e. By induction, δ(2, 1, m) can be expressed in terms of λ(2, k, 0), λ(1, k, 0), δ(k, 2, 0), δ(2, 1, 0), and δ(2, 1, 1). It follows that ϕ_{2,1} contributes {ϕ_{2,1}, ϕ_{1,2} ϕ_{2,1} ϕ_{1,2}^{−1}}.

\underline{Subcase IVB3}. ϕ_{k,2} is dead, ϕ_{1,k} is live and ϕ_{2,k} is dead [resp., ϕ_{1,k} is dead and ϕ_{2,k} is live].

The relation [ϕ_{2,1}, ϕ_{2,k} ϕ_{1,k}] = 1 yields the family of relations in Case 3g [resp. Case 3f]. By induction, δ(2, 1, m) can be expressed in terms of δ(2, k, 0) [resp. λ(2, k, 0)], λ(1, k, 0) [resp. δ(1, k, 0)], δ(k, 2, 0), and δ(2, 1, 0). In either case, it follows that ϕ_{2,1} contributes {ϕ_{2,1}}.

Since all possible cases have been considered, it follows that for each ϕ_{i,j}, the family of generators of ker θ corresponding to ϕ_{i,j} can be reduced to at most two generators.

\underline{Example}. Let θ: PΣ_{4} → ⟨t⟩ be given by ϕ_{1,2}, ϕ_{3,2}, ϕ_{4,1}, ϕ_{2,4} ↦ t and all remaining generators mapped to 1. (Figure 1 contains CD(PΣ_{4}).) Note that ϕ_{i,j} is represented as i, j, vertices of the form (i, j) are identified with i, j, live vertices are represented by squares, and dead vertices are represented by circles.

By Corollary 2, ker θ is finitely generated. First, consider all generators ϕ_{i,j} for which there is a live path from ϕ_{1,2} to ϕ_{i,j}. ϕ_{3,2} is live and therefore by Corollary 3 contributes {ϕ_{3,2} ϕ_{1,2}^{−1}}. Similarly, ϕ_{4,1} contributes {ϕ_{4,1} ϕ_{1,2}^{−1}}. ϕ_{4,2} is dead and contributes {ϕ_{4,2}}. Similarly, ϕ_{4,3}, ϕ_{3,4}, ϕ_{2,1}, ϕ_{3,1}, ϕ_{2,3} and ϕ_{1,4} correspond to the generators {ϕ_{4,3}}, {ϕ_{3,4}}, {ϕ_{2,1}}, {ϕ_{3,1}}, {ϕ_{2,3}} and {ϕ_{1,4}}, respectively. Finally, consider all generators with no live path from ϕ_{1,2} to the generator, i.e. ϕ_{1,3} and ϕ_{2,4}. By the previous theorem, ϕ_{1,3} corresponds to {ϕ_{1,3}, ϕ_{1,2} ϕ_{1,3} ϕ_{1,2}^{−1}}. Similarly, ϕ_{2,4} contributes {ϕ_{2,4} ϕ_{1,2}^{−1}}. So, a generating set for ker θ is:

{ϕ_{3,2} ϕ_{1,2}^{−1}, ϕ_{4,2}, ϕ_{4,3}, ϕ_{3,4}, ϕ_{4,1} ϕ_{1,2}^{−1}, ϕ_{2,1}, ϕ_{3,1}, ϕ_{2,3}, ϕ_{1,4}, ϕ_{1,3}, ϕ_{1,2} ϕ_{1,3} ϕ_{1,2}^{−1}, ϕ_{2,4} ϕ_{1,2}^{−1}}.

\underline{References}

1. J. Becker, M. Horak, and L. VanWyk, “Presentations of Subgroups of Artin Groups,” Missouri Journal of Mathematical Sciences,. 10 (1998), 3–14.

2. M. Bestvina and N. Brady, “Morse Theory and Finiteness Properties of Groups,” Invent. Math., 129 (1997), 445–470.

3. N. Brady, J. McCammond, J. Meier, and A. Miller, “The Pure Symmetric Automorphisms of a Free Group Form a Duality Group,” Journal of Algebra, 246 (2001), 881-896.

4. A. Brownstein and R. Lee, “Cohomology of the Group of Motions of n Strings in 3-space,” Contemp. Math., 150 (1993), 51–61.

5. C. Droms, “Graph Groups, Coherence, and Three-manifolds,” Journal of Algebra, 106 (1987), 484–489.

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

7. D. L. Goldsmith, “The Theory of Motion Groups,” Mich. Math. J., 28 (1981), 3–17.

8. M. Gutiérrez and S. Krstić, “Normal Forms for Basis-Conjugating Automorphisms of a Free Group,” IJAC, 8 (1998), 631–669.

9. S. P. Humphries “On Weakly Distinguished Bases and Free Generating Sets of Free Groups,” Quart. J. Math. Oxford, 36 (1985), 215–219.

10. J. Levy, C. Parker, L. VanWyk, “Finite Presentation of Subgroups of Graph Groups,” Missouri Journal of Mathematical Sciences, 10 (1998), 70–82.

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

12. W. Magnus, A. Karrass, and D. Solitar, Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations, second revised edition, Dover, New York, 1976.

13. J. McCool, “On Basis-Conjugating Automorphisms of Free Groups,” Canadian Journal of Mathematics, 38 (1986), 1525–1529.

14. J. Meier and L. VanWyk, “‘Bieri-Neumann-Strebel Invariants for Graph Groups,” Proceedings of the London Mathematical Society, 71 (1995), 263–280.

15. J. Meier, H. Meinert, and L. VanWyk, “Higher Generation Subgroup Sets and the Σ-invariants of Graph Groups,” Comment. Math. Helv., 73 (1998), 22–44.

16. L. Orlandi-Korner, “The Bieri-Neumann-Strebel Invariant for Basisconjugating Autmorphisms of Free Groups,” Proceedings of the American Mathematical Society, 128 (2000), 1257–1262.

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

Erin Corman Department of Mathematics Keene State College Keene, NH 03435 email: eecorman@hotmail.com

Rebecca Dolphin Department of Mathematics Mary Washington College Fredericksburg, VA 22401 email: radolphin@juno.com

Leonard VanWyk Department of Mathematics & Statistics James Madison University Harrisonburg, VA 22802 email: vanwyk@math.jmu.edu