Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

6 Graphs of Groups and Groupoids
 6.1 Digraphs
 6.2 Graphs of Groups
 6.3 Words in a Graph of Groups and their normal forms
 6.4 Free products with amalgamation and HNN extensions
 6.5 GraphsOfGroupoids and their Words

6 Graphs of Groups and Groupoids

This package was originally designed to implement graphs of groups, a notion introduced by Serre in [Ser80]. It was only when this was extended to graphs of groupoids that the functions for groupoids, described in the previous chapters, were required. The methods described here are based on Philip Higgins' paper [Hig76]. For further details see Chapter 2 of [Moo01]. Since a graph of groups involves a directed graph, with a group associated to each vertex and arc, we first define digraphs with edges weighted by the generators of a free group.

6.1 Digraphs

6.1-1 FpWeightedDigraph
‣ FpWeightedDigraph( verts, arcs )( attribute )
‣ IsFpWeightedDigraph( dig )( attribute )
‣ InvolutoryArcs( dig )( attribute )

A weighted digraph is a record with two components: vertices, which are usually taken to be positive integers (to distinguish them from the objects in a groupoid); and arcs, which take the form of 3-element lists [weight,tail,head]. The tail and head are the two vertices of the arc. The weight is taken to be an element of a finitely presented group, so as to produce digraphs of type IsFpWeightedDigraph.


gap> V1 := [ 5, 6 ];;
gap> fg1 := FreeGroup( "y" );;
gap> y := fg1.1;;
gap> A1 := [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ];
gap> D1 := FpWeightedDigraph( fg1, V1, A1 );
weighted digraph with vertices: [ 5, 6 ]
and arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
gap> inv1 := InvolutoryArcs( D1 );
[ 2, 1 ]

The example illustrates the fact that we require arcs to be defined in involutory pairs, as though they were inverse elements in a groupoid. We may in future decide just to give [y,5,6] as the data and get the function to construct the reverse edge. The attribute InvolutoryArcs returns a list of the positions of each inverse arc in the list of arcs. In the second example the graph is a complete digraph on three vertices.


gap> fg3 := FreeGroup( 3, "z" );;
gap> z1 := fg3.1;;  z2 := fg3.2;;  z3 := fg3.3;;
gap> V3 := [ 7, 8, 9 ];;
gap> A3 := [[z1,7,8],[z2,8,9],[z3,9,7],[z1^-1,8,7],[z2^-1,9,8],[z3^-1,7,9]];;
gap> D3 := FpWeightedDigraph( fg3, V3, A3 );
weighted digraph with vertices: [ 7, 8, 9 ]
and arcs: [ [ z1, 7, 8 ], [ z2, 8, 9 ], [ z3, 9, 7 ], [ z1^-1, 8, 7 ],
  [ z2^-1, 9, 8 ], [ z3^-1, 7, 9 ] ]
[gap> inv3 := InvolutoryArcs( D3 );
[ 4, 5, 6, 1, 2, 3 ]

6.2 Graphs of Groups

6.2-1 GraphOfGroups
‣ GraphOfGroups( dig, gps, isos )( operation )
‣ DigraphOfGraphOfGroups( gg )( attribute )
‣ GroupsOfGraphOfGroups( gg )( attribute )
‣ IsomorphismsOfGraphOfGroups( gg )( attribute )

A graph of groups is traditionally defined as consisting of:

We have found it more convenient to associate to each arc:

These two viewpoints are clearly equivalent.

In this implementation we require that all subgroups are of finite index in the vertex groups.

The three attributes provide a means of calling the three items of data in the construction of a graph of groups.

We shall be representing free products with amalgamation of groups and HNN extensions of groups, so we take as our first example the trefoil group with generators a,b and relation a^3=b^2. For this we take digraph D1 above with an infinite cyclic group at each vertex, generated by a and b respectively. The two subgroups will be generated by a^3 and b^2 with the obvious isomorphisms.


gap> ## free vertex group at 5
gap> fa := FreeGroup( "a" );;
gap> a := fa.1;;
gap> SetName( fa, "fa" );
gap> hy := Subgroup( fa, [a^3] );;
gap> SetName( hy, "hy" );
gap> ## free vertex group at 6
gap> fb := FreeGroup( "b" );;
gap> b := fb.1;;
gap> SetName( fb, "fb" );
gap> hybar := Subgroup( fb, [b^2] );;
gap> SetName( hybar, "hybar" );
gap> ## isomorphisms between subgroups
gap> homy := GroupHomomorphismByImagesNC( hy, hybar, [a^3], [b^2] );;
gap> homybar := GroupHomomorphismByImagesNC( hybar, hy, [b^2], [a^3] );;
gap> ## defining graph of groups G1
gap> G1 := GraphOfGroups( D1, [fa,fb], [homy,homybar] );
Graph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ]
gap> Display( G1 );
Graph of Groups with :-
    vertices: [ 5, 6 ]
        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
      groups: [ fa, fb ]
isomorphisms: [ [ [ a^3 ], [ b^2 ] ], [ [ b^2 ], [ a^3 ] ] ]

6.2-2 IsGraphOfFpGroups
‣ IsGraphOfFpGroups( gg )( property )
‣ IsGraphOfPcGroups( gg )( property )
‣ IsGraphOfPermGroups( gg )( property )

This is a list of properties to be expected of a graph of groups. In principle any type of group known to GAP may be used as vertex groups, though these types are not normally mixed in a single structure.


gap> IsGraphOfFpGroups( G1 );
true
gap> IsomorphismsOfGraphOfGroups( G1 );
[ GroupHomomorphismByImages( hy, hybar, [ a^3 ], [ b^2 ] ), 
  GroupHomomorphismByImages( hybar, hy, [ b^2 ], [ a^3 ] ) ]


6.2-3 RightTransversalsOfGraphOfGroups
‣ RightTransversalsOfGraphOfGroups( gg )( attribute )
‣ LeftTransversalsOfGraphOfGroups( gg )( attribute )

Computation with graph of groups words will require, for each arc subgroup ha, a set of representatives for the left cosets of ha in the tail vertex group. As already pointed out, we require subgroups of finite index. Since GAP prefers to provide right cosets, we obtain the right representatives first, and then invert them.

When the vertex groups are of type FpGroup we shall require normal forms for these groups, so we assume that such vertex groups are provided with Knuth Bendix rewriting systems using functions from the main GAP library, (e.g. IsomorphismFpSemigroup).


gap> RTG1 := RightTransversalsOfGraphOfGroups( G1 );
[ [ <identity ...>, a, a^2 ], [ <identity ...>, b ] ]
gap> LTG1 := LeftTransversalsOfGraphOfGroups( G1 );
[ [ <identity ...>, a^-1, a^-2 ], [ <identity ...>, b^-1 ] ] 

6.3 Words in a Graph of Groups and their normal forms

6.3-1 GraphOfGroupsWord
‣ GraphOfGroupsWord( gg, tv, list )( operation )
‣ IsGraphOfGroupsWord( w )( property )
‣ GraphOfGroupsOfWord( w )( attribute )
‣ WordOfGraphOfGroupsWord( w )( attribute )
‣ GGTail( w )( attribute )
‣ GGHead( w )( attribute )

If G is a graph of groups with underlying digraph D, the following groupoids may be considered. First there is the free groupoid or path groupoid on D. Since we want each involutory pair of arcs to represent inverse elements in the groupoid, we quotient out by the relations y^-1 = ybar to obtain PG(D). Secondly, there is the discrete groupoid VG(D), namely the union of all the vertex groups. Since these two groupoids have the same object set (the vertices of D) we can form A(G), the free product of PG(D) and VG(D) amalgamated over the vertices. For further details of this universal groupoid construction see [Moo01]. (Note that these groupoids are not implemented in this package.)

An element of A(G) is a graph of groups word which may be represented by a list of the form w = [g_1,y_1,g_2,y_2,...,g_n,y_n,g_n+1]. Here each y_i is an arc of D; the head of y_i-1 is a vertex v_i which is also the tail of y_i; and g_i is an element of the vertex group at v_i.

The attributes GGTail and GGHead are temporary names for the tail and head of a graph of groups word, and are likely to be replaced in future versions.

So a graph of groups word requires as data the graph of groups; the tail vertex for the word; and a list of arcs and group elements. We may specify each arc by its position in the list of arcs.

In the following example, where gw1 is a word in the trefoil graph of groups, the y_i are specified by their positions in A1. Both arcs are traversed twice, so the resulting word is a loop at vertex 5.


gap> L1 := [ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ];;
gap> gw1 := GraphOfGroupsWord( G1, 5, L1 );
(5)a^7.y.b^-6.y^-1.a^-11.y.b^9.y^-1.a^7(5)
gap> IsGraphOfGroupsWord( gw1 );
true
gap> [ GGTail(gw1), GGHead(gw1) ];
[ 5, 5 ]
gap> GraphOfGroupsOfWord(gw1);
Graph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ]
gap> WordOfGraphOfGroupsWord( gw1 );
[ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ]

6.3-2 ReducedGraphOfGroupsWord
‣ ReducedGraphOfGroupsWord( w )( operation )
‣ IsReducedGraphOfGroupsWord( w )( property )

A graph of groups word may be reduced in two ways, to give a normal form. Firstly, if part of the word has the form [yi, identity, yibar] then this subword may be omitted. This is known as a length reduction. Secondly there are coset reductions. Working from the left-hand end of the word, subwords of the form [g_i,y_i,g_i+1] are replaced by [t_i,y_i,m_i(h_i)*g_i+1] where g_i = t_i*h_i is the unique factorisation of g_i as a left coset representative times an element of the arc subgroup, and m_i is the isomorphism associated to y_i. Thus we may consider a coset reduction as passing a subgroup element along an arc. The resulting normal form (if no length reductions have taken place) is then [t_1,y_1,t_2,y_2,...,t_n,y_n,k] for some k in the head group of y_n. For further details see Section 2.2 of [Moo01].

The reduction of the word gw1 in our example includes one length reduction. The four stages of the reduction are as follows:

a^7b^{-6}a^{-11}b^9a^7 ~\mapsto~ a^{-2}b^0a^{-11}b^9a^7 ~\mapsto~ a^{-13}b^9a^7 ~\mapsto~ a^{-1}b^{-8}b^9a^7 ~\mapsto~ a^{-1}b^{-1}a^{10}.


gap> nw1 := ReducedGraphOfGroupsWord( gw1 );
(5)a^-1.y.b^-1.y^-1.a^10(5)

6.4 Free products with amalgamation and HNN extensions

6.4-1 FreeProductWithAmalgamation
‣ FreeProductWithAmalgamation( gp1, gp2, iso )( operation )
‣ IsFpaGroup( fpa )( property )
‣ GraphOfGroupsRewritingSystem( fpa )( attribute )
‣ NormalFormGGRWS( fpa, word )( attribute )

As we have seen with the trefoil group example, graphs of groups can be used to obtain a normal form for free products with amalgamation G_1 *_H G_2 when G_1, G_2 both have rewrite systems, and H is of finite index in both G_1 and G_2.

When gp1 and gp2 are fp-groups, the operation FreeProductWithAmalgamation constructs the required fp-group. When the two groups are permutation groups, the IsomorphismFpGroup operation is called on both gp1 and gp2, and the resulting isomorphism is transported to one between the two new subgroups.

The attribute GraphOfGroupsRewritingSystem of fpa is the graph of groups which has underlying digraph D1, with two vertices and two arcs; the two groups as vertex groups; and the specified isomorphisms on the arcs. Despite the name, graphs of groups constructed in this way do not belong to the category IsRewritingSystem. This anomaly may be dealt with when time permits.

The example below shows a computation in the the free product of the symmetric s3 and the alternating a4, amalgamated over a cyclic subgroup c3.


gap> ## set up the first group s3 and a subgroup c3=<a1>
gap> fg2 := FreeGroup( 2, "a" );;
gap> rel1 := [ fg2.1^3, fg2.2^2, (fg2.1*fg2.2)^2 ];;
gap> s3 := fg2/rel1;;
gap> gs3 := GeneratorsOfGroup(s3);;
gap> SetName( s3, "s3" );
gap> a1 := gs3[1];;  a2 := gs3[2];;
gap> H1 := Subgroup(s3,[a1]);;
gap> ## then the second group a4 and subgroup c3=<b1>
gap> f2 := FreeGroup( 2, "b" );;
gap> rel2 := [ f2.1^3, f2.2^3, (f2.1*f2.2)^2 ];;
gap> a4 := f2/rel2;;
gap> ga4 := GeneratorsOfGroup(a4);;
gap> SetName( a4, "a4" );
gap> b1 := ga4[1];  b2 := ga4[2];;
gap> H2 := Subgroup(a4,[b1]);;
gap> ## form the isomorphism and the fpa group
gap> iso := GroupHomomorphismByImages(H1,H2,[a1],[b1]);;
gap> fpa := FreeProductWithAmalgamation( s3, a4, iso );
<fp group on the generators [ fa1, fa2, fa3, fa4 ]>
gap> RelatorsOfFpGroup( fpa );
[ fa1^3, fa2^2, (fa1*fa2)^2, fa3^3, fa4^3, (fa3*fa4)^2, fa1*fa3^-1 ]
gap> gg1 := GraphOfGroupsRewritingSystem( fpa );;
gap> Display( gg1 );
Graph of Groups with :-
    vertices: [ 5, 6 ]
        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
      groups: [ s3, a4 ]
isomorphisms: [ [ [ a1 ], [ b1 ] ], [ [ b1 ], [ a1 ] ] ]
gap> LeftTransversalsOfGraphOfGroups( gg1 );
[ [ <identity ..>, a2^-1 ], [ <identity ..>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ] ]
gap> ## choose a word in fpa and find its normal form 
gap> gfpa := GeneratorsOfGroup( fpa );;
gap> w2 := (gfpa[1]*gfpa[2]*gfpa[3]^gfpa[4])^3;
(fa1*fa2*fa4^-1*fa3*fa4)^3
gap> n2 := NormalFormGGRWS( fpa, w2 );
fa2*fa3*(fa4^-1*fa2)^2*fa4^-1*fa3


6.4-2 HnnExtension
‣ HnnExtension( gp, iso )( operation )
‣ IsHnnGroup( hnn )( property )

For HNN extensions, the appropriate graph of groups has underlying digraph with just one vertex and one pair of loops, weighted with FpGroup generators z,z^-1. There is one vertex group G, two isomorphic subgroups H1,H2 of G, with the isomorphism and its inverse on the loops. The presentation of the extension has one more generator than that of G and corresponds to the generator z.

The functions GraphOfGroupsRewritingSystem and NormalFormGGRWS may be applied to hnn-groups as well as to fpa-groups.

In the example we take G=a4 and the two subgroups are cyclic groups of order 3.


gap> H3 := Subgroup(a4,[b2]);;
gap> i23 := GroupHomomorphismByImages( H2, H3, [b1], [b2] );;
gap> hnn := HnnExtension( a4, i23 );
<fp group on the generators [ fe1, fe2, fe3 ]> 
gap> phnn := PresentationFpGroup( hnn );;
gap> TzPrint( phnn );
#I  generators: [ fe1, fe2, fe3 ]
#I  relators:
#I  1.  3  [ 1, 1, 1 ]
#I  2.  3  [ 2, 2, 2 ]
#I  3.  4  [ 1, 2, 1, 2 ]
#I  4.  4  [ -3, 1, 3, -2 ] 
gap> gg2 := GraphOfGroupsRewritingSystem( hnn );
Graph of Groups: 1 vertices; 2 arcs; groups [ a4 ]
gap> LeftTransversalsOfGraphOfGroups( gg2 );
[ [ <identity ...>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ],
  [ <identity ...>, b1^-1, b1, b2^-1*b1 ] ]
gap> gh := GeneratorsOfGroup( hnn );;
gap> w3 := (gh[1]^gh[2])*gh[3]^-1*(gh[1]*gh[3]*gh[2]^2)^2*gh[3]*gh[2];
fe2^-1*fe1*fe2*fe3^-1*(fe1*fe3*fe2^2)^2*fe3*fe2
gap> n3 := NormalFormGGRWS( hnn, w3 );
(fe2*fe1*fe3)^2

Both fpa-groups and hnn-groups are provided with a record attribute, FpaInfo(fpa) and HnnInfo(hnn) respectively, storing the groups and isomorphisms involved in their construction.


gap> fpainfo := FpaInfo( fpa );
rec( groups := [ s3, a4 ], positions := [ [ 1, 2 ], [ 3, 4 ] ],
  isomorphism := [ a1 ] -> [ b1 ] )
gap> hnninfo := HnnInfo( hnn );
rec( group := a4, isomorphism := [ b1 ] -> [ b2 ] )

6.5 GraphsOfGroupoids and their Words

6.5-1 GraphOfGroupoids
‣ GraphOfGroupoids( dig, gpds, subgpds, isos )( operation )
‣ IsGraphOfPermGroupoids( gg )( property )
‣ IsGraphOfFpGroupoids( gg )( property )
‣ GroupoidsOfGraphOfGroupoids( gg )( attribute )
‣ DigraphOfGraphOfGroupoids( gg )( attribute )
‣ SubgroupoidsOfGraphOfGroupoids( gg )( attribute )
‣ IsomorphismsOfGraphOfGroupoids( gg )( attribute )
‣ RightTransversalsOfGraphOfGroupoids( gg )( attribute )
‣ LeftTransversalsOfGraphOfGroupoids( gg )( attribute )

Graphs of groups generalise naturally to graphs of groupoids, forming the class IsGraphOfGroupoids. There is now a groupoid at each vertex and the isomorphism on an arc identifies wide subgroupoids at the tail and at the head. Since all subgroupoids are wide, every groupoid in a connected constituent of the graph has the same number of objects, but there is no requirement that the object sets are all the same.

The example below generalises the trefoil group example in subsection 4.4.1, taking at each vertex of D1 a two-object groupoid with a free group on one generator, and full subgroupoids with groups ⟨ a^3 ⟩ and ⟨ b^2 ⟩.


gap> Gfa := SinglePieceGroupoid( fa, [-2,-1] );;
gap> ofa := One( fa );;
gap> SetName( Gfa, "Gfa" );
gap> Uhy := Subgroupoid( Gfa, [ [[-2,-1], hy ] ] );;
gap> SetName( Uhy, "Uhy" );
gap> Gfb := SinglePieceGroupoid( fb, [-4,-3] );;
gap> ofb := One( fb );;
gap> SetName( Gfb, "Gfb" );
gap> Uhybar := Subgroupoid( Gfb, [ [[-4,-3], hybar ] ] );;
gap> SetName( Uhybar, "Uhybar" );
gap> mory := GroupoidMappingOfSinglePieces( 
gap>      Uhy, Uhybar, homy, [-4,-3], [ofb,ofb] );;
gap> morybar := GroupoidMappingOfSinglePieces( 
gap>      Uhybar, Uhy, homybar, [-2,-1], [ofa,ofa] );;
gap> gg3 := GraphOfGroupoids( D1, [Gfa,Gfb], [Uhy,Uhybar], [mory,morybar] );;
gap> Display( gg3 );
Graph of Groupoids with :- 
    vertices: [ 5, 6 ]
        arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
   groupoids: 
fp single piece groupoid: Gfa
  objects: [ -2, -1 ]
    group: fa = <[ a ]>
fp single piece groupoid: Gfb
  objects: [ -4, -3 ]
    group: fb = <[ b ]>
subgroupoids: single piece groupoid: Uhy
  objects: [ -2, -1 ]
    group: hy = <[ a^3 ]>
single piece groupoid: Uhybar
  objects: [ -4, -3 ]
    group: hybar = <[ b^2 ]>
isomorphisms: [ groupoid homomorphism : Uhy -> Uhybar
    [ [ GroupHomomorphismByImages( hy, hybar, [ a^3 ], [ b^2 ] ), [ -4, -3 ], 
          [ <identity ...>, <identity ...> ] ] ], 
  groupoid homomorphism : Uhybar -> Uhy
    [ [ GroupHomomorphismByImages( hybar, hy, [ b^2 ], [ a^3 ] ), [ -2, -1 ], 
          [ <identity ...>, <identity ...> ] ] ] ]

6.5-2 GraphOfGroupoidsWord
‣ GraphOfGroupoidsWord( gg, tv, list )( operation )
‣ IsGraphOfGroupoidsWord( w )( property )
‣ GraphOfGroupoidsOfWord( w )( attribute )
‣ WordOfGraphOfGroupoidsWord( w )( attribute )
‣ ReducedGraphOfGroupoidsWord( w )( operation )
‣ IsReducedGraphOfGroupoidsWord( w )( property )

Having produced the graph of groupoids gg3, we may construct left coset representatives; choose a graph of groupoids word; and reduce this to normal form. Compare the nw3 below with the normal form nw1 in subsection 4.3.2.


gap> f1 := Arrow( Gfa, a^7, -1, -2);;
gap> f2 := Arrow( Gfb, b^-6, -4, -4 );;
gap> f3 := Arrow( Gfa, a^-11, -2, -1 );;
gap> f4 := Arrow( Gfb, b^9, -3, -4 );;
gap> f5 := Arrow( Gfa, a^7, -2, -1 );;
gap> L3 := [ f1, 1, f2, 2, f3, 1, f4, 2, f5 ];
[ [a^7 : -1 -> -2], 1, [b^-6 : -4 -> -4], 2, [a^-11 : -2 -> -1], 1, 
  [b^9 : -3 -> -4], 2, [a^7 : -2 -> -1] ]
gap> gw3 := GraphOfGroupoidsWord( gg3, 5, L3);
(5)[a^7 : -1 -> -2].y.[b^-6 : -4 -> -4].y^-1.[a^-11 : -2 -> -1].y.[b^9 : 
-3 -> -4].y^-1.[a^7 : -2 -> -1](5)
gap> nw3 := ReducedGraphOfGroupoidsWord( gw3 );
(5)[a^-1 : -1 -> -2].y.[b^-1 : -4 -> -4].y^-1.[a^10 : -2 -> -1](5)

More examples of these operations may be found in the example file gpd/examples/ggraph.g.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

generated by GAPDoc2HTML