|
|
|
|
Quelle chap7_mj.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/groupoids/doc/chap7_mj.html |
 |
<?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>
< script type= "text/javascript"
src= "https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (groupoids) - Chapter 7: 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" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap7" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap6_mj.html">[Previous Chapter]</a> <a href="chap8_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap7.html">[MathJax off]</a></p>
<p><a id="X78063DC8847554B4" name="X78063DC8847554B4"></a></p>
<div class="ChapSects"><a href="chap7_mj.html#X78063DC8847554B4">7 <span class="Heading">Graphs of Groups and Groupoids</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7_mj.html#X7D554C5D7FDC3D02">7.1 <span class="Heading">Digraphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X85BD6D2584D8A22F">7.1-1 FpWeightedDigraph</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7_mj.html#X7BAFCA3680E478AE">7.2 <span class="Heading">Graphs of Groups</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X8130246E854BC5D9">7.2-1 GraphOfGroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X847464677F641527">7.2-2 IsGraphOfFpGroups</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X7B036C2B84E48BB1">7.2-3 RightTransversalsOfGraphOfGroups</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7_mj.html#X7BD9DCF87FB3E0AF">7.3 <span class="Heading">Words in a Graph of Groups and their normal forms</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X87937AE47C5B1018">7.3-1 GraphOfGroupsWord</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X78FA7C3F831AA6E4">7.3-2 ReducedGraphOfGroupsWord</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7_mj.html#X7D99A7B37B36BAA8">7.4 <span class="Heading">Free products with amalgamation and HNN extensions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X795AB71F7E370119">7.4-1 FreeProductWithAmalgamation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X86F5F9787E3644FD">7.4-2 ReducedImageElm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X7CB0F120804A8DED">7.4-3 HnnExtension</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap7_mj.html#X78108FB4814AE887">7.5 <span class="Heading">GraphsOfGroupoids and their Words</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X8739267678808E85">7.5-1 GraphOfGroupoids</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap7_mj.html#X7EC1A9067FC91255">7.5-2 GraphOfGroupoidsWord</a></span>
</div></div>
</div>
<h3>7 <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_mj.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_mj.html#biBHiJLMS">[Hig76]</a>. For further details see Chapter 2 of <a href="chapBib_mj.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>7.1 <span class="Heading">Digraphs</span></h4>
<p><a id="X85BD6D2584D8A22F" name="X85BD6D2584D8A22F"></a></p>
<h5>7.1-1 FpWeightedDigraph</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FpWeightedDigraph</code>( <var class="Arg">verts</var>, <var class="Arg">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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">V1 := [ 5, 6 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fg1 := FreeGroup( "y" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := fg1.1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A1 := [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ];</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">D1 := FpWeightedDigraph( fg1, V1, A1 );</span>
weighted digraph with vertices: [ 5, 6 ]
and arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">inv1 := InvolutoryArcs( D1 );</span>
[ 2, 1 ]
</pre></div>
<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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">fg3 := FreeGroup( 3, "z" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">z1 := fg3.1;; z2 := fg3.2;; z3 := fg3.3;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ob3 := [ 7, 8, 9 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">A3 := [[z1,7,8],[z2,8,9],[z3,9,7],[z1^-1,8,7],[z2^-1,9,8],[z3^-1,7,9]];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">D3 := FpWeightedDigraph( fg3, ob3, A3 );</span>
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> inob3 := InvolutoryArcs( D3 );
[ 4, 5, 6, 1, 2, 3 ]
</pre></div>
<p><a id="X7BAFCA3680E478AE" name="X7BAFCA3680E478AE"></a></p>
<h4>7.2 <span class="Heading">Graphs of Groups</span></h4>
<p><a id="X8130246E854BC5D9" name="X8130246E854BC5D9"></a></p>
<h5>7.2-1 GraphOfGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GraphOfGroups</code>( <var class="Arg">dig</var>, <var class="Arg">gps</var>, <var class="Arg">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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; IsomorphismsOfGraphOfGroups</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">&#an style='color: green'>8227; IsGraphOfGroups</code>( <var class="Arg">dig</var> )</td><td class="tdright">( category )</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 three attributes provide a means of calling the three 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 in Section <a href="chap7_mj.html#X7D99A7B37B36BAA8"><span class="RefLink">7.4</span></a>. So we take as our first example the trefoil group with generators <span class="SimpleMath">\(a,b\)</span> and relation <span class="SimpleMath">\(a^3=b^2\)</span>. For this we take digraph <code class="code">D1</code> above with an infinite cyclic group at each vertex, generated by <span class="SimpleMath">\(a\)</span> and <span class="SimpleMath">\(b\)</span> respectively. The two subgroups will be generated by <span class="SimpleMath">\(a^3\)</span> and <span class="SimpleMath">\(b^2\)</span> with the obvious isomorphisms.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">## free vertex group at 5</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fa := FreeGroup( "a" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a := fa.1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( fa, "fa" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hy := Subgroup( fa, [a^3] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( hy, "hy" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## free vertex group at 6</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fb := FreeGroup( "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := fb.1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( fb, "fb" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hybar := Subgroup( fb, [b^2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( hybar, "hybar" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## isomorphisms between subgroups</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">homy := GroupHomomorphismByImagesNC( hy, hybar, [a^3], [b^2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">homybar := GroupHomomorphismByImagesNC( hybar, hy, [b^2], [a^3] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## defining graph of groups G1</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">G1 := GraphOfGroups( D1, [fa,fb], [homy,homybar] );</span>
Graph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( G1 );</span>
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 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfGroups( G1 );</span>
true
</pre></div>
<p><a id="X847464677F641527" name="X847464677F641527"></a></p>
<h5>7.2-2 IsGraphOfFpGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfFpGroups( G1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsomorphismsOfGraphOfGroups( G1 );</span>
[ [ a^3 ] -> [ b^2 ], [ b^2 ] -> [ a^3 ] ]
</pre></div>
<p><a id="X7B036C2B84E48BB1" name="X7B036C2B84E48BB1"></a></p>
<h5>7.2-3 RightTransversalsOfGraphOfGroups</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RTG1 := RightTransversalsOfGraphOfGroups( G1 );</span>
[ [ <identity ...>, a, a^2 ], [ <identity ...>, b ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LTG1 := LeftTransversalsOfGraphOfGroups( G1 );</span>
[ [ <identity ...>, a^-1, a^-2 ], [ <identity ...>, b^-1 ] ]
</pre></div>
<p><a id="X7BD9DCF87FB3E0AF" name="X7BD9DCF87FB3E0AF"></a></p>
<h4>7.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>7.3-1 GraphOfGroupsWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GraphOfGroupsWord</code>( <var class="Arg">gg</var>, <var class="Arg">tv</var>, <var class="Arg">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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; TailOfGraphOfGroupsWord</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">&#an style='color: green'>8227; HeadOfGraphOfGroupsWord</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_mj.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 <span class="SimpleMath">\(w = [g_1,y_1,g_2,y_2,...,g_n,y_n,g_{n+1}]\)</span>. Here each <span class="SimpleMath">\(y_i\)</span> is an arc of <code class="code">D</code>; the head of <span class="SimpleMath">\(y_{i-1}\)</span> is a vertex <span class="SimpleMath">\(v_i\)</span> which is also the tail of <span class="SimpleMath">\(y_i\)</span>; and <span class="SimpleMath">\(g_i\)</span> is an element of the vertex group at <span class="SimpleMath">\(v_i\)</span>.</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 <span class="SimpleMath">\(y_i\)</span> 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 <span class="SimpleMath">\(5\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">L1 := [ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gw1 := GraphOfGroupsWord( G1, 5, L1 );</span>
(5)a^7.y.b^-6.y^-1.a^-11.y.b^9.y^-1.a^7(5)
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfGroupsWord( gw1 );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">[ TailOfGraphOfGroupsWord(gw1), HeadOfGraphOfGroupsWord(gw1) ];</span>
[ 5, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">GraphOfGroupsOfWord(gw1);</span>
Graph of Groups: 2 vertices; 2 arcs; groups [ fa, fb ]
<span class="GAPprompt">gap></span> <span class="GAPinput">WordOfGraphOfGroupsWord( gw1 );</span>
[ a^7, 1, b^-6, 2, a^-11, 1, b^9, 2, a^7 ]
</pre></div>
<p><a id="X78FA7C3F831AA6E4" name="X78FA7C3F831AA6E4"></a></p>
<h5>7.3-2 ReducedGraphOfGroupsWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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 <span class="SimpleMath">\([g_i,y_i,g_{i+1}]\)</span> are replaced by <span class="SimpleMath">\([t_i,y_i,m_i(h_i)*g_{i+1}]\)</span> where <span class="SimpleMath">\(g_i = t_i*h_i\)</span> is the unique factorisation of <span class="SimpleMath">\(g_i\)</span> as a left coset representative times an element of the arc subgroup, and <span class="SimpleMath">\(m_i\)</span> is the isomorphism associated to <span class="SimpleMath">\(y_i\)</span>. 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 <span class="SimpleMath">\([t_1,y_1,t_2,y_2,...,t_n,y_n,k]\)</span> for some <span class="SimpleMath">\(k\)</span> in the head group of <span class="SimpleMath">\(y_n\)</span>. For further details see Section 2.2 of <a href="chapBib_mj.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="center">\[
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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">nw1 := ReducedGraphOfGroupsWord( gw1 );</span>
(5)a^-1.y.b^-1.y^-1.a^10(5)
</pre></div>
<p><a id="X7D99A7B37B36BAA8" name="X7D99A7B37B36BAA8"></a></p>
<h4>7.4 <span class="Heading">Free products with amalgamation and HNN extensions</span></h4>
<p><a id="X795AB71F7E370119" name="X795AB71F7E370119"></a></p>
<h5>7.4-1 FreeProductWithAmalgamation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; FreeProductWithAmalgamation</code>( <var class="Arg">gp1</var>, <var class="Arg">gp2</var>, <var class="Arg">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">&#an style='color: green'>8227; FreeProductWithAmalgamationInfo</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">&#an style='color: green'>8227; IsFreeProductWithAmalgamation</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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; NormalFormGGRWS</code>( <var class="Arg">fpa</var>, <var class="Arg">word</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>As we have seen with the trefoil group example in Section <a href="chap7_mj.html#X7BAFCA3680E478AE"><span class="RefLink">7.2</span></a>, graphs of groups can be used to obtain a normal form for free products with amalgamation <span class="SimpleMath">\(G_1 *_H G_2\)</span> when <span class="SimpleMath">\(G_1, G_2\)</span> both have rewrite systems, and <span class="SimpleMath">\(H\)</span> is of finite index in both <span class="SimpleMath">\(G_1\)</span> and <span class="SimpleMath">\(G_2\)</span>.</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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">## set up the first group s3 and a subgroup c3=<a1></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fg2 := FreeGroup( 2, "a" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rel1 := [ fg2.1^3, fg2.2^2, (fg2.1*fg2.2)^2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">s3 := fg2/rel1;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gs3 := GeneratorsOfGroup(s3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( s3, "s3" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a1 := gs3[1];; a2 := gs3[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H1 := Subgroup(s3,[a1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## then the second group a4 and subgroup c3=<b1></span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := FreeGroup( 2, "b" );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">rel2 := [ f2.1^3, f2.2^3, (f2.1*f2.2)^2 ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">a4 := f2/rel2;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ga4 := GeneratorsOfGroup(a4);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( a4, "a4" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">b1 := ga4[1]; b2 := ga4[2];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">H2 := Subgroup(a4,[b1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">## form the isomorphism and the fpa group</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">iso := GroupHomomorphismByImages(H1,H2,[a1],[b1]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">inv := InverseGeneralMapping(iso);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">fpa := FreeProductWithAmalgamation( s3, a4, iso );</span>
<fp group on the generators [ f1, f2, f3, f4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RelatorsOfFpGroup( fpa );</span>
[ f1^2, f2^3, (f2*f1)^2, f3^3, f4^3, (f4*f3)^2, f2*f3^-1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gg1 := GraphOfGroupsRewritingSystem( fpa );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( gg1 );</span>
Graph of Groups with :-
vertices: [ 5, 6 ]
arcs: [ [ y, 5, 6 ], [ y^-1, 6, 5 ] ]
groups: [ s3, a4 ]
isomorphisms: [ [ [ a1 ], [ b1 ] ], [ [ b1 ], [ a1 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftTransversalsOfGraphOfGroups( gg1 );</span>
[ [ <identity ...>, a2^-1 ], [ <identity ...>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ]
]
<span class="GAPprompt">gap></span> <span class="GAPinput">gfpa := GeneratorsOfGroup( fpa );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">w2 := (gfpa[1]*gfpa[2]*gfpa[3]^gfpa[4])^3;</span>
(f1*f2*f4^-1*f3*f4)^3
<span class="GAPprompt">gap></span> <span class="GAPinput">n2 := NormalFormGGRWS( fpa, w2 );</span>
f2*f3*(f4^-1*f2)^2*f4^-1*f3
</pre></div>
<p><a id="X86F5F9787E3644FD" name="X86F5F9787E3644FD"></a></p>
<h5>7.4-2 ReducedImageElm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ReducedImageElm</code>( <var class="Arg">hom</var>, <var class="Arg">eml</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">&#an style='color: green'>8227; IsMappingToGroupWithGGRWS</code>( <var class="Arg">map</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">&#an style='color: green'>8227; Embedding</code>( <var class="Arg">fpa</var>, <var class="Arg">num</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>All fpa-groups are provided with a record attribute, <code class="code">FreeProductWithAmalgamationInfo(fpa)</code> which is a record storing the groups, subgroups and isomorphism involved in their construction. This information record also contains the embeddings of the two groups into the product. The operation <code class="code">ReducedImageElm</code>, applied to a homomorphism <span class="SimpleMath">\(h\)</span> of type <code class="code">IsMappingToGroupWithGGRWS</code> and an element <span class="SimpleMath">\(x\)</span> of the source, finds the usual <code class="code">ImageElm(h,x)</code> and then reduces this to its normal form using the graph of groups rewriting system.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">fpainfo;</span>
rec( embeddings := [ [ a2, a1 ] -> [ f1, f2 ], [ b1, b2 ] -> [ f3, f4 ] ],
groups := [ s3, a4 ], isomorphism := [ a1 ] -> [ b1 ],
positions := [ [ 1, 2 ], [ 3, 4 ] ],
subgroups := [ Group([ a1 ]), Group([ b1 ]) ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">emb2 := Embedding( fpa, 2 );</span>
[ b1, b2 ] -> [ f3, f4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ImageElm( emb2, b1^b2 ); </span>
f4^-1*f3*f4
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedImageElm( emb2, b1^b2 );</span>
f4*f3^-1
</pre></div>
<p><a id="X7CB0F120804A8DED" name="X7CB0F120804A8DED"></a></p>
<h5>7.4-3 HnnExtension</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; HnnExtension</code>( <var class="Arg">gp</var>, <var class="Arg">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">&#an style='color: green'>8227; HnnExtensionInfo</code>( <var class="Arg">gp</var>, <var class="Arg">iso</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">&#an style='color: green'>8227; IsHnnExtension</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 <span class="SimpleMath">\(z,z^{-1}\)</span>. 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 <span class="SimpleMath">\(z\)</span>.</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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">H3 := Subgroup(a4,[b2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">i23 := GroupHomomorphismByImages( H2, H3, [b1], [b2] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">hnn := HnnExtension( a4, i23 );</span>
<fp group on the generators [ fe1, fe2, fe3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">phnn := PresentationFpGroup( hnn );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">TzPrint( phnn );</span>
#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 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gg2 := GraphOfGroupsRewritingSystem( hnn );</span>
Graph of Groups: 1 vertices; 2 arcs; groups [ a4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftTransversalsOfGraphOfGroups( gg2 );</span>
[ [ <identity ...>, b2^-1, b1^-1*b2^-1, b1*b2^-1 ],
[ <identity ...>, b1^-1, b1, b2^-1*b1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gh := GeneratorsOfGroup( hnn );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">w3 := (gh[1]^gh[2])*gh[3]^-1*(gh[1]*gh[3]*gh[2]^2)^2*gh[3]*gh[2];</span>
fe2^-1*fe1*fe2*fe3^-1*(fe1*fe3*fe2^2)^2*fe3*fe2
<span class="GAPprompt">gap></span> <span class="GAPinput">n3 := NormalFormGGRWS( hnn, w3 );</span>
(fe2*fe1*fe3)^2
</pre></div>
<p>As with fpa-groups, hnn-groups are provided with a record attribute, <code class="code">HnnExtensionInfo(hnn)</code>, storing the group, subgroups and isomorphism involved in their construction.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">hnninfo := HnnExtensionInfo( hnn );</span>
rec( embeddings := [ [ b1, b2 ] -> [ fe1, fe2 ] ], group := a4,
isomorphism := [ b1 ] -> [ b2 ],
subgroups := [ Group([ b1 ]), Group([ b2 ]) ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">emb := Embedding( hnn, 1 );</span>
[ b1, b2 ] -> [ fe1, fe2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ImageElm( emb, b1^b2 ); </span>
fe2^-1*fe1*fe2
<span class="GAPprompt">gap></span> <span class="GAPinput">ReducedImageElm( emb, b1^b2 );</span>
fe2*fe1^-1
</pre></div>
<p><a id="X78108FB4814AE887" name="X78108FB4814AE887"></a></p>
<h4>7.5 <span class="Heading">GraphsOfGroupoids and their Words</span></h4>
<p><a id="X8739267678808E85" name="X8739267678808E85"></a></p>
<h5>7.5-1 GraphOfGroupoids</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GraphOfGroupoids</code>( <var class="Arg">dig</var>, <var class="Arg">gpds</var>, <var class="Arg">subgpds</var>, <var class="Arg">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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; LeftTransversalsOfGraphOfGroupoids</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">&#an style='color: green'>8227; IsGraphOfGroupoids</code>( <var class="Arg">dig</var> )</td><td class="tdright">( category )</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 <span class="SimpleMath">\(\langle a^3 \rangle\)</span> and <span class="SimpleMath">\(\langle b^2 \rangle\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gfa := SinglePieceGroupoid( fa, [-2,-1] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ofa := One( fa );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Gfa, "Gfa" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Uhy := Subgroupoid( Gfa, [ [ hy, [-2,-1] ] ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Uhy, "Uhy" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Gfb := SinglePieceGroupoid( fb, [-4,-3] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ofb := One( fb );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Gfb, "Gfb" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Uhybar := Subgroupoid( Gfb, [ [ hybar, [-4,-3] ] ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetName( Uhybar, "Uhybar" );</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gens := GeneratorsOfGroupoid( Uhy );; </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">gensbar := GeneratorsOfGroupoid( Uhybar );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">mory := GroupoidHomomorphismFromSinglePiece( </span>
<span class="GAPprompt">></span> <span class="GAPinput"> Uhy, Uhybar, gens, gensbar );</span>
groupoid homomorphism : Uhy -> Uhybar
[ [ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ],
[ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">morybar := InverseGeneralMapping( mory );</span>
groupoid homomorphism : Uhybar -> Uhy
[ [ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ],
[ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gg3 := GraphOfGroupoids( D1, [Gfa,Gfb], [Uhy,Uhybar], [mory,morybar] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( gg3 );</span>
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
[ [ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ],
[ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ] ],
groupoid homomorphism : Uhybar -> Uhy
[ [ [b^2 : -4 -> -4], [<identity ...> : -4 -> -3] ],
[ [a^3 : -2 -> -2], [<identity ...> : -2 -> -1] ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsGraphOfGroupoids( gg3 );</span>
true
</pre></div>
<p><a id="X7EC1A9067FC91255" name="X7EC1A9067FC91255"></a></p>
<h5>7.5-2 GraphOfGroupoidsWord</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; GraphOfGroupoidsWord</code>( <var class="Arg">gg</var>, <var class="Arg">tv</var>, <var class="Arg">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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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">&#an style='color: green'>8227; 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. Analogous to the word <span class="SimpleMath">\(a^7b^{-6}a^{-11}b^9a^7\)</span> in subsection <code class="func">ReducedGraphOfGroupsWord</code> (<a href="chap7_mj.html#X78FA7C3F831AA6E4"><span class="RefLink">7.3-2</span></a>) we shall consider</p>
<p class="center">\[
(a^7 : -1 \to -2)~(b^{-6} : -4 \to -4 )~(a^{-11} : -2 \to -1)~
(b^9 : -3 \to -4)~(a^7 : -2 \to -1).
\]</p>
<p>Compare the normal form <code class="code">nw3</code> below with the normal form <code class="code">nw1</code> above.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f1 := Arrow( Gfa, a^7, -1, -2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f2 := Arrow( Gfb, b^-6, -4, -4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f3 := Arrow( Gfa, a^-11, -2, -1 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f4 := Arrow( Gfb, b^9, -3, -4 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">f5 := Arrow( Gfa, a^7, -2, -2 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">L3 := [ f1, 1, f2, 2, f3, 1, f4, 2, f5 ];</span>
[ [a^7 : -1 -> -2], 1, [b^-6 : -4 -> -4], 2, [a^-11 : -2 -> -1], 1,
[b^9 : -3 -> -4], 2, [a^7 : -2 -> -2] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">gw3 := GraphOfGroupoidsWord( gg3, 5, L3);</span>
(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 -> -2](5)
<span class="GAPprompt">gap></span> <span class="GAPinput">nw3 := ReducedGraphOfGroupoidsWord( gw3 );</span>
(5)[a^-1 : -1 -> -1].y.[b^-1 : -3 -> -3].y^-1.[a^10 : -1 -> -2](5)
</pre></div>
<p>The reduction proceeds as follows.</p>
<ul>
<li><p><span class="SimpleMath">\( [a^7 : -1 \to -2] = [a^{-2} : -1 \to -1]*[a^9 : -1 \to -2] \stackrel{y}{\to} [a^{-2} : -1 \to -1]*[b^6 : -3 \to -4] \)</span></p>
</li>
<li><p><span class="SimpleMath">\( [b^6 : -3 \to -4]*[b^{-6} : -4 \to -4] = [\mathrm{id} : -3 \to -4] \stackrel{\bar{y}}{\to} [\mathrm{id} : -1 \to -2] \)</span></p>
</li>
<li><p><span class="SimpleMath">\( [a^{-2} : -1 \to -1]*[\mathrm{id} : -1 \to -2]*[a^{-11} : -2 \to -1] = [a^{-13} : -1 \to -1] \)</span></p>
</li>
<li><p><span class="SimpleMath">\( [a^{-13} : -1 \to -1] = [a^{-1} : -1 \to -1]*[a^{-12} : -1 \to -1] \stackrel{y}{\to} [a^{-1} : -1 \to -1]*[b^{-8} : -3 \to -3] \)</span></p>
</li>
<li><p><span class="SimpleMath">\( [b^{-8} : -3 \to -3]*[b^9 : -3 \to -4] = [b^{-1} : -3 \to -3]*[b^2 : -3 \to -4] \stackrel{\bar{y}}{\to} [b^{-1} : -3 \to -3]*[a^3 : -1 \to -2] \)</span></p>
</li>
<li><p><span class="SimpleMath">\( [a^3 := -1 \to -2]*[a^7 : -2 \to -2] = [a^{10} : -1 \to -2] \)</span></p>
</li>
</ul>
<p>So the resulting word is <span class="SimpleMath">\(~(a^{-1} : -1, -1)(b^{-1} : -3, -3)(a^{10} : -1, -2)\)</span>. Notice that all the arrows except the final one are loops.</p>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap6_mj.html">[Previous Chapter]</a> <a href="chap8_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.35 Sekunden
¤
*© Formatika GbR, Deutschland
|
|
2026-11-01
|
|
|
|
|
Neuigkeiten |
| Aktuelles |
| Motto des Tages |
|
Open Source Software |
|
|
|
Jenseits des Üblichen ....
|
|
Besucherstatistik |
|
|
| Statistik |
| #Sources=1104852 |
| #Domains=417180 |
|
|
