% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}
\usepackage{fancyvrb}
\usepackage{pslatex}
\usepackage[pdftex=true,
a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
pdfcreator={LaTeX with hyperref package / GAPDoc},
colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
citecolor=RoyalGreen,filecolor=RoyalRed,
urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}
% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
%% were never documented, give conflicts with some additional packages
\newcommand{\GAP}{\textsf{GAP}}
\begin{document}
\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{\textsf{Gpd}\mbox{}}}\\[1cm]
\hypersetup{pdftitle=\textsf{Gpd}}
\markright{\scriptsize \mbox{}\hfill \textsf{Gpd} \hfill\mbox{}}
{\Large \textbf{Groupoids, graphs of groups, and graphs of groupoids\mbox{}}}\\[1cm]
{Version 1.05\mbox{}}\\[1cm]
{November 2008\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{ Emma Moore \mbox{}}}\\
{\large \textbf{ Chris Wensley \mbox{}}}\\
\hypersetup{pdfauthor= Emma Moore ; Chris Wensley }
\end{center}\vfill
\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{ Emma Moore } --- Email: \href{mailto://emmajmoore@yahoo.co.uk} {\texttt{emmajmoore@yahoo.co.uk}}}\\
{\mbox{}\\
\small \noindent \textbf{ Chris Wensley } --- Email: \href{mailto://c.d.wensley@bangor.ac.uk} {\texttt{c.d.wensley@bangor.ac.uk}}\\
--- Homepage: \href{http://www.bangor.ac.uk/~mas023/} {\texttt{http://www.bangor.ac.uk/\texttt{\symbol{126}}mas023/}}\\
--- Address: \begin{minipage}[t]{8cm}\noindent
School of Computer Science, Bangor University,\\
Dean Street, Bangor, Gwynedd, LL57 1UT, U.K. \end{minipage}
}\\
\end{titlepage}
\newpage\setcounter{page}{2}
{\small
\section*{Abstract}
\logpage{[ 0, 0, 1 ]}
The \textsf{Gpd} package for \textsf{GAP}4 provides functions for the computation with groupoids (categories with every
arrow invertible) and their morphisms; for graphs of groups, and graphs of
groupoids.
It provides normal forms for Free Products with Amalgamation and for
HNN-extensions when the initial groups have rewrite systems and the subgroups
have finite index.
The \textsf{Gpd} package was originally implemented in 2000 (as \textsf{GraphGpd}) when the first author was studying for a Ph.D. in Bangor.
The current version is 1.05, released on 21st November 2008, and now includes
the more basic structure of \emph{magma with objects}. It had to be released hurriedly, due to the change of website, so some of
the function are no longer available. A new version will be released as soon
as possible.
Bug reports, suggestions and comments are, of course, welcome. Please contact
the second author at \href{mailto://c.d.wensley@bangor.ac.uk} {\texttt{c.d.wensley@bangor.ac.uk}}. \mbox{}}\\[1cm]
{\small
\section*{Copyright}
\logpage{[ 0, 0, 2 ]}
{\copyright} 2000-2008 Emma Moore and Chris Wensley
\mbox{}}\\[1cm]
{\small
\section*{Acknowledgements}
\logpage{[ 0, 0, 3 ]}
This \textsf{gpd} package is released under the GNU General Public License (GPL). This file is
part of \textsf{gpd}, though as documentation it is released under the GNU Free Documentation
License (see \href{http://www.gnu.org/licenses/licenses.html#FDL} {\texttt{http://www.gnu.org/licenses/licenses.html\#FDL}}).
\textsf{gpd} is free software; you can redistribute it and/or modify it under the terms of
the GNU General Public License as published by the Free Software Foundation;
either version 2 of the License, or (at your option) any later version.
\textsf{gpd} is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with \textsf{gpd}; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite
330, Boston, MA 02111-1307 USA.
For more details, see \href{http://www.fsf.org/licenses/gpl.html} {\texttt{http://www.fsf.org/licenses/gpl.html}}.
This documentation was prepared with the \textsf{GAPDoc} package of Frank L\texttt{\symbol{92}}"ubeck and Max
Neunh\texttt{\symbol{92}}"offer. \mbox{}}\\[1cm]
\newpage
\def\contentsname{Contents\logpage{[ 0, 0, 4 ]}}
\tableofcontents
\newpage
\chapter{\textcolor{Chapter }{Introduction}}\label{intro}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
Groupoids are mathematical categories in which every arrow is invertible. The \textsf{Gpd} package provides functions for the computation with groupoids and their
morphisms; for graphs of groups and graphs of groupoids. The package is far
from complete, and development continues.
It was used by Emma Moore in her thesis \cite{emma-thesis} to calculate normal forms for Free Products with Amalgamation, and for
HNN-extensions, when the initial groups have rewrite systems.
\textsf{Gpd} is implemented using \textsf{GAP} 4.4.
The information parameter \texttt{InfoGpd} takes default value \texttt{1} which, for the benefit of new users, causes more messages to be printed out
when operations fail. When raised to a higher value, additional information is
printed out.
Help is available in the usual way.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> LoadPackage( "gpd" );
-----------------------------------------------------------
loading Gpd 1.05 for GAP 4.4 - Emma Moore and Chris Wensley
-----------------------------------------------------------
true
\end{Verbatim}
For version 1.05 the package has been completely restructured, starting with \emph{magmas with objects} and their mappings, and building up to groupoids via semigroups with objects
and monoids with objects. This development is ongoing, and this manual does
not mention all the available functions. A new version will be released as
soon as possible.
Once the package is loaded, it is possible to check the correct installation
by running the test suite of the package with the following command. (The test
file itself is \texttt{tst/gpd{\textunderscore}manual.tst}.)
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> ReadPackage( "gpd", "tst/testall.g" );
+ Testing examples in Chapter 2 of the Gpd manual
+ GAP4stones: 1250
+ Testing examples in Chapter 3 of the Gpd manual
+ GAP4stones: infinity
+ Testing examples in Chapter 4 of the Gpd manual
+ GAP4stones: 416
+ Testing examples in Chapter 5 of the Gpd manual
+ GAP4stones: 2500
+ Testing examples in Chapter 6 of the Gpd manual
+ GAP4stones: 28
\end{Verbatim}
You may reference this package by mentioning \cite{BrMoPoWe} and \cite{emma-thesis}. }
\chapter{\textcolor{Chapter }{Many-object structures}}\label{chap-mwp}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X8361CEA4856430C6}{}
{
A \emph{magma with objects} $M$ consists of a set of \emph{objects} Ob$(M)$, and a set of \emph{arrows} Arr$(M)$ together with \emph{tail} and \emph{head} maps $t,h :$ Arr$(M) \to$ Ob$(M)$, and a \emph{partial multiplication} $* :$ Arr$(M) \to $ Arr$(M)$, with $a*b$ defined precisely when the head of $a$ coincides with the tail of $b$. We write an arrow $a$ with tail $u$ and head $v$ as $(a : u \to v)$.
When this multiplication is associative we obtain a \emph{semigroup with objects}.
A \emph{loop} is an arrow whose tail and head are the same object. An \emph{identity arrow} at object $u$ is a loop $(1_u : u \to u)$ such that $a*1_u=a$ and $1_u*b=b$ whenever $u$ is the head of $a$ and the tail of $b$. When $M$ is a semigroup with objects and every object has an identity arrow, we obtain
a \emph{monoid with objects}, which is just the usual notion of mathematical category.
An arrow $(a : u \to v)$ in a monoid with objects has \emph{inverse} $(a^{-1} : v \to u)$ provided $a*a^{-1} = 1_u$ and $a^{-1}*a = 1_v$. A monoid with objects in which every arrow has an inverse is a \emph{group with objects}, usually called a \emph{groupoid}.
For the definitions of the standard properties of groupoids we refer to R.
Brown's book ``Topology'' \cite{BrTop}, recently revised and reissued as ``Topology and Groupoids'' \cite{BrTopGpd}.
\section{\textcolor{Chapter }{Magmas with objects}}\logpage{[ 2, 1, 0 ]}
\hyperdef{L}{X79CE5DFF7ADC7744}{}
{
\subsection{\textcolor{Chapter }{MagmaWithObjects}}
\logpage{[ 2, 1, 1 ]}\nobreak
\hyperdef{L}{X7C51D7847BD23284}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MagmaWithObjects({\slshape args})\index{MagmaWithObjects@\texttt{MagmaWithObjects}}
\label{MagmaWithObjects}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ObjectList({\slshape mwo})\index{ObjectList@\texttt{ObjectList}}
\label{ObjectList}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SemigroupithObjects({\slshape args})\index{SemigroupithObjects@\texttt{SemigroupithObjects}}
\label{SemigroupithObjects}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MonoidWithObjects({\slshape args})\index{MonoidWithObjects@\texttt{MonoidWithObjects}}
\label{MonoidWithObjects}
}\hfill{\scriptsize (function)}}\\
The simplest construction for a magma with objects is to take a magma $m$ and form arrows $(u,x,v)$ for every $x$ in $m$ and every pair of objects $(u,v)$. Multiplication is defined by $(u,x,v)*(v,y,w) = (u,x*y,w)$.
Any finite, ordered set is in principle acceptable as the objects of $M$, but we will restrict ourselves to sets of negative integers here.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> tm := [[1,2,4,3],[1,2,4,3],[3,4,2,1],[3,4,2,1]];; Display( tm );
[ [ 1, 2, 4, 3 ],
[ 1, 2, 4, 3 ],
[ 3, 4, 2, 1 ],
[ 3, 4, 2, 1 ] ]
gap> m := MagmaByMultiplicationTable( tm );
<magma with 4 generators>
gap> SetName( m, "m" );
gap> m1 := MagmaElement(m,1);;
gap> m2 := MagmaElement(m,2);;
gap> m3 := MagmaElement(m,3);;
gap> m4 := MagmaElement(m,4);;
gap> One(m);
fail
gap> M78 := MagmaWithObjects( [-8,-7], m );
Magma with objects :-
objects = [ -8, -7 ]
magma = m
gap> [ IsAssociative(M78), IsCommutative(M78) ];
[ false, false ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{MultiplicativeElementWithObjects}}
\logpage{[ 2, 1, 2 ]}\nobreak
\hyperdef{L}{X79D2548F7DD8C6E7}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MultiplicativeElementWithObjects({\slshape mwo, elt, tail, head})\index{MultiplicativeElementWithObjects@\texttt{MultiplicativeElementWithObjects}}
\label{MultiplicativeElementWithObjects}
}\hfill{\scriptsize (operation)}}\\
Elements in a magma with objects lie in the category \texttt{IsMultiplicativeElementWithObjects}. An attempt to multiply two arrows which do not compose resuts in \texttt{fail} being returned.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> a78 := MultiplicativeElementWithObjects( M78, m4, -7, -8 );
[m2 : -7 -> -8]
gap> b87 := MultiplicativeElementWithObjects( M78, m3, -8, -7 );
[m3 : -8 -> -7]
gap> ba := b87*a78;
[m4 : -8 -> -8]
gap> ab := a78*b87;
[m4 : -7 -> -7]
gap> a78^2;
fail
gap> ba^2;
[m1 : -8 -> -8]
\end{Verbatim}
\subsection{\textcolor{Chapter }{IsSinglePiece}}
\logpage{[ 2, 1, 3 ]}\nobreak
\hyperdef{L}{X7C0911667FF90DB2}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsSinglePiece({\slshape mwo})\index{IsSinglePiece@\texttt{IsSinglePiece}}
\label{IsSinglePiece}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsDirectProductWithCompleteGraph({\slshape mwo})\index{IsDirectProductWithCompleteGraph@\texttt{IsDirectProductWithCompleteGraph}}
\label{IsDirectProductWithCompleteGraph}
}\hfill{\scriptsize (property)}}\\
If the partial composition is forgotten, then a digraph is left (usually with
multiple edges and loops). Thus the notion of \emph{connected component} may be inherited by magmas with objects from digraphs. Unfortunately the terms \texttt{Component} and \texttt{Constituent} are already in considerably use in \textsf{GAP}, so (for now?) we use the term \texttt{IsSinglePiece} to describe a connected magma with objects.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> IsSinglePiece( M78 );
true
gap> IsDirectProductWithCompleteGraph( M78 );
true
\end{Verbatim}
}
}
\chapter{\textcolor{Chapter }{Homomorphisms of many-object structures}}\label{chap-mwohom}
\logpage{[ 3, 0, 0 ]}
\hyperdef{L}{X85297B407ACAED81}{}
{
A \emph{homomorphism} $f$ from a magma with objects $M$ to a magma with objects $N$ consists of a map $f_O$ from the objects of $M$ to those of $N$ together with a map $f_A$ from the arrows of $M$ to those of $N$ which is compatible with tail and head and which preserves multiplication:
\[ f_A((a : u \to v)*f(b : v \to w)) ~=~ f_A(a*b : u \to w) \]
with tail $f_O(u)$ and head $f_O(v)$.
\section{\textcolor{Chapter }{Homomorphisms of magmas with objects}}\logpage{[ 3, 1, 0 ]}
\hyperdef{L}{X82F856A086B93832}{}
{
\subsection{\textcolor{Chapter }{MagmaWithObjectsHomomorphism}}
\logpage{[ 3, 1, 1 ]}\nobreak
\hyperdef{L}{X86E00FEA7FF38FEA}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MagmaWithObjectsHomomorphism({\slshape args})\index{MagmaWithObjectsHomomorphism@\texttt{MagmaWithObjectsHomomorphism}}
\label{MagmaWithObjectsHomomorphism}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MagmaHomomorphismFromSinglePiece({\slshape src, rng, hom, imobs})\index{MagmaHomomorphismFromSinglePiece@\texttt{MagmaHomomorphismFromSinglePiece}}
\label{MagmaHomomorphismFromSinglePiece}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{HomomorphismToSinglePiece({\slshape src, rng, images})\index{HomomorphismToSinglePiece@\texttt{HomomorphismToSinglePiece}}
\label{HomomorphismToSinglePiece}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{HomomorphismByUnion({\slshape src, rng, homs})\index{HomomorphismByUnion@\texttt{HomomorphismByUnion}}
\label{HomomorphismByUnion}
}\hfill{\scriptsize (operation)}}\\
As usual, there are a variety of homomorphism constructors. The basic
construction is a homomorphism $M \to N$ with both $M$ and $N$ connected, which is implemented as \texttt{IsHomomorphismToSinglePieceRep} with attributes \texttt{Source}, \texttt{Range} and \texttt{PieceImages}. We require the following information:
\begin{itemize}
\item a magma homomorphism \texttt{f} from the underlying of $M$ to the underlying magma of $N$.
\item a list \texttt{imobs} of the images of the objects of $M$;
\end{itemize}
In the example we construct endomappings of $m$ and $M78$.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> tup1 := [ Tuple([m1,m2]), Tuple([m2,m1]), Tuple([m3,m4]), Tuple([m4,m3]) ];
gap> f1 := GeneralMappingByElements( m, m, tup1 );
f1 = <general mapping: m -> m >
gap> IsMagmaHomomorphism( f1 );
true
gap> tup2 := [ Tuple([m1,m1]), Tuple([m2,m1]), Tuple([m3,m1]), Tuple([m4,m1]) ];;
gap> f2 := GeneralMappingByElements( m, m, tup2 );;
gap> IsMagmaHomomorphism( f2 );
true
gap> map1 := HomomorphismFromSinglePiece( M78, M78, [-8,-7], f1 );
magma with objects homomorphism : M78 -> M78
gap> Display( map1 );
Mapping to single piece magma:
[ M78 ] -> [ M78 ]
magma mapping: <mapping: m -> m >
object map: [ -8, -7 ] -> [ -8, -7 ]
Homomorphism to connected magma:
[ M78 ] -> [ M78 ]
object map = [ [ -8, -7 ], [ -8, -7 ] ]
homomorphism = <homomorphism: m -> m >
gap> idm := f1*f1;;
gap> idmap := HomomorphismFromSinglePiece( M78, M78, idm, [-7,-8] );
gap> map2 := HomomorphismFromSinglePiece( M78, M78, f2, [-7,-8] );
\end{Verbatim}
}
}
\chapter{\textcolor{Chapter }{Groupoids}}\label{chap-gpd}
\logpage{[ 4, 0, 0 ]}
\hyperdef{L}{X82F6A1AB798648F4}{}
{
\emph{Many of the names of the functions described in this chapter have changed, due
to the introduction of magmas with objects, so the chapter is full of errors.
A new version will be released as soon as possible.}
A \emph{groupoid} is a (mathematical) category in which every element is invertible. It consists
of a set of \emph{pieces}, each of which is a connected groupoid. (The usual terminology is `connected
component', but in \textsf{GAP} `component' is used for `record component'.)
A \emph{single piece groupoid} is determined by a set of \emph{objects} \texttt{obs} and an \emph{object group} \texttt{grp}. The objects of a single piece groupoid are generally chosen to be
consecutive negative integers, but any suitable ordered set is acceptable, and
`consecutive' is not a requirement. The object groups will usually be taken to
be permutation groups, but pc-groups and fp-groups are also supported.
A \emph{group} is a single piece groupoid with one object.
A \emph{groupoid} is a set of one or more single piece groupoids, its single piece \emph{pieces}, and is represented as \texttt{IsGroupoidRep}, with attribute \texttt{PiecesOfGroupoid}.
For the definitions of the standard properties of groupoids we refer to R.
Brown's book ``Topology'' \cite{BrTop}, recently revised and reissued as ``Topology and Groupoids'' \cite{BrTopGpd}.
\section{\textcolor{Chapter }{Groupoids: their elements and attributes}}\logpage{[ 4, 1, 0 ]}
\hyperdef{L}{X7A7355C58610A48C}{}
{
\subsection{\textcolor{Chapter }{SinglePieceGroupoid}}
\logpage{[ 4, 1, 1 ]}\nobreak
\hyperdef{L}{X8406913B7ED86CFE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SinglePieceGroupoid({\slshape grp, obs})\index{SinglePieceGroupoid@\texttt{SinglePieceGroupoid}}
\label{SinglePieceGroupoid}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Groupoid({\slshape args})\index{Groupoid@\texttt{Groupoid}}
\label{Groupoid}
}\hfill{\scriptsize (function)}}\\
There are a variety of constructors for groupoids, with one or two parameters.
The global function \texttt{Groupoid} will normally find the appropriate one to call, the options being:
\begin{itemize}
\item the object group, a list of objects;
\item a group being converted to a groupoid, a single object;
\item a list of groupoids which have already been constructed.
\end{itemize}
Methods for \texttt{ViewObj}, \texttt{PrintObj} and \texttt{Display} are provided for groupoids and the other types of object in this package.
Users are advised to supply names for all the groups and groupoids they
construct.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> d8 := Group( (1,2,3,4), (1,3) );;
gap> SetName( d8, "d8" );
gap> Gd8 := SinglePieceGroupoid( d8, [-9,-8,-7] );
Perm single piece groupoid:
< d8, [ -9, -8, -7 ] >
gap> c6 := Group( (5,6,7)(8,9) );;
gap> SetName( c6, "c6" );
gap> Gc6 := DomainWithSingleObject( c6, -6 );
Perm SinglePiece Groupoid:
< c6, [ -6 ] >
gap> Gd8c6 := UnionOfPieces( [ Gd8, Gc6 ] );;
gap> Display( Gd8c6 );
Perm Groupoid with 2 pieces:
< objects: [ -9, -8, -7 ]
group: d8 = <[ (1,2,3,4), (1,3) ]> >
< objects: [ -6 ]
group: c6 = <[ (5,6,7)(8,9) ]> >
gap> SetName( Gd8, "Gd8" ); SetName( Gc6, "Gc6" ); SetName( Gd8c6, "Gd8+Gc6" );
\end{Verbatim}
\subsection{\textcolor{Chapter }{Pieces}}
\logpage{[ 4, 1, 2 ]}\nobreak
\hyperdef{L}{X8382678F86F18DA8}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Pieces({\slshape gpd})\index{Pieces@\texttt{Pieces}}
\label{Pieces}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ObjectList({\slshape gpd})\index{ObjectList@\texttt{ObjectList}}
\label{ObjectList}
}\hfill{\scriptsize (attribute)}}\\
When a groupoid consists of two or more pieces, we require their object lists
to be disjoint. The pieces are sorted by the first object in their object
lists, which must be disjoint. The list \texttt{ObjectsOfGroupoid} of a groupoid is the sorted concatenation of the objects in the pieces.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> Pieces( Gd8c6 );
[ Gd8, Gc6 ]
gap> ObjectList( Gd8c6 );
[ -9, -8, -7, -6 ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{IsPermGroupoid}}
\logpage{[ 4, 1, 3 ]}\nobreak
\hyperdef{L}{X8511D3EE845CC930}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsPermGroupoid({\slshape gpd})\index{IsPermGroupoid@\texttt{IsPermGroupoid}}
\label{IsPermGroupoid}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsPcGroupoid({\slshape gpd})\index{IsPcGroupoid@\texttt{IsPcGroupoid}}
\label{IsPcGroupoid}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsFpGroupoid({\slshape gpd})\index{IsFpGroupoid@\texttt{IsFpGroupoid}}
\label{IsFpGroupoid}
}\hfill{\scriptsize (property)}}\\
A groupoid is a permutation groupoid if all its pieces have permutation
groups. Most of the examples in this chapter are permutation groupoids, but in
principle any type of group known to \textsf{GAP} may be used.
In the following example \texttt{Gf2} is an fp-groupoid, while \texttt{Gq8} is a pc-groupoid.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> f2 := FreeGroup( 2 );;
gap> SetName( f2, "f2" );
gap> Gf2 := Groupoid( f2, -22 );;
gap> q8 := SmallGroup( 8, 4 );;
gap> Gq8 := Groupoid( q8, [ -28, -27 ] );;
gap> SetName( q8, "q8" ); SetName( Gq8, "Gq8" );
gap> Gf2q8 := Groupoid( [ Gf2, Gq8 ] );;
gap> [ IsFpGroupoid( Gf2 ), IsPcGroupoid( Gq8 ), IsPcGroupoid( Gf2q8 ) ];
[ true, true, false ]
gap> G4 := Groupoid( [ Gd8c6, Gf2, Gq8 ] );;
gap> Display( G4 );
Groupoid with 4 pieces:
< objects: [ -28, -27 ]
group: q8 = <[ f1, f2, f3 ]> >
< objects: [ -22 ]
group: f2 = <[ f1, f2 ]> >
< objects: [ -9, -8, -7 ]
group: d8 = <[ (1,2,3,4), (1,3) ]> >
< objects: [ -6 ]
group: c6 = <[ (5,6,7)(8,9) ]> >
gap> G4 = Groupoid( [ Gq8, Gf2, Gd8c6 ] );
true
\end{Verbatim}
\subsection{\textcolor{Chapter }{GroupoidElement}}
\logpage{[ 4, 1, 4 ]}\nobreak
\hyperdef{L}{X7D028B3B8385ED07}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GroupoidElement({\slshape gpd, elt, tail, head})\index{GroupoidElement@\texttt{GroupoidElement}}
\label{GroupoidElement}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsElementOfGroupoid({\slshape elt})\index{IsElementOfGroupoid@\texttt{IsElementOfGroupoid}}
\label{IsElementOfGroupoid}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Arrow({\slshape elt})\index{Arrow@\texttt{Arrow}}
\label{Arrow}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Arrowtail({\slshape elt})\index{Arrowtail@\texttt{Arrowtail}}
\label{Arrowtail}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Arrowhead({\slshape elt})\index{Arrowhead@\texttt{Arrowhead}}
\label{Arrowhead}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Size({\slshape gpd})\index{Size@\texttt{Size}}
\label{Size}
}\hfill{\scriptsize (attribute)}}\\
A \emph{groupoid element} \texttt{e} is a triple consisting of a group element, \texttt{Arrow(e)} or \texttt{e![1]}; the tail (source) object, \texttt{Arrowtail(e)} or \texttt{e![2]}; and the head (target) object, \texttt{Arrowhead(e)} or \texttt{e![3]}.
The \texttt{Size} of a groupoid is the number of its elements which, for a single piece
groupoid, is the product of the size of the group with the square of the
number of objects.
Groupoid elements have a \emph{partial composition}: two elements may be multiplied when the head of the first coincides with the
tail of the second.
}
\index{* for groupoid elements}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> e1 := GroupoidElement( Gd8, (1,2)(3,4), -9, -8 );
[(1,2)(3,4) : -9 -> -8]
gap> e2 := GroupoidElement( Gd8, (1,3), -8, -7 );;
gap> Print( [ Arrow( e2 ), Arrowtail( e2 ), Arrowhead( e2 ) ], "\n" );
[ (1,3), -8, -7 ]
gap> prod := e1*e2;
[(1,2,3,4) : -9 -> -7]
gap> e3 := GroupoidElement( Gd8, (1,3)(2,4), -7, -9 );;
gap> cycle := prod*e3;
[(1,4,3,2) : -9 -> -9]
gap> cycle^2;
[(1,3)(2,4) : -9 -> -9]
gap> Order( cycle );
4
gap> cycle^e1;
[(1,2,3,4) : -8 -> -8]
gap> [ Size( Gd8 ), Size( Gc6 ), Size( Gd8c6 ), Size( Gf2q8 ) ];
[ 72, 6, 78, infinity ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{IsSinglePiece}}
\logpage{[ 4, 1, 5 ]}\nobreak
\hyperdef{L}{X7C0911667FF90DB2}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsSinglePiece({\slshape gpd})\index{IsSinglePiece@\texttt{IsSinglePiece}}
\label{IsSinglePiece}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsDiscrete({\slshape gpd})\index{IsDiscrete@\texttt{IsDiscrete}}
\label{IsDiscrete}
}\hfill{\scriptsize (property)}}\\
The forgetful functor, which forgets the composition of elements, maps the
category of groupoids and their morphisms to the category of digraphs and
their morphisms. Applying this functor to a particular groupoid gives the \emph{underlying digraph} of the groupoid. A groupoid is \emph{connected} if its underlying digraph is connected (and so complete). A groupoid is \emph{discrete} if it is a union of groups, so that all the arcs in its underlying digraph are
loops. It is sometimes convenient to call a groupoid element a \emph{loop} when its tail and head are the same object.
}
}
\section{\textcolor{Chapter }{Subgroupoids}}\logpage{[ 4, 2, 0 ]}
\hyperdef{L}{X7BDBA72C852C4625}{}
{
\subsection{\textcolor{Chapter }{SubgroupoidByPieces}}
\logpage{[ 4, 2, 1 ]}\nobreak
\hyperdef{L}{X7AEA9BF780CD6957}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SubgroupoidByPieces({\slshape gpd, obhoms})\index{SubgroupoidByPieces@\texttt{SubgroupoidByPieces}}
\label{SubgroupoidByPieces}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Subgroupoid({\slshape args})\index{Subgroupoid@\texttt{Subgroupoid}}
\label{Subgroupoid}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FullSubgroupoid({\slshape gpd, obs})\index{FullSubgroupoid@\texttt{FullSubgroupoid}}
\label{FullSubgroupoid}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MaximalDiscreteSubgroupoid({\slshape gpd})\index{MaximalDiscreteSubgroupoid@\texttt{MaximalDiscreteSubgroupoid}}
\label{MaximalDiscreteSubgroupoid}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DiscreteSubgroupoid({\slshape gpd, obs, sgps})\index{DiscreteSubgroupoid@\texttt{DiscreteSubgroupoid}}
\label{DiscreteSubgroupoid}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FullIdentitySubgroupoid({\slshape gpd})\index{FullIdentitySubgroupoid@\texttt{FullIdentitySubgroupoid}}
\label{FullIdentitySubgroupoid}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DiscreteIdentitySubgroupoid({\slshape gpd})\index{DiscreteIdentitySubgroupoid@\texttt{DiscreteIdentitySubgroupoid}}
\label{DiscreteIdentitySubgroupoid}
}\hfill{\scriptsize (attribute)}}\\
A \emph{subgroupoid} \texttt{sgpd} of \texttt{gpd} has as objects a subset of the objects of \texttt{gpd}. It is \emph{wide} if all the objects are included. It is \emph{full} if, for any two objects in \texttt{sgpd}, the \texttt{Homset} is the same as in \texttt{gpd}. The elements of \texttt{sgpd} are a subset of those of \texttt{gpd}, closed under multiplication and with tail and head in the chosen object set.
There are a variety of constructors for a subgroupoid of a groupoid. The
operation \texttt{SubgroupoidByPieces} is the most general. Its two parameters are a groupoid and a list of pieces,
where each piece is specified as a list \texttt{[obs,sgp]}, \texttt{obs} is a subset of the objects in one of the pieces of \texttt{gpd}, and \texttt{sgp} is a subgroup of the group in that piece.
The \texttt{FullSubgroupoid} of a groupoid \texttt{gpd} on a subset \texttt{obs} of its objects contains all the elements of \texttt{gpd} with tail and head in \texttt{obs}.
A subgroupoid is \emph{discrete} if it is a union of groups. The \texttt{MaximalDiscreteSubgroupoid} of \texttt{gpd} is the union of all the single-object full subgroupoids of \texttt{gpd}.
An \emph{identity subgroupoid} has trivial object groups, but need not be discrete. A single piece identity
groupoid is sometimes called a \emph{tree groupoid}.
The global function \texttt{Subgroupoid} should call the appropriate operation.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> c4d := Subgroup( d8, [ (1,2,3,4) ] );;
gap> k4d := Subgroup( d8, [ (1,2)(3,4), (1,3)(2,4) ] );;
gap> SetName( c4d, "c4d" ); SetName( k4d, "k4d" );
gap> Ud8 := Subgroupoid( Gd8, [ [ k4d,[-9] ], [ c4d, [-8,-7] ] ] );;
gap> SetName( Ud8, "Ud8" );
gap> Display( Ud8 );
Perm Groupoid with 2 pieces:
< objects: [ -9 ]
group: k4d = <[ (1,2)(3,4), (1,3)(2,4) ]> >
< objects: [ -8, -7 ]
group: c4d = <[ (1,2,3,4) ]> >
gap> FullSubgroupoid( Gd8c6, [-7,-6] );
Perm Groupoid with pieces:
< [ -7 ], d8 >
< [ -6 ], c6 >
gap> DiscreteSubgroupoid( Gd8c6, [-9,-8], [ c4d, k4d ] );
Perm Groupoid with pieces:
< [ -9 ], c4d >
< [ -8 ], k4d >
gap> FullIdentitySubgroupoid( Ud8 );
Perm Groupoid with pieces:
< [ -9 ], id(k4d) >
< [ -8, -7 ], id(c4d) >
\end{Verbatim}
}
\section{\textcolor{Chapter }{Stars, Costars and Homsets}}\logpage{[ 4, 3, 0 ]}
\hyperdef{L}{X793A3BBE81410B11}{}
{
\subsection{\textcolor{Chapter }{ObjectStar}}
\logpage{[ 4, 3, 1 ]}\nobreak
\hyperdef{L}{X7B561BAE7D471C60}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ObjectStar({\slshape gpd, obj})\index{ObjectStar@\texttt{ObjectStar}}
\label{ObjectStar}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ObjectCostar({\slshape gpd, obj})\index{ObjectCostar@\texttt{ObjectCostar}}
\label{ObjectCostar}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Homset({\slshape gpd, tail, head})\index{Homset@\texttt{Homset}}
\label{Homset}
}\hfill{\scriptsize (operation)}}\\
The \emph{star} at \texttt{obj} is the set of groupoid elements which have \texttt{obj} as tail, while the \emph{costar} is the set of elements which have \texttt{obj} as head. The \emph{homset} from \texttt{obj1} to \texttt{obj2} is the set of elements with the specified tail and head, and so is bijective
with the elements of the group. Thus every star and every costar is a union of
homsets.
In order not to create unneccessary long lists, these operations return
objects of type \texttt{IsHomsetCosetsRep} for which an \texttt{Iterator} is provided. (An \texttt{Enumerator} is not yet implemented.)
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> star9 := ObjectStar( Gd8, -9 );
<star at [ -9 ] with group d8>
gap> for e in star9 do
> if ( Order( e![1] ) = 4 ) then Print( e, "\n" ); fi;
> od;
[(1,4,3,2) : -9 -> -9]
[(1,4,3,2) : -9 -> -8]
[(1,4,3,2) : -9 -> -7]
[(1,2,3,4) : -9 -> -9]
[(1,2,3,4) : -9 -> -8]
[(1,2,3,4) : -9 -> -7]
gap> costar6 := ObjectCostar( Gc6, -6 );
<costar at [ -6 ] with group c6>
gap> hset78 := Homset( Ud8, -7, -8 );
<homset -7 -> -8 with group c4d>
gap> for e in hset78 do Print( e, "\n" ); od;
[() : -7 -> -8]
[(1,3)(2,4) : -7 -> -8]
[(1,4,3,2) : -7 -> -8]
[(1,2,3,4) : -7 -> -8]
\end{Verbatim}
\subsection{\textcolor{Chapter }{IdentityElement}}
\logpage{[ 4, 3, 2 ]}\nobreak
\hyperdef{L}{X7E30871D78B9F81C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IdentityElement({\slshape gpd, obj})\index{IdentityElement@\texttt{IdentityElement}}
\label{IdentityElement}
}\hfill{\scriptsize (operation)}}\\
The identity groupoid element \texttt{1\texttt{\symbol{92}}{\textunderscore}\texttt{\symbol{123}}o\texttt{\symbol{125}}} of \texttt{gpd} at object \texttt{o} is \texttt{[e,o,o]} where \texttt{e} is the identity group element in the object group. It is a left identity for
the star and a right identity for the costar at that object.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> i7 := IdentityElement( Gd8, -7 );;
gap> i8 := IdentityElement( Gd8, -8 );;
gap> L := [ i7, i8 ];;
gap> for e in hset78 do Add( L, i7*e*i8 = e ); od;
gap> L;
[ [() : -7 -> -7], [() : -8 -> -8], true, true, true, true ]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Left, right and double cosets}}\logpage{[ 4, 4, 0 ]}
\hyperdef{L}{X831AA9E8780235F2}{}
{
\subsection{\textcolor{Chapter }{RightCoset}}
\logpage{[ 4, 4, 1 ]}\nobreak
\hyperdef{L}{X8412ABD57986B9FC}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightCoset({\slshape G, U, elt})\index{RightCoset@\texttt{RightCoset}}
\label{RightCoset}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightCosetRepresentatives({\slshape G, U})\index{RightCosetRepresentatives@\texttt{RightCosetRepresentatives}}
\label{RightCosetRepresentatives}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightCosetsNC({\slshape G, U})\index{RightCosetsNC@\texttt{RightCosetsNC}}
\label{RightCosetsNC}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeftCoset({\slshape G, U, elt})\index{LeftCoset@\texttt{LeftCoset}}
\label{LeftCoset}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeftCosetRepresentatives({\slshape G, U})\index{LeftCosetRepresentatives@\texttt{LeftCosetRepresentatives}}
\label{LeftCosetRepresentatives}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeftCosetRepresentativesFromObject({\slshape G, U, obj})\index{LeftCosetRepresentativesFromObject@\texttt{LeftCosetRepresentativesFromObject}}
\label{LeftCosetRepresentativesFromObject}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeftCosetsNC({\slshape G, U})\index{LeftCosetsNC@\texttt{LeftCosetsNC}}
\label{LeftCosetsNC}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DoubleCoset({\slshape G, U, elt, V})\index{DoubleCoset@\texttt{DoubleCoset}}
\label{DoubleCoset}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DoubleCosetRepresentatives({\slshape G, U, V})\index{DoubleCosetRepresentatives@\texttt{DoubleCosetRepresentatives}}
\label{DoubleCosetRepresentatives}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DoubleCosetsNC({\slshape G, U, V})\index{DoubleCosetsNC@\texttt{DoubleCosetsNC}}
\label{DoubleCosetsNC}
}\hfill{\scriptsize (operation)}}\\
If \texttt{U} is a wide subgroupoid of $G$, the \emph{right cosets} of $U$ in $G$ are the equivalence classes of the relation on the elements of $G$ where $g1$ is related to $g2$ if and only if $g2 = u*g1$ for some element $u$ of $U$. The right coset containing $g$ is written $Ug$. These right cosets refine the costars of $G$ and, in particular, $U1\_{o}$ is the costar of $U$ at $o$, so that (unlike groups) $U$ is itself a coset only when $G$ has a single object.
The \emph{right coset representatives} for $U$ in $G$ form a list containing one groupoid element for each coset where, in a
particular piece of $U$, the group element chosen is the right coset representative of the group of $U$ in the group of $G$.
Similarly, the \emph{left cosets} $gU$ refine the stars of $G$, while \emph{double cosets} are unions of left cosets and of right cosets. The operation \texttt{LeftCosetRepresentativesFromObject( G, U, obj )} is used in Chapter 4, and returns only those representatives which have tail
at \texttt{obj}.
As with stars and homsets, these cosets are implemented with representation \texttt{IsHomsetCosetsRep} and provided with an iterator. Note that, when $U$ has more than one piece, cosets may have differing lengths.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> re2 := RightCoset( Gd8, Ud8, e2 );
RightCoset(c4d,[(1,3) : -8 -> -7])
gap> for x in re2 do Print( x, "\n" ); od;
[(1,3) : -8 -> -8]
[(1,3) : -7 -> -8]
[(2,4) : -8 -> -8]
[(2,4) : -7 -> -8]
[(1,4)(2,3) : -8 -> -8]
[(1,4)(2,3) : -7 -> -8]
[(1,2)(3,4) : -8 -> -8]
[(1,2)(3,4) : -7 -> -8]
gap> rcrd8 := RightCosetRepresentatives( Gd8, Ud8 );
[ [() : -9 -> -9], [() : -9 -> -8], [() : -9 -> -7], [(2,4) : -9 -> -9],
[(2,4) : -9 -> -8], [(2,4) : -9 -> -7], [() : -8 -> -9], [() : -8 -> -8],
[() : -8 -> -7], [(2,4) : -8 -> -9], [(2,4) : -8 -> -8], [(2,4) : -8 -> -7]
]
gap> lcr7 := LeftCosetRepresentativesFromObject( Gd8, Ud8, -7 );
[ [() : -7 -> -9], [(2,4) : -7 -> -9], [() : -7 -> -8], [(2,4) : -7 -> -8] ]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Conjugation}}\logpage{[ 4, 5, 0 ]}
\hyperdef{L}{X8653FC9786E3209A}{}
{
\subsection{\textcolor{Chapter }{\texttt{\symbol{92}}\texttt{\symbol{94}}}}
\logpage{[ 4, 5, 1 ]}\nobreak
\hyperdef{L}{X8123456781234567}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{\texttt{\symbol{92}}\texttt{\symbol{94}}({\slshape e1, e2})\index{^@\texttt{\texttt{\symbol{92}}\texttt{\symbol{94}}}}
\label{^}
}\hfill{\scriptsize (operation)}}\\
When $e2 = c : p -> q$ and $e1$ has group element $b$, the conjugate $e1^e2$ has a complicated definition, but may be remembered as follows. All objects
are fixed except $p,q$, which are interchanged. For $p,q$ as source, multiply $b$ on the left by $c^-1,c$ respectively; and for $p,q$ as target, multiply $b$ on the right by $c,c^-1$. This product gives the group element of the conjugate.
}
\index{\texttt{\symbol{92}}\texttt{\symbol{94}}\texttt{\symbol{123}}\texttt{\symbol{125}} for groupoid elements}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> x := GroupoidElement( Gd8, (2,4), -9, -9 );;
gap> y := GroupoidElement( Gd8, (1,2,3,4), -8, -9 );;
gap> z := GroupoidElement( Gd8, (1,3)(2,4), -7, -8 );;
gap> Print( "\nConjugation with elements x, y, and z in Gd8:\n" );
gap> Print( "x = ", x, ", y = ", y, ", z = ", z, "\n" );
x = [(2,4) : -9 -> -9], y = [(1,2,3,4) : -8 -> -9], z = [(1,3) : -8 -> -8]
gap> Print( "x^x = ", x^x, ", x^y = ", x^y, ", x^z = ", x^z, "\n" );
x^x = [(2,4) : -9 -> -9], x^y = [(1,3) : -8 -> -8], x^z = [(2,4) : -9 -> -9]
gap> Print( "y^x = ", y^x, ", y^y = ", y^y, ", y^z = ", y^z, "\n" );
y^x = [() : -8 -> -9], y^y = [(1,4,3,2) : -9 -> -8], y^z = [(1,4)(2,3) : -8 -> -9]
gap> Print( "z^x = ", z^x, ", z^y = ", z^y, ", z^z = ", z^z, "\n" );
z^x = [(1,3) : -8 -> -8], z^y = [(2,4) : -9 -> -9], z^z = [(1,3) : -8 -> -8]
\end{Verbatim}
}
More examples of all these operations may be found in the example file \texttt{gpd/examples/gpd.g}. }
\chapter{\textcolor{Chapter }{Homomorphisms of Groupoids}}\label{chap-gpdhom}
\logpage{[ 5, 0, 0 ]}
\hyperdef{L}{X879ED2A7878B5A7A}{}
{
A \emph{homomorphism} $m$ from a groupoid $G$ to a groupoid $H$ consists of a map from the objects of $G$ to those of $H$ together with a map from the elements of $G$ to those of $H$ which is compatible with tail and head and which preserves multiplication:
\[ m(g1 : o1 \to o2)*m(g2 : o2 \to o3) ~=~ m(g1*g2 : o1 \to o3). \]
Note that when a homomorphism is not injective on objects, the image of the
source need not be a subgroupoid of the range. The simplest example of this is
given by homomorphism the two-object groupoid with trivial group to the free
group $\langle a \rangle$ on one generator, when the image is $[1,a,a^{-1}]$.
\section{\textcolor{Chapter }{Homomorphisms to a connected groupoid}}\logpage{[ 5, 1, 0 ]}
\hyperdef{L}{X7EAAB2A97E097FB6}{}
{
\subsection{\textcolor{Chapter }{GroupoidHomomorphism}}
\logpage{[ 5, 1, 1 ]}\nobreak
\hyperdef{L}{X8013645279DEEB6F}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GroupoidHomomorphism({\slshape args})\index{GroupoidHomomorphism@\texttt{GroupoidHomomorphism}}
\label{GroupoidHomomorphism}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GroupoidHomomorphismFromSinglePiece({\slshape src, rng, hom, imobs})\index{GroupoidHomomorphismFromSinglePiece@\texttt{GroupoidHomomorphismFromSinglePiece}}
\label{GroupoidHomomorphismFromSinglePiece}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Source({\slshape hom})\index{Source@\texttt{Source}}
\label{Source}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Range({\slshape hom})\index{Range@\texttt{Range}}
\label{Range}
}\hfill{\scriptsize (attribute)}}\\
As usual, there are a variety of homomorphism constructors. The basic
construction is a homomorphism $G \to H$ with $H$ connected, which is implemented as \texttt{IsHomomorphismToSinglePieceGroupoidRep} with attributes \texttt{Source}, \texttt{Range} and \texttt{PieceImages}. If $G$ is also connected, we may apply \texttt{HomomorphismOfSinglePieceGroupoids}, requiring:
\begin{itemize}
\item a homomorphism \texttt{hom} from the group of $G$ to the group of $H$.
\item a list \texttt{imobs} of the images of the objects of $G$;
\end{itemize}
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> d12 := Group( (15,16,17,18,19,20, (15,20)(16,19)(17,18) );;
gap> Gd12 := SinglePieceGroupoid( [-37,-36,-35,-34], d12 );;
gap> SetName( d12, "d12" ); SetName( Gd12, "Gd12" );
gap> s3d := Subgroup( d12, [ (15,17,19)(16,18,20), (15,20)(16,19)(17,18) ] );
gap> Gs3d := SubgroupoidByPieces( Gd12, [ [[-36,-35,-34], s3d] ] );;
gap> SetName( s3d, "s3d" ); SetName( Gs3d, "Gs3d" );
gap> gend8 := GeneratorsOfGroup( d8 );;
gap> imhd8 := [ ( ), (15,20)(16,19)(17,18) ];;
gap> hd8 := GroupHomomorphismByImages( d8, s3d, gend8, imhd8 );
gap> homd8 := GroupoidHomomorphism( Gd8, Gs3d, hd8, [-34,-35,-36] );
groupoid homomorphism : Gd8 -> Gs3d
gap> IsBijectiveOnObjects( homd8 );
true
gap> Display( homd8 );
groupoid mapping: [ Gd8 ] -> [ Gs3d ]
root homomorphism: [ [ (1,2,3,4), (1,3) ], [ (), (15,20)(16,19)(17,18) ] ]
images of objects: [ -34, -35, -36 ]
images of rays: [ (), (), () ]
\end{Verbatim}
}
}
\chapter{\textcolor{Chapter }{Graphs of Groups and Groupoids}}\label{chap-ggraph}
\logpage{[ 6, 0, 0 ]}
\hyperdef{L}{X78063DC8847554B4}{}
{
This package was originally designed to implement \emph{graphs of groups}, a notion introduced by Serre in \cite{Serre}. It was only when this was extended to \emph{graphs of groupoids} that the functions for groupoids, described in the previous chapters, were
required. The methods described here are based on Philip Higgins' paper \cite{HiJLMS}. For further details see Chapter 2 of \cite{emma-thesis}. 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.
\section{\textcolor{Chapter }{Digraphs}}\logpage{[ 6, 1, 0 ]}
\hyperdef{L}{X7D554C5D7FDC3D02}{}
{
\subsection{\textcolor{Chapter }{FpWeightedDigraph}}
\logpage{[ 6, 1, 1 ]}\nobreak
\hyperdef{L}{X85BD6D2584D8A22F}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FpWeightedDigraph({\slshape verts, arcs})\index{FpWeightedDigraph@\texttt{FpWeightedDigraph}}
\label{FpWeightedDigraph}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsFpWeightedDigraph({\slshape dig})\index{IsFpWeightedDigraph@\texttt{IsFpWeightedDigraph}}
\label{IsFpWeightedDigraph}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InvolutoryArcs({\slshape dig})\index{InvolutoryArcs@\texttt{InvolutoryArcs}}
\label{InvolutoryArcs}
}\hfill{\scriptsize (attribute)}}\\
A \emph{weighted digraph} is a record with two components: \emph{vertices}, which are usually taken to be positive integers (to distinguish them from
the objects in a groupoid); and \emph{arcs}, which take the form of 3-element lists \texttt{[weight,tail,head]}. The \emph{tail} and \emph{head} are the two vertices of the arc. The \emph{weight} is taken to be an element of a finitely presented group, so as to produce
digraphs of type \texttt{IsFpWeightedDigraph}.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ]
\end{Verbatim}
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 \texttt{[y,5,6]} as the data and get the function to construct the reverse edge. The attribute \texttt{InvolutoryArcs} returns a list of the positions of each inverse arc in the list of arcs. In
the second example the graph is a complete digraph on three vertices.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Graphs of Groups}}\logpage{[ 6, 2, 0 ]}
\hyperdef{L}{X7BAFCA3680E478AE}{}
{
\subsection{\textcolor{Chapter }{GraphOfGroups}}
\logpage{[ 6, 2, 1 ]}\nobreak
\hyperdef{L}{X8130246E854BC5D9}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroups({\slshape dig, gps, sgps, isos})\index{GraphOfGroups@\texttt{GraphOfGroups}}
\label{GraphOfGroups}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DigraphOfGraphOfGroups({\slshape gg})\index{DigraphOfGraphOfGroups@\texttt{DigraphOfGraphOfGroups}}
\label{DigraphOfGraphOfGroups}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GroupsOfGraphOfGroups({\slshape gg})\index{GroupsOfGraphOfGroups@\texttt{GroupsOfGraphOfGroups}}
\label{GroupsOfGraphOfGroups}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SubgroupsOfGraphOfGroups({\slshape gg})\index{SubgroupsOfGraphOfGroups@\texttt{SubgroupsOfGraphOfGroups}}
\label{SubgroupsOfGraphOfGroups}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismsOfGraphOfGroups({\slshape gg})\index{IsomorphismsOfGraphOfGroups@\texttt{IsomorphismsOfGraphOfGroups}}
\label{IsomorphismsOfGraphOfGroups}
}\hfill{\scriptsize (attribute)}}\\
A graph of groups is traditionally defined as consisting of:
\begin{itemize}
\item a digraph with involutory pairs of arcs;
\item a \emph{vertex group} associated to each vertex;
\item a group associated to each pair of arcs;
\item an injective homomorphism from each arc group to the group at the head of the
arc.
\end{itemize}
We have found it more convenient to associate to each arc:
\begin{itemize}
\item a subgroup of the vertex group at the tail;
\item a subgroup of the vertex group at the head;
\item an isomorphism between these subgroups, such that each involutory pair of arcs
determines inverse isomorphisms.
\end{itemize}
These two viewpoints are clearly equivalent.
In this implementation we require that all subgroups are of finite index in
the vertex groups.
The four attributes provide a means of calling the four items of data in the
construction of a graph of groups.
We shall be representing free products with amalgamation of groups and HNN
extensions of groups, so we take as our first example the trefoil group with
generators $a,b$ and relation $a^3=b^2$. For this we take digraph \texttt{D1} above with an infinite cyclic group at each vertex, generated by $a$ and $b$ respectively. The two subgroups will be generated by $a^3$ and $b^2$ with the obvious isomorphisms.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ] ] ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{IsGraphOfFpGroups}}
\logpage{[ 6, 2, 2 ]}\nobreak
\hyperdef{L}{X847464677F641527}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfFpGroups({\slshape gg})\index{IsGraphOfFpGroups@\texttt{IsGraphOfFpGroups}}
\label{IsGraphOfFpGroups}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfPcGroups({\slshape gg})\index{IsGraphOfPcGroups@\texttt{IsGraphOfPcGroups}}
\label{IsGraphOfPcGroups}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfPermGroups({\slshape gg})\index{IsGraphOfPermGroups@\texttt{IsGraphOfPermGroups}}
\label{IsGraphOfPermGroups}
}\hfill{\scriptsize (property)}}\\
This is a list of properties to be expected of a graph of groups. In principle
any type of group known to \textsf{GAP} may be used as vertex groups, though these types are not normally mixed in a
single structure. }
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> IsGraphOfFpGroups( G1 );
true
gap> IsomorphismsOfGraphOfGroups( G1 );
[ [ a^3 ] -> [ b^2 ], [ b^2 ] -> [ a^3 ] ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{RightTransversalsOfGraphOfGroups}}
\logpage{[ 6, 2, 3 ]}\nobreak
\hyperdef{L}{X7B036C2B84E48BB1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightTransversalsOfGraphOfGroups({\slshape gg})\index{RightTransversalsOfGraphOfGroups@\texttt{RightTransversalsOfGraphOfGroups}}
\label{RightTransversalsOfGraphOfGroups}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LeftTransversalsOfGraphOfGroups({\slshape gg})\index{LeftTransversalsOfGraphOfGroups@\texttt{LeftTransversalsOfGraphOfGroups}}
\label{LeftTransversalsOfGraphOfGroups}
}\hfill{\scriptsize (attribute)}}\\
Computation with graph of groups words will require, for each arc subgroup \texttt{ha}, a set of representatives for the left cosets of \texttt{ha} in the tail vertex group. As already pointed out, we require subgroups of
finite index. Since \textsf{GAP} prefers to provide right cosets, we obtain the right representatives first,
and then invert them.
When the vertex groups are of type \texttt{FpGroup} we shall require normal forms for these groups, so we assume that such vertex
groups are provided with Knuth Bendix rewriting systems using functions from
the main \textsf{GAP} library, (e.g. \texttt{IsomorphismFpSemigroup}).
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> RTG1 := RightTransversalsOfGraphOfGroups( G1 );
[ [ <identity ...>, a, a^2 ], [ <identity ...>, b ] ]
gap> LTG1 := LeftTransversalsOfGraphOfGroups( G1 );
[ [ <identity ...>, a^-1, a^-2 ], [ <identity ...>, b^-1 ] ]
\end{Verbatim}
}
\section{\textcolor{Chapter }{Words in a Graph of Groups and their normal forms}}\logpage{[ 6, 3, 0 ]}
\hyperdef{L}{X7BD9DCF87FB3E0AF}{}
{
\subsection{\textcolor{Chapter }{GraphOfGroupsWord}}
\logpage{[ 6, 3, 1 ]}\nobreak
\hyperdef{L}{X87937AE47C5B1018}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroupsWord({\slshape gg, tv, list})\index{GraphOfGroupsWord@\texttt{GraphOfGroupsWord}}
\label{GraphOfGroupsWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfGroupsWord({\slshape w})\index{IsGraphOfGroupsWord@\texttt{IsGraphOfGroupsWord}}
\label{IsGraphOfGroupsWord}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroupsOfWord({\slshape w})\index{GraphOfGroupsOfWord@\texttt{GraphOfGroupsOfWord}}
\label{GraphOfGroupsOfWord}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordOfGraphOfGroupsWord({\slshape w})\index{WordOfGraphOfGroupsWord@\texttt{WordOfGraphOfGroupsWord}}
\label{WordOfGraphOfGroupsWord}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GGTail({\slshape w})\index{GGTail@\texttt{GGTail}}
\label{GGTail}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GGHead({\slshape w})\index{GGHead@\texttt{GGHead}}
\label{GGHead}
}\hfill{\scriptsize (attribute)}}\\
If \texttt{G} is a graph of groups with underlying digraph \texttt{D}, the following groupoids may be considered. First there is the free groupoid
or path groupoid on \texttt{D}. Since we want each involutory pair of arcs to represent inverse elements in
the groupoid, we quotient out by the relations \texttt{y\texttt{\symbol{92}}\texttt{\symbol{94}}\texttt{\symbol{123}}\texttt{\symbol{125}}-1
= ybar} to obtain \texttt{PG(D)}. Secondly, there is the discrete groupoid \texttt{VG(D)}, namely the union of all the vertex groups. Since these two groupoids have
the same object set (the vertices of \texttt{D}) we can form \texttt{A(G)}, the free product of \texttt{PG(D)} and \texttt{VG(D)} amalgamated over the vertices. For further details of this universal groupoid
construction see \cite{emma-thesis}. (Note that these groupoids are not implemented in this package.)
An element of \texttt{A(G)} is a graph of groups word which may be represented by a list of the form $w = [g_1,y_1,g_2,y_2,...,g_n,y_n,g_{n+1}]$. Here each $y_i$ is an arc of \texttt{D}; the head of $y_{i-1}$ is a vertex $v_i$ which is also the tail of $y_i$; and $g_i$ is an element of the vertex group at $v_i$.
The attributes \texttt{GGTail} and \texttt{GGHead} are \emph{temporary} names for the tail and head of a graph of groups word, and are likely to be
replaced in future versions.
So a graph of groups word requires as data the graph of groups; the tail
vertex for the word; and a list of arcs and group elements. We may specify
each arc by its position in the list of arcs.
In the following example, where \texttt{gw1} is a word in the trefoil graph of groups, the $y_i$ are specified by their positions in \texttt{A1}. Both arcs are traversed twice, so the resulting word is a loop at vertex $5$.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{ReducedGraphOfGroupsWord}}
\logpage{[ 6, 3, 2 ]}\nobreak
\hyperdef{L}{X78FA7C3F831AA6E4}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ReducedGraphOfGroupsWord({\slshape w})\index{ReducedGraphOfGroupsWord@\texttt{ReducedGraphOfGroupsWord}}
\label{ReducedGraphOfGroupsWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsReducedGraphOfGroupsWord({\slshape w})\index{IsReducedGraphOfGroupsWord@\texttt{IsReducedGraphOfGroupsWord}}
\label{IsReducedGraphOfGroupsWord}
}\hfill{\scriptsize (property)}}\\
A graph of groups word may be reduced in two ways, to give a normal form.
Firstly, if part of the word has the form \texttt{[yi, identity, yibar]} then this subword may be omitted. This is known as a length reduction.
Secondly there are coset reductions. Working from the left-hand end of the
word, subwords of the form $[g_i,y_i,g_{i+1}]$ are replaced by $[t_i,y_i,m_i(h_i)*g_{i+1}]$ where $g_i = t_i*h_i$ is the unique factorisation of $g_i$ as a left coset representative times an element of the arc subgroup, and $m_i$ is the isomorphism associated to $y_i$. Thus we may consider a coset reduction as passing a subgroup element along
an arc. The resulting normal form (if no length reductions have taken place)
is then $[t_1,y_1,t_2,y_2,...,t_n,y_n,k]$ for some $k$ in the head group of $y_n$. For further details see Section 2.2 of \cite{emma-thesis}.
The reduction of the word \texttt{gw1} in our example includes one length reduction. The four stages of the reduction
are as follows:
\[ a^7b^{-6}a^{-11}b^9a^7 ~\mapsto~ a^{-2}b^0a^{-11}b^9a^7 ~\mapsto~
a^{-13}b^9a^7 ~\mapsto~ a^{-1}b^{-8}b^9a^7 ~\mapsto~ a^{-1}b^{-1}a^{10}. \]
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
gap> nw1 := ReducedGraphOfGroupsWord( gw1 );
(5)a^-1.y.b^-1.y^-1.a^10(5)
\end{Verbatim}
}
\section{\textcolor{Chapter }{Free products with amalgamation and HNN extensions}}\logpage{[ 6, 4, 0 ]}
\hyperdef{L}{X7D99A7B37B36BAA8}{}
{
\subsection{\textcolor{Chapter }{FreeProductWithAmalgamation}}
\logpage{[ 6, 4, 1 ]}\nobreak
\hyperdef{L}{X795AB71F7E370119}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FreeProductWithAmalgamation({\slshape gp1, gp2, iso})\index{FreeProductWithAmalgamation@\texttt{FreeProductWithAmalgamation}}
\label{FreeProductWithAmalgamation}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsFpaGroup({\slshape fpa})\index{IsFpaGroup@\texttt{IsFpaGroup}}
\label{IsFpaGroup}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroupsRewritingSystem({\slshape fpa})\index{GraphOfGroupsRewritingSystem@\texttt{GraphOfGroupsRewritingSystem}}
\label{GraphOfGroupsRewritingSystem}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{NormalFormGGRWS({\slshape fpa, word})\index{NormalFormGGRWS@\texttt{NormalFormGGRWS}}
\label{NormalFormGGRWS}
}\hfill{\scriptsize (attribute)}}\\
As we have seen with the trefoil group example, graphs of groups can be used
to obtain a normal form for free products with amalgamation $G_1 *_H G_2$ when $G_1, G_2$ both have rewrite systems, and $H$ is of finite index in both $G_1$ and $G_2$.
When \texttt{gp1} and \texttt{gp2} are fp-groups, the operation \texttt{FreeProductWithAmalgamation} constructs the required fp-group. When the two groups are permutation groups,
the \texttt{IsomorphismFpGroup} operation is called on both \texttt{gp1} and \texttt{gp2}, and the resulting isomorphism is transported to one between the two new
subgroups.
The attribute \texttt{GraphOfGroupsRewritingSystem} of \texttt{fpa} is the graph of groups which has underlying digraph \texttt{D1}, with two vertices and two arcs; the two groups as vertex groups; and the
specified isomorphisms on the arcs. Despite the name, graphs of groups
constructed in this way \emph{do not} belong to the category \texttt{IsRewritingSystem}. This anomaly may be dealt with when time permits.
The example below shows a computation in the the free product of the symmetric \texttt{s3} and the alternating \texttt{a4}, amalgamated over a cyclic subgroup \texttt{c3}.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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
\end{Verbatim}
\subsection{\textcolor{Chapter }{HnnExtension}}
\logpage{[ 6, 4, 2 ]}\nobreak
\hyperdef{L}{X7CB0F120804A8DED}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{HnnExtension({\slshape gp, iso})\index{HnnExtension@\texttt{HnnExtension}}
\label{HnnExtension}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsHnnGroup({\slshape hnn})\index{IsHnnGroup@\texttt{IsHnnGroup}}
\label{IsHnnGroup}
}\hfill{\scriptsize (property)}}\\
For \emph{HNN extensions}, the appropriate graph of groups has underlying digraph with just one vertex
and one pair of loops, weighted with \texttt{FpGroup} generators $z,z^{-1}$. There is one vertex group \texttt{G}, two isomorphic subgroups \texttt{H1,H2} of \texttt{G}, with the isomorphism and its inverse on the loops. The presentation of the
extension has one more generator than that of \texttt{G} and corresponds to the generator $z$.
The functions \texttt{GraphOfGroupsRewritingSystem} and \texttt{NormalFormGGRWS} may be applied to hnn-groups as well as to fpa-groups.
In the example we take \texttt{G=a4} and the two subgroups are cyclic groups of order 3. }
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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
\end{Verbatim}
Both fpa-groups and hnn-groups are provided with a record attribute, \texttt{FpaInfo(fpa)} and \texttt{HnnInfo(hnn)} respectively, storing the groups and isomorphisms involved in their
construction.
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ] )
\end{Verbatim}
}
\section{\textcolor{Chapter }{GraphsOfGroupoids and their Words}}\logpage{[ 6, 5, 0 ]}
\hyperdef{L}{X78108FB4814AE887}{}
{
\subsection{\textcolor{Chapter }{GraphOfGroupoids}}
\logpage{[ 6, 5, 1 ]}\nobreak
\hyperdef{L}{X8739267678808E85}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroupoids({\slshape dig, gpds, subgpds, isos})\index{GraphOfGroupoids@\texttt{GraphOfGroupoids}}
\label{GraphOfGroupoids}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfPermGroupoids({\slshape gg})\index{IsGraphOfPermGroupoids@\texttt{IsGraphOfPermGroupoids}}
\label{IsGraphOfPermGroupoids}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfFpGroupoids({\slshape gg})\index{IsGraphOfFpGroupoids@\texttt{IsGraphOfFpGroupoids}}
\label{IsGraphOfFpGroupoids}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GroupoidsOfGraphOfGroupoids({\slshape gg})\index{GroupoidsOfGraphOfGroupoids@\texttt{GroupoidsOfGraphOfGroupoids}}
\label{GroupoidsOfGraphOfGroupoids}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DigraphOfGraphOfGroupoids({\slshape gg})\index{DigraphOfGraphOfGroupoids@\texttt{DigraphOfGraphOfGroupoids}}
\label{DigraphOfGraphOfGroupoids}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SubgroupoidsOfGraphOfGroupoids({\slshape gg})\index{SubgroupoidsOfGraphOfGroupoids@\texttt{SubgroupoidsOfGraphOfGroupoids}}
\label{SubgroupoidsOfGraphOfGroupoids}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsomorphismsOfGraphOfGroupoids({\slshape gg})\index{IsomorphismsOfGraphOfGroupoids@\texttt{IsomorphismsOfGraphOfGroupoids}}
\label{IsomorphismsOfGraphOfGroupoids}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightTransversalsOfGraphOfGroupoids({\slshape gg})\index{RightTransversalsOfGraphOfGroupoids@\texttt{RightTransversalsOfGraphOfGroupoids}}
\label{RightTransversalsOfGraphOfGroupoids}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LefvtTransversalsOfGraphOfGroupoids({\slshape gg})\index{LefvtTransversalsOfGraphOfGroupoids@\texttt{LefvtTransversalsOfGraphOfGroupoids}}
\label{LefvtTransversalsOfGraphOfGroupoids}
}\hfill{\scriptsize (attribute)}}\\
Graphs of groups generalise naturally to graphs of groupoids, forming the
class \texttt{IsGraphOfGroupoids}. There is now a groupoid at each vertex and the isomorphism on an arc
identifies wide subgroupoids at the tail and at the head. Since all
subgroupoids are wide, every groupoid in a connected constituent of the graph
has the same number of objects, but there is no requirement that the object
sets are all the same.
The example below generalises the trefoil group example in subsection 4.4.1,
taking at each vertex of \texttt{D1} a two-object groupoid with a free group on one generator, and full
subgroupoids with groups $\langle a^3 \rangle$ and $\langle b^2 \rangle$.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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 ]
\end{Verbatim}
\subsection{\textcolor{Chapter }{GraphOfGroupoidsWord}}
\logpage{[ 6, 5, 2 ]}\nobreak
\hyperdef{L}{X7EC1A9067FC91255}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroupoidsWord({\slshape gg, tv, list})\index{GraphOfGroupoidsWord@\texttt{GraphOfGroupoidsWord}}
\label{GraphOfGroupoidsWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsGraphOfGroupoidsWord({\slshape w})\index{IsGraphOfGroupoidsWord@\texttt{IsGraphOfGroupoidsWord}}
\label{IsGraphOfGroupoidsWord}
}\hfill{\scriptsize (property)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GraphOfGroupoidsOfWord({\slshape w})\index{GraphOfGroupoidsOfWord@\texttt{GraphOfGroupoidsOfWord}}
\label{GraphOfGroupoidsOfWord}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordOfGraphOfGroupoidsWord({\slshape w})\index{WordOfGraphOfGroupoidsWord@\texttt{WordOfGraphOfGroupoidsWord}}
\label{WordOfGraphOfGroupoidsWord}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ReducedGraphOfGroupoidsWord({\slshape w})\index{ReducedGraphOfGroupoidsWord@\texttt{ReducedGraphOfGroupoidsWord}}
\label{ReducedGraphOfGroupoidsWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsReducedGraphOfGroupoidsWord({\slshape w})\index{IsReducedGraphOfGroupoidsWord@\texttt{IsReducedGraphOfGroupoidsWord}}
\label{IsReducedGraphOfGroupoidsWord}
}\hfill{\scriptsize (property)}}\\
Having produced the graph of groupoids \texttt{gg3}, we may construct left coset representatives; choose a graph of groupoids
word; and reduce this to normal form. Compare the \texttt{nw3} below with the normal form \texttt{nw1} in subsection 4.3.2.
}
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
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)
\end{Verbatim}
}
More examples of these operations may be found in the example file \texttt{gpd/examples/ggraph.g}. }
\chapter{\textcolor{Chapter }{Development History}}\label{history}
\logpage{[ 7, 0, 0 ]}
\hyperdef{L}{X810C43BC7F63C4B4}{}
{
\section{\textcolor{Chapter }{Versions of the Package}}\logpage{[ 7, 1, 0 ]}
\hyperdef{L}{X8192EA4C7B7CC5CD}{}
{
The first version, \textsf{GraphGpd} 1.001, formed part of Emma Moore's thesis \cite{emma-thesis} in December 2000, but was not made generally available.
Version 1.002 of \textsf{GraphGpd} was prepared to run under \textsf{GAP} 4.4 in January 2004; was submitted to the \textsf{GAP} council to be considered as an accepted package; but suggestions from the
referee were not followed up.
In April 2006 the manual was converted to \textsf{GAPDoc} format. Variables \texttt{Star}, \texttt{Costar} and \texttt{CoveringGroup} were found to conflict with usage in other packages, and were renamed \texttt{VertexStar}, \texttt{VertexCostar} and \texttt{CoveringGroupOfGroupoid} respectively. Similarly, the \texttt{Vertices} and \texttt{Arcs} of an \texttt{FpWeightedDigraph} were changed from attributes to record components.
In the spring of 2006 the package was extensively rewritten and renamed \textsf{Gpd}. Version 1.01 was submitted as a deposited package in June 2006. Version
1.03, of October 2007, fixed some file protections, and introduced the test
file \texttt{gpd{\textunderscore}manual.tst}.
Version 1.05, of November 2008, was released because the website at Bangor
changed.
\emph{A further extensive rewrite is in progress, introducing magmas with objects
and their mappings, but many of the functions fail to work at present, and
this manual is far from correct.} }
\section{\textcolor{Chapter }{What needs to be done next?}}\logpage{[ 7, 2, 0 ]}
\hyperdef{L}{X82148FB77CC3CCC0}{}
{
Computationally, there are three types of connected groupoid:
\begin{itemize}
\item those with identical object groups,
\item those with object groups conjugate in some supergroup,
\item those with object groups which are simply isomorphic.
\end{itemize}
\textsf{GraphGpd} attempted to implement the second case, while \textsf{Gpd} 1.01 and 1.03 considered only the first case, and \textsf{Gpd} 1.05 extended 1.03 to the second case. Here are some other immediate
requirements:
\begin{itemize}
\item Automorphism group of a groupoid.
\item normal subgroupoids and quotient groupoids;
\item more methods for morphisms of groupoids, particularly when the range is not
connected;
\item \texttt{ImageElm} and \texttt{ImagesSource} for the cases of groupoid morphisms not yet covered;
\item \texttt{Enumerator} for \texttt{IsHomsetCosetsRep};
\item free groupoid on a graph;
\item methods for \texttt{FreeProductWithAmalgamation} and \texttt{HnnEntension} for pc-groups;
\item convert \texttt{GraphOfGroupsRewritingSystem} to the category \texttt{IsRewritingSystem};
\item in \textsf{XMod}, implement crossed modules over groupoids.
\end{itemize}
}
}
\def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}
\bibliographystyle{alpha}
\bibliography{manual}
\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}
\printindex
\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}
