Graph Foldings

Ryan Hoban
May 2007

The purpose of this notebook is to demonstrate the graph folding algorithm of Stallings, and illustrate how this algorithm can be used to simplify comutations in Free Groups.  This algorithm is a fantastic example of using topological methods to simplfy the answers algebraic questions.

The algorithm enables one to easily compute a Nielsen basis for a subgroup of a free group, as well as detect when a set of n words in a free group of rank n determines an automorphism of the group (Sections 1,2).  In the case where the input set does determine an automorphism, the process can be used to decompose the automorphism as a product of Nielsen Transformations.  This makes computing the inverse of the automorphsim easy as well (Section 3).  Finally we demonstrate how to obtain subgroups of finite index (Section 6).  For rank 1 free groups this is all trivial since the group is then cyclic.  Currently the notebook will only work for free groups of rank 2 or 3, but this should generalize pretty easily.  

This notebook relys upon the package FreeGroupAutos.m by Bill Goldman, and Combinatorica which is a standard add-on that comes with Mathematica 5.2.   These packages are loaded below.

SetDirectory[ToFileName[Extract["FileName"/.NotebookInformation[EvaluationNotebook[]], {1}, FrontEnd`FileName]]] ;

<<FreeGroupAutos.m

<<DiscreteMath/Combinatorica.m

Necessary Functions - code is suppressed, descriptions are below.

Descriptions of all Graph Functions defined above

All the descriptions listed here are functions written for this notebook specifically for working with these graphs.

? CreateLoopFromWord

? ContractDirected

? IdentifyVertices

? CreateStartingBouquet

? FixedGraphDifference

? FindWordsFromGraphs

? FindPossibleFolds

? IdentifyEdges

? FindTree

? ChangeTree

? FindNielsenTrans

CreateLoopFromWord[word] returns a loop that corresponds to the input word.  The graph output is colored and the edges labeled by the letters in word.

IdentifyVertices[graph,{v,w}] returns the quotient of graph obtained by identifying vertices v and w

CreateStartingBouquet[{word1,word2,...}] returns the starting Bouquet graph generated by the list of words

FindWordsFromGraphs[graph,spanningtree] returns the list of words which are induced by the tree inside graph

FindPossibleFolds[graph] returns all possible pairs of edges that could be folded

FindTree[graph] returns a geodesic spanning tree inside a directed graph with a basepoint that is the largest numbered vertex in graph

ChangeTree[tree,edge] returns a spanning tree which contains edge.  edge must have the form {{v1,v2},opts}

FindNielsenTrans[graph,tree1,tree2] gives the Nielsen Transformation that changes from a set of generators induced by tree1 to a set of generators induced by tree2.

1) Setup Starting Graphs

A free group of rank n is the fundamental group of the one point union of n circles.  Let F_n =<X_1,..X_n.> be a free set of generators and we will identifyF_n with a graph G that is simply the wedge of n circles.  Let {W_1,...,W_k} be a list of words in these generators and let H be the subgroup generated by these words.  Nielsen proved that H is itself free, although the topological proof of this fact is quite trivial.  The inclusion of H into F_n induces a morphism of a bouquet of k circles into G which we now describe.  
Begin by creating a circle which will correspond to W_1.  Subdivide this circle into |W_1| edges.  Choose a vertex in this graph to be a basepoint, and label each edge by the generators in W_1.  For example:   

W1 = Word[1, 2, -1, 3, -2] ;

loop1 = CreateLoopFromWord[W1] ;

ShowGraph[loop1, VertexNumber→True] ;

[Graphics:HTMLFiles/GraphFoldings_62.gif]

Throughtout this notebook, we make use of the Word datatype defined in FreeGroupAutos.nb.  For further explaination of this data type see that notebook, but for our purposes, Word[1] represents the first generator of F_n, Word[2] the second generator and so on.  Word[1,2] is the product of Word[1] and Word[2], and the inverses of these generators are Word[-1], Word[-2], etc.

Realize that the graph labeled loop1 above now defines a graph morphism from loop1 (which is simply a circle) into G by gluing directed edges around the appropriate loops of G.  This quotient of loop1 is naturally a subspace of G, and there is an induced homomorphism on π_1 whose image inside F_nis the subgroup generated by W_1.  Repeat this procedure for each W_i, and then glue these circles together by simply identifying the basepoint of each circle.  The result is a bouquet of k circles which is called a rose and is denoted G_0.  Note that for all graphs throughtout this notebook, the basepoint will be the largest numbered vertex.  Some care needs to be taken keeping track of this basepoint, and most of the functions defined above make this assumption and return graphs whose highest numbered vertex is the image of the original input basepoint.

By identifying all vertices to a single vertex, and all directed edges of the bouquet we again obtain a subspace of G, and, following the notation in Bestvina's notes, denote the quotient map g_0:G_0→G.  The image of the induced map on π_1 is precisely H, i.e g_0^*(π_1(G_0))=H.  We illustrate with the example below:

H = {Word[-2, 1, -2, -2, 1], Word[-2, -2, 1]}

G0 = CreateStartingBouquet[H] ;

ShowGraph[G0, VertexNumber→True] ;

{Word[-2, 1, -2, -2, 1], Word[-2, -2, 1]}

[Graphics:HTMLFiles/GraphFoldings_79.gif]

This graph can be used to identify a generating set for H.  To do this, we choose a spanning tree T_0 inside G_0.  For each edge e in G_0-T_0, there is a unique loop in G_0 containing e which is determined as follows.  There is a unique path p_1 in T_0 from the basepoint to the initial vertex of e, and a unique path p_2 from the terminal vertex of e to the basepoint.  Construct the loop that is the composition of p_1, then e, then p_2.  This is a based loop in G_0, and by reading the (oriented) labels of the edges in this loop we obtain a word.  Doing this for each edge in the compliment of T_0 gives a generating set for H.  Note that this may not be exactly the orignial generating set, rather it may contain the inverses of some words as we see in this example.  

T0 = FindTree[G0] ;

ShowGraphArray[{G0, T0}, VertexNumber→True] ;

gens = FindWordsFromGraphs[G0, T0] ;

Print["The Generating Set is: ", gens]

[Graphics:HTMLFiles/GraphFoldings_96.gif]

The Generating Set is:  {Word[-1, 2, 2, -1, 2], Word[-1, 2, 2]}

2. Graph Foldings (Stallings Algorithm)

The graph G_0 described above defines a morphism g_0:G_0→G, ie a map from the wedge of 2 circles to the wedge of 2 circles.  By choosing a spanning tree, we are able to obtain a generating set for H as a subset of G.  Now let's consider how to find a free generating set, or a Nielsen Set of generators for H.  Essential to this algorithm will be the following morphism:

Definition:
Let e_1 and e_2 be distinct edges in a directed graph G, which share the same initial vertex (or terminal vertex).  Form a new graph G' which is obtained from G by identifying edges e_1 and e_2.  The quotient is a graph with one fewer edges than G, and the quotient map is a morphism in the category of directed graphs.  This map is called a Fold.

The key fact that makes the algorithms demonstrated here is the following due to Stallings:

Theorem (Stallings): Every morphsim of finite graphs can be factored as a composition of finitely many folds, and then an immersion.  

The algorithm begins by factoring the map
g_0 as in the previous theorem.  With each fold, the idea is to make the graph look more and more like a covering space of the rose G.  The function below identifies possible folds of the graph G_0.  This function only displays potential folds for which the edges have the same label, and are directed the same way with respect to the common vertex.  This is to ensure that the fold will actually commute with the original map g_0, and hence after folding, the image of π_1 will remain unchanged.

FindPossibleFolds[G0]

The above function has identified 2 potential folds of G_0.  The first glues edge {4,7} and edge{6,7} which are both directed inward to vertex 7 and labeled with Word[1].  The second glues edge {1,7} to edge {5,7} which are also both directed inward at vertex 7 but labeled with Word[2].  The order in which folds are done is not important, so we will simply choose the first pair of edges and identify them to obtain a new graph G_1.  The graph G_1 yields a map g_1:G_1→G by identifying edges which commutes with the folding map G_0G_1.

fold = FindPossibleFolds[G0][[1]] ;

G1 = IdentifyEdges[G0, fold] ;

ShowGraph[G1, VertexNumber→True] ;

[Graphics:HTMLFiles/GraphFoldings_120.gif]

The quotient graph will often look a bit confusing.  When forming the quotient graph, Mathematica will renumber most vertices, and will likely have a very different embedding in the plane than the previous graph.  All graphs in this notebook are Radially Embedded around the basepoint (which as noted above will always remain the highest numbered vertex).  This means vertices will be equally spaced around concentric circles centered at the basepoint depending upon their distance from the basepoint.  It is perhaps worth taking a moment and convincing yourself that the above graph is in fact (isomorphic to) the desired graph obtained from G_0.
Next we need to find the induced quotient graph T_1.  Similar to above this determines a generating set for the subgroup H.

T1 = IdentifyEdges[T0, fold] ;

ShowGraphArray[{G1, T1}, VertexNumber→True] ;

gens = FindWordsFromGraphs[G1, T1] ;

Print["The Generating Set is: ", gens] ;

[Graphics:HTMLFiles/GraphFoldings_127.gif]

The Generating Set is:  {Word[-1, 2, 2, -1, 2], Word[-1, 2, 2]}

Note here that the generating set determined by G_1 and T_1 is exactly the same as the one determined by G_0 and T_0.  This will always be the case provided that both of the folded edges are in the spanning tree prior to folding:

Lemma: Let G_i be a graph and T_iG_i a tree.  Let f:G_iG_ (i + 1)be a fold, which restricts to a fold of T_i.  This simply means that both edges to be identified in the fold are contained in T_i.  Then each edge in the complement of T_i has an image which is in the complement of of T_ (i + 1).  Each such edge determines a loop in G_i as described above.  This loop and its image in in G_ (i + 1)
are directed and labeled identically, and hence determine the same generator in
F_n.

Now look for possible folds of G_1 to obtain G_2.  Once again we will simply choose the first fold listed, except this time note that the both edges in this fold are not contained in the tree T_1.

fold = FindPossibleFolds[G1][[1]]

{{{5, 3}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}, {{5, 4}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}}

Before folding we first will change the choice of spanning tree.  This is accomplished by adding all edges to be folded to the tree, and removing others so the result is a different spanning tree.  The funciton ChangeTree below accomplishes this.

newT1 = ChangeTree[T1, fold[[1]]] ;

newT1 = ChangeTree[newT1, fold[[2]]] ;

newT1 = SetGraphOptions[newT1, PlotLabel→New Tree] ;

T1 = SetGraphOptions[T1, PlotLabel→Original Tree] ;

ShowGraphArray[{G1, T1, newT1}, VertexNumber→True] ;

[Graphics:HTMLFiles/GraphFoldings_155.gif]

This new tree induces a  different new generating set for H.  Of course the loops are the same so this new set still generates H.  The generating set induced by newT1 is interesting in this case because there is a loop which has length 6 but the induced word only has length 2.  This is because the loop is not "tight" in the sense that there are consecutive edges in the loop with the same label and opposite orientations.

gens1 = FindWordsFromGraphs[G1, T1] ;

gens2 = FindWordsFromGraphs[G1, newT1] ;

Print["Generating Set induced by T1: ", gens1] ;

Print["Generating Set induced by newT1: ", gens2] ;

Generating Set induced by T1:  {Word[-1, 2, 2, -1, 2], Word[-1, 2, 2]}

Generating Set induced by newT1:  {Word[-1, 2], Word[-2, -2, 1]}

The difference between these 2 generating sets is a composition of at most one of each of the following Elementary Nielsen Transformations.  

Definition: Given a set H={W_1,...,W_k} of words in F_n, then the Elementary Nielsen Transformations of H are:
1) Permutations- These are maps which fix  all but 2 words, and simply permute these remaining 2 words of H
2) Sign Changes- These are maps which fix all but 1 word, and take that special word to its inverse
3) Change of spanning tree - Maps for which there is some k such that
W_k is mapped either to W_kor W_k^(-1), and all other W_j are mapped to one of:
    
W_j^(±1)W_k
    
W_kW_j^(±1)
    
W_j^(±1)W_kW_j^(∓1)
    
W_j^(∓1)W_kW_j^(±1)

*****I think this is probably worth a detailed explaination of all the possible cases when changing spanning tree if I'm going to do something useful with this.  Could be pretty interesting to illustrate these cases too.  Maybe make an additional section at the end discussing these.**********

The function FindNielsenTrans can be used to compute the Transformation induced by changing spanning trees.  Here we find this transformation and verify that this is indeed the correct Nielsen Transformation by composing the transformation with the original generating set to obtain the new generating set.

trans1 = FindNielsenTrans[G1, T1, newT1] ;

Print["The Nielsen Transformation induced by this change of Trees is: ", trans1] ;

ComposeAuto[trans1, gens1] == gens2

The Nielsen Transformation induced by this change of Trees is:  {Word[-2, 1], Word[-2]}

True

We now fold G_1 again.  The quotient tree we use is newT1 since this contains both edges to be folded.  Once again since both edges to be folded are contained in newT1, the induced generating set does not change after folding:

G2 = IdentifyEdges[G1, fold] ;

T2 = IdentifyEdges[newT1, fold] ;

T2 = SetGraphOptions[T2, PlotLabel->""] ;

T2 = ChangeVertices[T2, Vertices[G2]] ;

ShowGraphArray[{G2, T2}, VertexNumber→True] ;

gens = FindWordsFromGraphs[G2, T2] ;

Print["The Generating Set is still: ", gens] ;

[Graphics:HTMLFiles/GraphFoldings_192.gif]

The Generating Set is still:  {Word[-1, 2], Word[-2, -2, 1]}

Fold Again. This time the second edge to be folded is not in the tree T_2, so we first change trees and find the corresponding Nielsen Transformation.  Since the edges changed are only in one loop and are oriented the same way, this new tree does not change the generating set, hence the corresponding Nielsen Transformation is the identity map.

fold = FindPossibleFolds[G2][[1]] ;

Print["The fold is: ", fold] ;

newT2 = ChangeTree[T2, fold[[1]]] ;

newT2 = ChangeTree[newT2, fold[[2]]] ;

ShowGraphArray[{G2, T2, newT2}, VertexNumber→True] ;

Print["The generating set is still:", FindWordsFromGraphs[G2, newT2]] ;

The fold is:  {{{4, 2}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}, {{4, 5}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}}

[Graphics:HTMLFiles/GraphFoldings_202.gif]

The generating set is still: {Word[-1, 2], Word[-2, -2, 1]}

Fold G_2 to obtain G_3.  The gererating set remains the same:

G3 = IdentifyEdges[G2, fold] ;

T3 = IdentifyEdges[newT2, fold] ;

T3 = ChangeVertices[T3, Vertices[G3]] ;

ShowGraphArray[{G3, T3}, VertexNumber→True] ;

Print["The generating set is still: ", FindWordsFromGraphs[G3, T3]] ;

[Graphics:HTMLFiles/GraphFoldings_211.gif]

The generating set is still:  {Word[-1, 2], Word[-2, -2, 1]}

Again the second element of fold is not in the tree, so we change trees and find the corresponding Nielsen Transformation.

fold = FindPossibleFolds[G3][[1]] ;

newT3 = ChangeTree[T3, fold[[2]]] ;

gens3 = FindWordsFromGraphs[G3, newT3] ;

trans2 = FindNielsenTrans[G3, T3, newT3] ;

ShowGraphArray[{G3, T3, newT3}, VertexNumber→True] ;

Print["The fold is: ", fold] ;

Print["The new generating set is: ", gens3] ;

Print["The Nielsen Transformation induced by the changing trees is: ", trans2] ;

ComposeAuto[trans2, gens2] == gens3

[Graphics:HTMLFiles/GraphFoldings_222.gif]

The fold is:  {{{1, 4}, EdgeLabel→Word[1], EdgeColor→RGBColor[1, 0, 0]}, {{2, 4}, EdgeLabel→Word[1], EdgeColor→RGBColor[1, 0, 0]}}

The new generating set is:  {Word[-1, 2], Word[-1, 2, 2]}

The Nielsen Transformation induced by the changing trees is:  {Word[1], Word[-2]}

True

Perform the fold found above to obtain G_4 and T_4.  Of course the generating set does not change:

G4 = IdentifyEdges[G3, fold] ;

T4 = IdentifyEdges[newT3, fold] ;

T4 = ChangeVertices[T4, Vertices[G4]] ;

ShowGraphArray[{G4, T4}, VertexNumber→True] ;

FindWordsFromGraphs[G4, T4]

[Graphics:HTMLFiles/GraphFoldings_234.gif]

{Word[-1, 2], Word[-1, 2, 2]}

Compute newT4 to contain the first edge of fold and find the corresponding Nielsen Transformation.  Worth noting that the first word in the new generating set has length 1 but comes from a path of length 3.  Once again this is simply due to the fact that the path is not "tight".

fold = FindPossibleFolds[G4][[1]] ;

newT4 = ChangeTree[T4, fold[[1]]] ;

ShowGraphArray[{G4, T4, newT4}, VertexNumber→True] ;

gens4 = FindWordsFromGraphs[G4, newT4] ;

trans3 = FindNielsenTrans[G4, T4, newT4] ;

Print["The fold is: ", fold] ;

Print["The new generating set is: ", gens4] ;

Print["The Nielsen Transformation induced by the changing trees is: ", trans3] ;

ComposeAuto[trans3, gens3] == gens4

[Graphics:HTMLFiles/GraphFoldings_245.gif]

The fold is:  {{{2, 3}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}, {{2, 1}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}}

The new generating set is:  {Word[2], Word[-2, 1]}

The Nielsen Transformation induced by the changing trees is:  {Word[-1, 2], Word[-1]}

True

We fold to obtain G_5 and T_5.  Although the generating set does not change (as expected) the order of the generators differs by a permutation, which we label trans4:

G5 = IdentifyEdges[G4, fold] ;

T5 = IdentifyEdges[newT4, fold] ;

ShowGraphArray[{G5, T5}, VertexNumber→True] ;

gens5 = FindWordsFromGraphs[G5, T5] ;

trans4 = {Word[2], Word[1]} ;

Print["The new generating set is: ", gens4] ;

Print["The permutation is: ", trans4] ;

ComposeAuto[trans4, gens4] == gens5

[Graphics:HTMLFiles/GraphFoldings_260.gif]

The new generating set is:  {Word[2], Word[-2, 1]}

The permutation is:  {Word[2], Word[1]}

True

The only remaining possible fold identifies the loop at the basepoint with the remaining green edge.  

fold = FindPossibleFolds[G5][[1]] ;

G6 = IdentifyEdges[G5, fold] ;

T6 = MakeDirected[EmptyGraph[1]] ;

ShowGraph[G6] ;

FindWordsFromGraphs[G6, T6]

[Graphics:HTMLFiles/GraphFoldings_269.gif]

{Word[2], Word[1]}

The graph G_6 is Completely Folded, and is the Core of the covering space corresponding to H.  Note this is precisely isomorphic to G.  This means that the subgroup H above actually generates the entire group F_2.  So a set of words generates the entire group if and only if the last step of this algorithm is G.

3. Automorphisms of Free Groups

A set of n words in F_n define an endomorphism of F_n.  If {W_1,...,W_n} is set of words in a free group of rank n, then the map X_1W_1,...,X_nW_n defines an enomorphism of F_n, and if the set of words actually generates all of F_n, then this map is an automorphism.  

The example above was a 2 element generating set for F_2, so let's consider the automorphism σ:F_2F_2 by σ(Word[1])=Word[-2,1,-2,-2,1] and σ(Word[2])=Word[-2,-2,1].  This is an automorphism because the image is all of F_2 as computed above, and we can use the above factorization to compute σ^(-1).  

***Ideally draw a big commutative diagram here- need to figure out if that's possible in mathematica***  

With each fold above, or at least anytime we changed trees, we found a Nielsen Transformation which changed the generating set.  The map σ is precisely g_0^*, and so we obtain a factorization of g_0^* as a product of the above transformations.  Recall that the original generating set differed from that found using the graph G_0 by some inverses, so we call that transformation trans0 here:
First find the inverses of each of the Nielsen Transformations found above.  The second to last generating set was itself a Nielsen Transformation, so trans5 will simply be the inverse of that.

trans0 = {Word[-1], Word[-2]} ;

invtrans0 = trans0 ;

trans1 ;

invtrans1 = trans1 ;

trans2 ;

invtrans2 = trans2 ;

trans3 ;

invtrans3 = {Word[-2], Word[-2, 1]} ;

trans4 ;

invtrans4 = trans4 ;

trans5 = {Word[2, 1], Word[2]} ;

invtrans5 = gens5 ;

Recall now each of the above following equations:

ComposeAuto[trans0, H] == gens1

ComposeAuto[trans1, gens1] == gens2

ComposeAuto[trans2, gens2] == gens3

ComposeAuto[trans3, gens3] == gens4

ComposeAuto[trans4, gens4] == gens5

ComposeAuto[trans5, gens5]

True

True

True

True

True

{Word[1], Word[2]}

We solve the above equations to obtain:

ComposeAuto[trans5, trans4, trans3, trans2, trans1, trans0, H]

{Word[1], Word[2]}

The automorphism σ is then factored as the composition of the above :

ComposeAuto[invtrans0, invtrans1, invtrans2, invtrans3, invtrans4, invtrans5] == H

True

Then we know that σ^(-1) is:

invH = ComposeAuto[trans5, trans4, trans3, trans2, trans1, trans0] ;

             -1 Print[σ   =, invH] ;

       -1 σ   =  {Word[1, -2, -2, 1, -2], Word[1, -2, -2]}

4 An Example in Rank 3

Below is an illustration of this algorithm in Rank 3.  The result is a proper rank 3 subgroup of F_3.

H = {Word[1, 2, 3], Word[-1, -2, -3, 1, 2, 3], Word[-2, -1, 2, 3]} ;

G0 = CreateStartingBouquet[H] ;

fold = FindPossibleFolds[G0][[1]] ;

G1 = IdentifyEdges[G0, fold] ;

fold = FindPossibleFolds[G1][[1]] ;

G2 = IdentifyEdges[G1, fold] ;

fold = FindPossibleFolds[G2][[1]] ;

G3 = IdentifyEdges[G2, fold] ;

fold = FindPossibleFolds[G3][[1]] ;

G4 = IdentifyEdges[G3, fold] ;

fold = FindPossibleFolds[G4][[1]] ;

G5 = IdentifyEdges[G4, fold] ;

ShowGraphArray[{{G0, G1, G2}, {G3, G4, G5}}] ;

[Graphics:HTMLFiles/GraphFoldings_337.gif]

No further folds are possible, the graph G_5is the core of the covering space corresponding to H.  The full covering space can be constructed from this core by adding infinite trees to each vertex appropriately.

5. An example which reduces perceived rank (example from Bestvina's notes)

This is an interesting example from Bestvina's notes.  The given subgroup is generated by 3 words, however there is a relation between these words.  The first 5 folds are illustrated below:

H = {Word[1, 1, 1, 2], Word[-1, 2, 1, 2], Word[1, 1, -2, 1]} ;

G0 = CreateStartingBouquet[H] ;

fold = FindPossibleFolds[G0][[1]] ;

G1 = IdentifyEdges[G0, fold] ;

fold = FindPossibleFolds[G1][[1]] ;

G2 = IdentifyEdges[G1, fold] ;

fold = FindPossibleFolds[G2][[1]] ;

G3 = IdentifyEdges[G2, fold] ;

fold = FindPossibleFolds[G3][[1]] ;

G4 = IdentifyEdges[G3, fold] ;

fold = FindPossibleFolds[G4][[1]] ;

G5 = IdentifyEdges[G4, fold] ;

ShowGraphArray[{{G0, G1, G2}, {G3, G4, G5}}] ;

[Graphics:HTMLFiles/GraphFoldings_352.gif]

Notice now that the graph G_5 has a multiple edge which can be folded.  This fold is not a homotopy equivalence, indicating that the perceived rank of is decreased to 2.  This graph is now completely folded and by choosing a geodesic tree we obtain a Nielsen Set of Generators for H.

fold = FindPossibleFolds[G5][[1]] ;

G6 = IdentifyEdges[G5, fold] ;

T6 = FindTree[G6] ;

ShowGraphArray[{G6, T6}, VertexNumber→True] ;

gens = FindWordsFromGraphs[G6, T6]

NielsenSet[gens]

[Graphics:HTMLFiles/GraphFoldings_360.gif]

{Word[1, 1, -2, 1], Word[-1, 2, 1, 2]}

True

6. Subgroups of Finite Index (Marshall Hall's Theorem)

The subgroup computed above is a proper rank 2 subgroup of F_2.  The covering space corresponding to this subgroup is constructed from this core graph by adding infinite trees to any vertex which is not locally homeomorphic to the vertex in the rose G (the single vertex in the bouquet of 2 cirlces) , i.e. to any vertex of valence smaller than 4 an infinite tree is added.   We can find a finite index subgroup by using this core and adding edges until the graph is regular, that is until each vertex has valence 4 with exactly one edge in and out for each word.

G7 = AddEdge[G6, {{3, 2}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}] ;

G8 = AddEdge[G7, {{2, 4}, EdgeLabel→Word[1], EdgeColor→RGBColor[1, 0, 0]}] ;

G9 = AddEdge[G8, {{5, 4}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}] ;

G10 = AddEdge[G9, {{1, 1}, EdgeLabel→Word[2], EdgeColor→RGBColor[0, 1, 0]}] ;

ShowGraphArray[{{G6, G7, G8}, {G9, G10}}, VertexNumber→True] ;

[Graphics:HTMLFiles/GraphFoldings_369.gif]

Note the graph G_10 is now a finite cover of the rose G, and hence corresponds to a finite index subgroup.  We show below that this graph is regular, and find a generating set.  This is a rank 6 subgroup containing H, and has index 5 which is equal to the number of vertices of G_10, i.e. this is a 5 sheeted cover of G.  Note of course that this subgroup is not unique- there are other subgroups of finite index containing H, and in fact we could compute the number of such subgroups by simply computing the number of ways we could add edges to G_6 to obtain a regular graph.  

RegularQ[G10]

T = FindTree[G10] ;

ShowGraphArray[{G10, T}, VertexNumber→True] ;

gens = FindWordsFromGraphs[G10, T] ;

Print["This subgroup of index 5 has rank 6 and is generated by: ", gens] ;

True

[Graphics:HTMLFiles/GraphFoldings_379.gif]

This subgroup of index 5 has rank 6 and is generated by:  {Word[1, 1, -2, 1], Word[-1, 2, 1, 2], Word[-1, 2, 2, 2], Word[-2, 1, 1], Word[2, 1], Word[1, 2, -1]}

References:

Bestvina, Malden, Folding graphs and aplications, d'apres Stallings, Fall 2001 Class Notes

Kapovich, Ilya and Myasnikov, Alexei, Stallings Foldings and Subgroups of Free Groups, Journal of Algebra 248, 608-668 (2002).

Lyndon & Schupp, "Combinatorial Group Theory", Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin Heidelberg New York 1977

Magnus, Karass, Solitar, "Combinatorial Group Theory", rev ed., Dover, New York, 1976.

Pemmaraju S. & Skiena S., "Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica", Cambridge University Press 2003

Stallings, J.R., Topology of finite graphs,  Inventiones mathematicae 71, No 3 (1983), 551-565


Created by Mathematica  (May 18, 2007) Valid XHTML 1.1!