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.

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.

1) Setup Starting Graphs

A free group of rank n is the fundamental group of the one point union of n circles.  Let =<,...> be a free set of generators and we will identify with a graph G that is simply the wedge of n circles.  Let {,...,} 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 induces a morphism of a bouquet of k circles into G which we now describe.  
Begin by creating a circle which will correspond to .  Subdivide this circle into || edges.  Choose a vertex in this graph to be a basepoint, and label each edge by the generators in .  For example:   

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 , 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 whose image inside is the subgroup generated by .  Repeat this procedure for each , 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 .  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.  The image of the induced map on is precisely H, i.e (())=H.  We illustrate with the example below:

This graph can be used to identify a generating set for H.  To do this, we choose a spanning tree inside .  For each edge e in -, there is a unique loop in containing e which is determined as follows.  There is a unique path in from the basepoint to the initial vertex of e, and a unique path from the terminal vertex of e to the basepoint.  Construct the loop that is the composition of , then e, then .  This is a based loop in , 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 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.  

2. Graph Foldings (Stallings Algorithm)

The graph described above defines a morphism :→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 and 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 and .  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 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 .  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 , and hence after folding, the image of π_1 will remain unchanged.

The above function has identified 2 potential folds of .  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 .  The graph yields a map :→G by identifying edges which commutes with the folding map →.

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 .
Next we need to find the induced quotient graph .  Similar to above this determines a generating set for the subgroup H.

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

Lemma: Let be a graph and ⊂ a tree.  Let f:→be a fold, which restricts to a fold of .  This simply means that both edges to be identified in the fold are contained in .  Then each edge in the complement of has an image which is in the complement of of .  Each such edge determines a loop in as described above.  This loop and its image in in
are directed and labeled identically, and hence determine the same generator in .

Now look for possible folds of to obtain .  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 .

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.

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.

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={,...,} of words in , 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 is mapped either to or , and all other are mapped to one of:
    
    
    
    

*****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.

We now fold 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:

Fold Again. This time the second edge to be folded is not in the tree , 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 to obtain .  The gererating set remains the same:

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

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

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".

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

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

The graph 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 .  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 define an endomorphism of .  If {,...,} is set of words in a free group of rank n, then the map →,...,→ defines an enomorphism of , and if the set of words actually generates all of , then this map is an automorphism.  

The example above was a 2 element generating set for , so let's consider the automorphism σ:→ 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 as computed above, and we can use the above factorization to compute .  

***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 , and so we obtain a factorization of as a product of the above transformations.  Recall that the original generating set differed from that found using the graph 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.

Recall now each of the above following equations:

We solve the above equations to obtain:

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

Then we know that is:

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 .

No further folds are possible, the graph is 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:

Notice now that the graph 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.

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

The subgroup computed above is a proper rank 2 subgroup of .  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.

Note the graph 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 , 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 to obtain a regular graph.  

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)