<?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>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
1577
