Groups, graphs, and bases

:g - G R O U P S , G R A P H S , A N D B A S E S

Christopher Schaufele and Nancy Zumoff Kennesaw State College, Marietta, Georgia 30061

1. Introduction:

In 1949, Marshall Hall, Jr., proved the now well-known theorem [1]: If F is a finitely generated free group,

Ho

a finitely generated subgroup, and x~..... x m are any

elements of which are not in H o, then there exists a subgroup H* of F satisfying i) H* has finite index in F, ii)

Ho

is a free factor of H*, and

iii) Xl,...,I m q~ H * . Throughout this paper, a subgroup H* which satisfies i) and ii) will he called a Ho .

*-group

for

Hall's proof was completely algebraic, but several geometric proofs have followed

using topological covering space theory: Tretkoff [3]; and Stallings [2], to name a couple. However, these proofs only demonstrate the existence of such a subgroup, H*, and leave many questions regarding the nature of the collection of all *-groups for a given subgroup Ho .

This paper provides an effective method for constructing all *-groups corresponding

to an

H o . Our

method uses the folding and immersion techniques for graphs developed by

Stallings [2]. In his paper, he constructs a graph immerses

No

vertices of

No

with fundamental group

H o,

in a covering graph N without destroying a maximal tree or the number

N o,

thus producing all possible *-groups of index

no .

then no

of

Larger index *-groups

are rather easy to come by; a search for such subgroups of index smaller than

no

lead to

the techniques in this research. Essentially, our method involves identification of certain vertices of the graph

No

by extending a basis for

H o,

and then embedding the resulting

graph in a covering graph to reduce index, or addition of vertices and embedding to increase index. Precisely, our result is: given a finitely generated subgroup

H o

of a finitely

generated free group F, we describe a construction which yields any *-group

187

corresponding to H o. For simplicity, this construction is described for a free group of rank 2; generalization to larger rank is obvious. Also the construction is for the special case when the set of xi's ( in Hall's theorem ) is empty. This construction is easily adaptable to produce *-groups which do not contain a given set of x i ~ H o.

2. Stalling's Folding and Immersion:

We give a brief description of these techniques used in [2]. Let F be a graph with two types of oriented edges: a-edges and b-edges ( we are thinking of a and b as free generators of F -- F 2 ). Suppose that e t and e2 are edges of F of the same type with either the same initial or same terminal vertices. Then F admits a fold, which is an identification of edges e I and e 2 as shown.

~

e2

~ r

eI

=

e2

Let X be the one point union of two circles joined at base point x o and identify nl(X, x o) with F = (a, b:). ff F is a graph which admits no folds, then F immerses in a

coveting graph (~,, T0) over (X, x0). If F is any graph, then there is a mapping f : F A, where A is a coveting graph over X, and f factors through a sequence of folds and an immersion. Let H o be a subgroup of F with generating set B = {7/,---,'tin}, where each ~/l is a

reduced word in a and b. Construct a graph which has fundamental group H o as follows: take the one point union of m circles joined at base point vo , each circle subdivided so as to correspond to a "ri as a word in a and b. Fold to a graph N o which admits no more folds; N o is called a core graph, and hi(N0, v0) = H o . N o can be immersed in a covering graph

N0 over X such that the coveting map 9 induces a monomorphism p. : nl(~r0, v0)

• 1(x, ,Co) and Ho =

Vo).

188

3. Extending Free Bases:

Henceforth, H o will be a given finitely generated subgroup of F = F 2 with a free basis B o = {71,".,Tm}. Now, let H t be a subgroup of F which is generated by B = BokJ[~l,...,~r}, where the [3i are freely reduced as words in a and b. We are interested in

when B is a free basis for H 1, Let (NI, wl) be the covering graph over (X, x o) which corresponds to the subgroup H 1. Since H o is a subgroup of H~, there is a covering map

Oo : (l%, Vo) > (Ux, wl), where N o and N0 are as described in section 2. We define a new graph F 1 as follows: vertices zi of F 1 are in a one-to-one correspondence with vertices vi of At0 such that p0(vi) = wx ; base point will be Zo; vertices zi and zj are joined by an edge e in F 1 if and only if viand vj (not both of which are v0) are

joined by a path in N0 corresponding to a reduced word in B. Let X 1 be the one-point union of m + r circles joined at base point x l, one circle for each element of B. Then F t immerses in a covering graph ('~p z 0) over (X1, Zl)T H E O R E M 1. B is a f r e e basis f o r H 1 i f and only i f (F1, Zo) can be embedded in the universal cover over (X~, xl).

PROOF: Suppose B is not a free basis for H r Since B o is a free basis for H o, there is a

non-trivial freely reduced word (in B ) w E H o in which some Ill appears at least once. Thus w is a loop in (N0, Vo) and so the vertex Zo is joined to itself by the path corresponding to w in F1; i.e., 7rl(F1, Zo) ~ O. The converse is a reversal of the above argument. 4. Construction of * - Groups: Let N o, X , and H o be as described in Section 2, and let n o be the number of vertices

of N o. In [2], N o is immersed in all possible covering graphs which have producing all *-groups of index yields all *-groups.

no

no

vertices, thus

corresponding to H o. We now describe a process which

189

Let T o be a maximal tree in the core graph N o. For each vertex v i e N o , there is a unique path c~i in T o joining the basepoint v o to v i . Each of these ct i corresponds to a reduced word in F 2 which will also be referred to as o~i. Note that these c~i's are contained in a Schreier system for Ho; we call the set {cti}j a

core

Schreier

s y s t e m ( C S S ) , and the

basis B o for H o which is obtained from the C S S will be called a core basis. For each pair of vertices v i, vy e N o, i ~ j , let I~/j = aiccj "1. (Note that as part of the graph No, ~iy starts at the basepoint v o, goes out to vertex v i, jumps to vertex vj, and then returns to Vo.) Consider any set of the form

B = B 0 k.) B 1 ,

where B 1 is a subset of {[30.}ld such that B is a free basis for the subgroup of F which it generates. For each word [3/j e B 1 , adjoin to N o a v0-based loop subdivided so as to correspond to [3/yas a word in a and b. Now, perform all possible folds to obtain a graph N 1 with n I vertices. (This identifies at least vertices v i and vy, and hence n 1 <

no

if B 1 ~ 0

• ) The given subgroup H o is a free factor of ~1(N1, v o) since B freely generates its subgroup of F. N 1 may or may not be a covering graph over X; if it is, then ~ l ( N p v o) corresponds to a *-group of index n 1. If N 1 is not a covering graph over X, then it can be embedded in a covering graph Ar1 with n vertices for any n > n 1. The actual construction of a Nr1 with n 1 vertices is described in [2]; covering graphs /V1 which have n > n 1 vertices can be constructed using the same method after first adding disjoint vertices to

Ul. 5. Characterization of *-Groups: A finite subset B of F will be called a * - e x t e n s i o n of the core basis B o if B is the disjoint union of sets B o, B 1, and. B 2, where i) B is a free basis for the subgroup of F which it generates, ii) B 1 is composed of words [3~/= o ~ f 1 , a i o~j e CSS, iii) B 2 is composed of words of the form

[3 -- o~iuo~f 1 , u ~e

1, and the longest initial segments of [3 and of [3-1cti which are in the core N o are a i and o~j respectively. B 1 will be called an i d e n t t f i c a t i o n set, and B 2 a c o m p l e t i o n set for B o

T H E O R E M 2. l f H is a *-group f o r H o , then any core basis B o f o r H o is c o n t a i n e d in a

190

basis B f o r H which is a *-extension o f B o.

PROOF: Suppose H is any *-group, and let B o be a core basis for H o obtained from a CSS {ai}j- There is a free basis

B / = B o u B1 /

for H since H o is a free factor of H. If w is any reduced word in F, we think of w as an oriented path in N0 with initial vertex at the base point v o. Each I3/e B / c a n be written as 5tU~iz"t , where 8 x is the maximal initial segment of t3/which lies in the core N o, and 62 is the maximal initial segment of (13/)'161 which lies in N o. Let v i and vi be the terminal vertices of 51 and 52; then replace 13/e B / b y

13/j = cxiucxfI , and let B 1 be the set of all

these 13/j for which u = 1, B 2 the set of all these 13/ysuch that u e 1. Note that 13ij = (OqSl'l)13/(y~o:fI) and that oqS1"l and 52etl"1 e H o , so the replacement of I3/ by 13/) yields another free basis

B = B o u B t ~) B 2

for H which is a *-extension of B o. Theorem 2 shows that the construction irL Section 4 yields all *-groups corresponding to H o. A brief description of the identification set B 1 and the completion set B 2 is as follows: first add to N o v0-based loops corresponding to elements of B 1 and fold

(geometrically, this identifies certain vertices and edges of N o) to a graph No/; then add v0-based loops to No / corresponding to elements of B 2 and fold to a graph N1/. This is a covering graph of finite index into which N O is immersed. Since *-groups are constructed by extending z free basis for H o, THEOREM 1 gives some insight into what kind of elements can be added to B o without destroying freeness.

191

REFERENCES

1. M. Hall, Jr., CosetRepresentations in Free Groups, Trans. A. M. S. 67 (1949), 421-432. 2. J. R. Stallings, Topology of Finite Graphs, Invent. Math. 71 (1983), 551-565. 3. M. Tretkoff, Covering Space Proofs in Combinatorial Group Theory, Communications in Alg. 3(5) (1975), 429-457.