<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <title>GAP (Gpd) - Chapter 6: Graphs of Groups and Groupoids</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8" /> <meta name="generator" content="GAPDoc2HTML" /> <link rel="stylesheet" type="text/css" href="manual.css" /> </head> <body> <div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div> <div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div> <p><a id="X78063DC8847554B4" name="X78063DC8847554B4"></a></p> <div class="ChapSects"><a href="chap6.html#X78063DC8847554B4">6 <span class="Heading">Graphs of Groups and Groupoids</span></a> <div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7D554C5D7FDC3D02">6.1 <span class="Heading">Digraphs</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X85BD6D2584D8A22F">6.1-1 FpWeightedDigraph</a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7BAFCA3680E478AE">6.2 <span class="Heading">Graphs of Groups</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8130246E854BC5D9">6.2-1 GraphOfGroups</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X847464677F641527">6.2-2 IsGraphOfFpGroups</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B036C2B84E48BB1">6.2-3 RightTransversalsOfGraphOfGroups</a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7BD9DCF87FB3E0AF">6.3 <span class="Heading">Words in a Graph of Groups and their normal forms</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X87937AE47C5B1018">6.3-1 GraphOfGroupsWord</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X78FA7C3F831AA6E4">6.3-2 ReducedGraphOfGroupsWord</a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X7D99A7B37B36BAA8">6.4 <span class="Heading">Free products with amalgamation and HNN extensions</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X795AB71F7E370119">6.4-1 FreeProductWithAmalgamation</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7CB0F120804A8DED">6.4-2 HnnExtension</a></span> </div> <div class="ContSect"><span class="nocss"> </span><a href="chap6.html#X78108FB4814AE887">6.5 <span class="Heading">GraphsOfGroupoids and their Words</span></a> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8739267678808E85">6.5-1 GraphOfGroupoids</a></span> <span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EC1A9067FC91255">6.5-2 GraphOfGroupoidsWord</a></span> </div> </div> <h3>6 <span class="Heading">Graphs of Groups and Groupoids</span></h3> <p>This package was originally designed to implement <em>graphs of groups</em>, a notion introduced by Serre in <a href="chapBib.html#biBSerre">[Ser80]</a>. It was only when this was extended to <em>graphs of groupoids</em> that the functions for groupoids, described in the previous chapters, were required. The methods described here are based on Philip Higgins' paper <a href="chapBib.html#biBHiJLMS">[Hig76]</a>. For further details see Chapter 2 of <a href="chapBib.html#biBemma-thesis">[Moo01]</a>. 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.</p> <p><a id="X7D554C5D7FDC3D02" name="X7D554C5D7FDC3D02"></a></p> <h4>6.1 <span class="Heading">Digraphs</span></h4> <p><a id="X85BD6D2584D8A22F" name="X85BD6D2584D8A22F"></a></p> <h5>6.1-1 FpWeightedDigraph</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FpWeightedDigraph</code>( <var class="Arg">verts, arcs</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFpWeightedDigraph</code>( <var class="Arg">dig</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> InvolutoryArcs</code>( <var class="Arg">dig</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <p>A <em>weighted digraph</em> is a record with two components: <em>vertices</em>, which are usually taken to be positive integers (to distinguish them from the objects in a groupoid); and <em>arcs</em>, which take the form of 3-element lists <code class="code">[weight,tail,head]</code>. The <em>tail</em> and <em>head</em> are the two vertices of the arc. The <em>weight</em> is taken to be an element of a finitely presented group, so as to produce digraphs of type <code class="code">IsFpWeightedDigraph</code>.</p> <table class="example"> <tr><td><pre> gap> V1 := [ 5, 6 ];; gap> f1 := FreeGroup( "y" );; gap> y := f1.1;; gap> A1 := [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]; gap> D1 := FpWeightedDigraph( V1, A1 ); weighted digraph with vertices: [ 5, 6 ] and arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ] gap> inv1 := InvolutoryArcs( D1 ); [ 2, 1 ] </pre></td></tr></table> <p>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 <code class="code">[y,5,6]</code> as the data and get the function to construct the reverse edge. The attribute <code class="code">InvolutoryArcs</code> 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.</p> <table class="example"> <tr><td><pre> gap> f3 := FreeGroup( 3, "z" );; gap> z1 := f3.1;; z2 := f3.2;; z3 := f3.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( 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 ] </pre></td></tr></table> <p><a id="X7BAFCA3680E478AE" name="X7BAFCA3680E478AE"></a></p> <h4>6.2 <span class="Heading">Graphs of Groups</span></h4> <p><a id="X8130246E854BC5D9" name="X8130246E854BC5D9"></a></p> <h5>6.2-1 GraphOfGroups</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroups</code>( <var class="Arg">dig, gps, sgps, isos</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DigraphOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GroupsOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SubgroupsOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsomorphismsOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <p>A graph of groups is traditionally defined as consisting of:</p> <ul> <li><p>a digraph with involutory pairs of arcs;</p> </li> <li><p>a <em>vertex group</em> associated to each vertex;</p> </li> <li><p>a group associated to each pair of arcs;</p> </li> <li><p>an injective homomorphism from each arc group to the group at the head of the arc.</p> </li> </ul> <p>We have found it more convenient to associate to each arc:</p> <ul> <li><p>a subgroup of the vertex group at the tail;</p> </li> <li><p>a subgroup of the vertex group at the head;</p> </li> <li><p>an isomorphism between these subgroups, such that each involutory pair of arcs determines inverse isomorphisms.</p> </li> </ul> <p>These two viewpoints are clearly equivalent.</p> <p>In this implementation we require that all subgroups are of finite index in the vertex groups.</p> <p>The four attributes provide a means of calling the four items of data in the construction of a graph of groups.</p> <p>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 <code class="code">D1</code> 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.</p> <table class="example"> <tr><td><pre> 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], [hy,hybar], [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 ] subgroups: [ hy, hybar ] isomorphisms: [ [ [ a^3 ], [ b^2 ] ], [ [ b^2 ], [ a^3 ] ] ] </pre></td></tr></table> <p><a id="X847464677F641527" name="X847464677F641527"></a></p> <h5>6.2-2 IsGraphOfFpGroups</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfFpGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfPcGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfPermGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div> <p>This is a list of properties to be expected of a graph of groups. In principle any type of group known to <strong class="pkg">GAP</strong> may be used as vertex groups, though these types are not normally mixed in a single structure.</p> <table class="example"> <tr><td><pre> gap> IsGraphOfFpGroups( G1 ); true gap> IsomorphismsOfGraphOfGroups( G1 ); [ [ a^3 ] -> [ b^2 ], [ b^2 ] -> [ a^3 ] ] </pre></td></tr></table> <p><a id="X7B036C2B84E48BB1" name="X7B036C2B84E48BB1"></a></p> <h5>6.2-3 RightTransversalsOfGraphOfGroups</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RightTransversalsOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LeftTransversalsOfGraphOfGroups</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <p>Computation with graph of groups words will require, for each arc subgroup <code class="code">ha</code>, a set of representatives for the left cosets of <code class="code">ha</code> in the tail vertex group. As already pointed out, we require subgroups of finite index. Since <strong class="pkg">GAP</strong> prefers to provide right cosets, we obtain the right representatives first, and then invert them.</p> <p>When the vertex groups are of type <code class="code">FpGroup</code> 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 <strong class="pkg">GAP</strong> library, (e.g. <code class="code">IsomorphismFpSemigroup</code>).</p> <table class="example"> <tr><td><pre> gap> RTG1 := RightTransversalsOfGraphOfGroups( G1 ); [ [ <identity ...>, a, a^2 ], [ <identity ...>, b ] ] gap> LTG1 := LeftTransversalsOfGraphOfGroups( G1 ); [ [ <identity ...>, a^-1, a^-2 ], [ <identity ...>, b^-1 ] ] </pre></td></tr></table> <p><a id="X7BD9DCF87FB3E0AF" name="X7BD9DCF87FB3E0AF"></a></p> <h4>6.3 <span class="Heading">Words in a Graph of Groups and their normal forms</span></h4> <p><a id="X87937AE47C5B1018" name="X87937AE47C5B1018"></a></p> <h5>6.3-1 GraphOfGroupsWord</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroupsWord</code>( <var class="Arg">gg, tv, list</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroupsOfWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordOfGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GGTail</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GGHead</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <p>If <code class="code">G</code> is a graph of groups with underlying digraph <code class="code">D</code>, the following groupoids may be considered. First there is the free groupoid or path groupoid on <code class="code">D</code>. Since we want each involutory pair of arcs to represent inverse elements in the groupoid, we quotient out by the relations <code class="code">y\^{}-1 = ybar</code> to obtain <code class="code">PG(D)</code>. Secondly, there is the discrete groupoid <code class="code">VG(D)</code>, namely the union of all the vertex groups. Since these two groupoids have the same object set (the vertices of <code class="code">D</code>) we can form <code class="code">A(G)</code>, the free product of <code class="code">PG(D)</code> and <code class="code">VG(D)</code> amalgamated over the vertices. For further details of this universal groupoid construction see <a href="chapBib.html#biBemma-thesis">[Moo01]</a>. (Note that these groupoids are not implemented in this package.)</p> <p>An element of <code class="code">A(G)</code> 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 <code class="code">D</code>; 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.</p> <p>The attributes <code class="code">GGTail</code> and <code class="code">GGHead</code> are <em>temporary</em> names for the tail and head of a graph of groups word, and are likely to be replaced in future versions.</p> <p>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.</p> <p>In the following example, where <code class="code">gw1</code> is a word in the trefoil graph of groups, the y_i are specified by their positions in <code class="code">A1</code>. Both arcs are traversed twice, so the resulting word is a loop at vertex 5.</p> <table class="example"> <tr><td><pre> 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 ] </pre></td></tr></table> <p><a id="X78FA7C3F831AA6E4" name="X78FA7C3F831AA6E4"></a></p> <h5>6.3-2 ReducedGraphOfGroupsWord</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ReducedGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsReducedGraphOfGroupsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div> <p>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 <code class="code">[yi, identity, yibar]</code> 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 <a href="chapBib.html#biBemma-thesis">[Moo01]</a>.</p> <p>The reduction of the word <code class="code">gw1</code> in our example includes one length reduction. The four stages of the reduction are as follows:</p> <p class="pcenter"> 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}. </p> <table class="example"> <tr><td><pre> gap> nw1 := ReducedGraphOfGroupsWord( gw1 ); (5)a^-1.y.b^-1.y^-1.a^10(5) </pre></td></tr></table> <p><a id="X7D99A7B37B36BAA8" name="X7D99A7B37B36BAA8"></a></p> <h4>6.4 <span class="Heading">Free products with amalgamation and HNN extensions</span></h4> <p><a id="X795AB71F7E370119" name="X795AB71F7E370119"></a></p> <h5>6.4-1 FreeProductWithAmalgamation</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FreeProductWithAmalgamation</code>( <var class="Arg">gp1, gp2, iso</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFpaGroup</code>( <var class="Arg">fpa</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroupsRewritingSystem</code>( <var class="Arg">fpa</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NormalFormGGRWS</code>( <var class="Arg">fpa, word</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <p>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.</p> <p>When <code class="code">gp1</code> and <code class="code">gp2</code> are fp-groups, the operation <code class="code">FreeProductWithAmalgamation</code> constructs the required fp-group. When the two groups are permutation groups, the <code class="code">IsomorphismFpGroup</code> operation is called on both <code class="code">gp1</code> and <code class="code">gp2</code>, and the resulting isomorphism is transported to one between the two new subgroups.</p> <p>The attribute <code class="code">GraphOfGroupsRewritingSystem</code> of <code class="code">fpa</code> is the graph of groups which has underlying digraph <code class="code">D1</code>, 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 <em>do not</em> belong to the category <code class="code">IsRewritingSystem</code>. This anomaly may be dealt with when time permits.</p> <p>The example below shows a computation in the the free product of the symmetric <code class="code">s3</code> and the alternating <code class="code">a4</code>, amalgamated over a cyclic subgroup <code class="code">c3</code>.</p> <table class="example"> <tr><td><pre> gap> ## set up the first group s3 and a subgroup c3=<a1> gap> f1 := FreeGroup( 2, "a" );; gap> rel1 := [ f1.1^3, f1.2^2, (f1.1*f1.2)^2 ];; gap> s3 := f1/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*fa1*fa2, fa3^3, fa4^3, fa3*fa4*fa3*fa4, 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 ] subgroups: [ Group( [ a1 ] ), Group( [ b1 ] ) ] 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 := GeneratorsOfGraphOfGroups( fpa );; gap> w2 := (gfpa[1]*gfpa[2]*gfpa[3]^gfpa[4])^3; fa1*fa2*fa4^-1*fa3*fa4*fa1*fa2*fa4^-1*fa3*fa4*fa1*fa2*fa4^-1*fa3*fa4 gap> n2 := NormalFormGGRWS( fpa, w2 ); fa2*fa3*fa4^-1*fa2*fa4^-1*fa2*fa3^-1*fa4*fa3^-1 </pre></td></tr></table> <p><a id="X7CB0F120804A8DED" name="X7CB0F120804A8DED"></a></p> <h5>6.4-2 HnnExtension</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HnnExtension</code>( <var class="Arg">gp, iso</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsHnnGroup</code>( <var class="Arg">hnn</var> )</td><td class="tdright">( property )</td></tr></table></div> <p>For <em>HNN extensions</em>, the appropriate graph of groups has underlying digraph with just one vertex and one pair of loops, weighted with <code class="code">FpGroup</code> generators z,z^-1. There is one vertex group <code class="code">G</code>, two isomorphic subgroups <code class="code">H1,H2</code> of <code class="code">G</code>, with the isomorphism and its inverse on the loops. The presentation of the extension has one more generator than that of <code class="code">G</code> and corresponds to the generator z.</p> <p>The functions <code class="code">GraphOfGroupsRewritingSystem</code> and <code class="code">NormalFormGGRWS</code> may be applied to hnn-groups as well as to fpa-groups.</p> <p>In the example we take <code class="code">G=a4</code> and the two subgroups are cyclic groups of order 3.</p> <table class="example"> <tr><td><pre> 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*fe1*fe3*fe2^2*fe3*fe2 gap> n3 := NormalFormGGRWS( hnn, w3 ); fe2*fe1*fe3*fe2*fe1*fe3 </pre></td></tr></table> <p>Both fpa-groups and hnn-groups are provided with a record attribute, <code class="code">FpaInfo(fpa)</code> and <code class="code">HnnInfo(hnn)</code> respectively, storing the groups and isomorphisms involved in their construction.</p> <table class="example"> <tr><td><pre> 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 ] ) </pre></td></tr></table> <p><a id="X78108FB4814AE887" name="X78108FB4814AE887"></a></p> <h4>6.5 <span class="Heading">GraphsOfGroupoids and their Words</span></h4> <p><a id="X8739267678808E85" name="X8739267678808E85"></a></p> <h5>6.5-1 GraphOfGroupoids</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroupoids</code>( <var class="Arg">dig, gpds, subgpds, isos</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfPermGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfFpGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GroupoidsOfGraphOfGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DigraphOfGraphOfGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SubgroupoidsOfGraphOfGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsomorphismsOfGraphOfGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> RightTransversalsOfGraphOfGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LefvtTransversalsOfGraphOfGroupoids</code>( <var class="Arg">gg</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <p>Graphs of groups generalise naturally to graphs of groupoids, forming the class <code class="code">IsGraphOfGroupoids</code>. 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.</p> <p>The example below generalises the trefoil group example in subsection 4.4.1, taking at each vertex of <code class="code">D1</code> a two-object groupoid with a free group on one generator, and full subgroupoids with groups < a^3 > and < b^2 >.</p> <table class="example"> <tr><td><pre> gap> Gfa := SinglePieceGroupoid( [-2,-1], fa );; gap> ofa := One( fa );; gap> SetName( Gfa, "Gfa" ); gap> Uhy := Subgroupoid( Gfa, [ [[-2,-1], hy ] ] );; gap> SetName( Uhy, "Uhy" ); gap> Gfb := SinglePieceGroupoid( [-4,-3], fb );; 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 mapping : Uhy -> Uhybar, groupoid mapping : Uhybar -> Uhy ] </pre></td></tr></table> <p><a id="X7EC1A9067FC91255" name="X7EC1A9067FC91255"></a></p> <h5>6.5-2 GraphOfGroupoidsWord</h5> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroupoidsWord</code>( <var class="Arg">gg, tv, list</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsGraphOfGroupoidsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GraphOfGroupoidsOfWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WordOfGraphOfGroupoidsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( attribute )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ReducedGraphOfGroupoidsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( operation )</td></tr></table></div> <div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsReducedGraphOfGroupoidsWord</code>( <var class="Arg">w</var> )</td><td class="tdright">( property )</td></tr></table></div> <p>Having produced the graph of groupoids <code class="code">gg3</code>, we may construct left coset representatives; choose a graph of groupoids word; and reduce this to normal form. Compare the <code class="code">nw3</code> below with the normal form <code class="code">nw1</code> in subsection 4.3.2.</p> <table class="example"> <tr><td><pre> gap> f1 := GroupoidElement( Gfa, a^7, -1, -2);; gap> f2 := GroupoidElement( Gfb, b^-6, -4, -4 );; gap> f3 := GroupoidElement( Gfa, a^-11, -2, -1 );; gap> f4 := GroupoidElement( Gfb, b^9, -3, -4 );; gap> f5 := GroupoidElement( 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) </pre></td></tr></table> <p>More examples of these operations may be found in the example file <code class="file">gpd/examples/ggraph.g</code>.</p> <div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap5.html">Previous Chapter</a> <a href="chap7.html">Next Chapter</a> </div> <div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div> <hr /> <p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p> </body> </html>