In this section, we describe the functions in GAP for creating and computing with McAlister triple semigroups and their subsemigroups. This implementation is based on the section in Chapter 5 of [How95] but differs from the treatment in Howie by using right actions instead of left. Some definitions found in the documentation are changed for this reason.
The importance of the McAlister triple semigroups lies in the fact that they are exactly the E-unitary inverse semigroups, which are an important class in the study of inverse semigroups.
First we define E-unitary inverse semigroups. It is standard to denote the subsemigroup of a semigroup consisting of its idempotents by E. A semigroup S is said to be E-unitary if for all e in E and for all s in S:
es ∈ E implies s ∈ E,
se ∈ E implies s ∈ E.
For inverse semigroups these two conditions are equivalent. We are only interested in E-unitary inverse semigroups. Before defining McAlister triple semigroups we define a McAlister triple. A McAlister triple is a triple (G,X,Y) which consists of:
a partial order X,
a subset Y of X,
a group G which acts on X, on the right, by order automorphisms. That means for all A,B ∈ X and for all g ∈ G: A ≤ B if and only if Ag ≤ Bg.
Furthermore, (G,X,Y) must satisfy the following four properties to be a McAlister triple:
Y is a subset of X which is a join-semilattice together with the restriction of the order relation of X to Y.
Y is an order ideal of X. That is to say, for all A ∈ X and for all B ∈ Y: if A ≤ B, then A ∈ Y.
Every element of X is the image of some element in Y moved by an element of G. That is to say, for every A ∈ X, there exists some B ∈ Y and there exists g ∈ G such that A = Bg.
Finally, for all g ∈ G, the intersection {yg : y ∈ Y} ∩ Y is non-empty.
We may define an E-unitary inverse semigroup using a McAlister triple. Given (G,X,Y) let M(G,X,Y) be the set of all pairs (A,g) in Y x G such that A acted on by the inverse of g is in Y together with multiplication defined by
(A,g)*(B,h) = (Join(A,Bg^-1),hg)
where Join is the natural join operation of the semilattice and Bg^-1 is B acted on by the inverse of g. With this operation, M(G,X,Y) is a semigroup which we call a McAlister triple semigroup over (G,X,Y). In fact every McAlister triple semigroup is an E-unitary inverse semigroup and every E-unitary inverse semigroup is isomorphic to some McAlister triple semigroup. Note that there need not be a unqiue McAlister triple semigroup for a particular McAlister triple because in general there is more than one way for a group to act on a partial order.
‣ IsMcAlisterTripleSemigroup( S ) | ( filter ) |
Returns: true or false.
This function returns true if S is a McAlister triple semigroup. A McAlister triple semigroup is a special representation of an E-unitary inverse semigroup IsEUnitaryInverseSemigroup (16.2-3) created by McAlisterTripleSemigroup (12.1-2).
‣ McAlisterTripleSemigroup( G, X, Y[, act] ) | ( operation ) |
Returns: A McAlister triple semigroup.
The following documentation covers the technical information needed to create McAlister triple semigroups in GAP, the underlying theory can be read in the introduction to Chapter 12.
In this implementation the partial order X of a McAlister triple is represented by a Digraph (Digraphs: Digraph) object X. The digraph represents a partial order in the sense that vertices are the elements of the partial order and the order relation is defined by A ≤ B if and only if there is an edge from B to A. The semilattice Y of the McAlister triple should be an induced subdigraph Y of X and the DigraphVertexLabels (Digraphs: DigraphVertexLabels) must correspond to the vertices of X on which Y is induced. That means that the following:
Y = InducedSubdigraph(X, DigraphVertexLabels(Y))
must return true. Herein if we say that a vertex A of X is 'in' Y then we mean there is a vertex of Y whose label is A. Alerternatively the user may choose to give the argument Y as the vertices of X on which Y is the induced subdigraph.
A McAlister triple semigroup is created from a quadruple (G, X, Y, act) where:
G is a finite group.
X is a digraph satisfying IsPartialOrderDigraph (Digraphs: IsPartialOrderDigraph).
Y is a digraph satisfying IsJoinSemilatticeDigraph (Digraphs: IsJoinSemilatticeDigraph) which is an induced subdigraph of X satisfying the aforementioned labeling criteria. Furthermore the OutNeighbours (Digraphs: OutNeighbours) of each vertex of X which is in Y must contain only vertices which are in Y.
act is a function which takes as its first argument a vertex of the digraph X, its second argument should be an element of G, and it must return a vertex of X. act must be a right action, meaning that act(A,gh)=act(act(A,g),h) holds for all A in X and g,h ∈ G. Furthermore the permutation represenation of this action must be a subgroup of the automorphism group of X. That means we require the following to return true:
IsSubgroup(AutomorphismGroup(X), Image(ActionHomomorphism(G, DigraphVertices(X), act));
Furthermore every vertex of X must be in the orbit of some vertex of X which is in Y. Finally, act must fix the vertex of X which is the minimal vertex of Y, i.e. the unique vertex of Y whose only out-neighbour is itself.
For user convienience, there are multiple versions of McAlisterTripleSemigroup. When the argument act is ommitted it is assumed to be OnPoints (Reference: OnPoints). Additionally, the semilattice argument Y may be replaced by a homogeneous list sub_ver of vertices of X. When sub_ver is provided, McAlisterTripleSemigroup is called with Y equalling InducedSubdigraph(X, sub_ver) with the appropriate labels.
gap> x := Digraph([[1], [1, 2], [1, 2, 3], [1, 4], [1, 4, 5]]); <immutable digraph with 5 vertices, 11 edges> gap> y := InducedSubdigraph(x, [1, 4, 5]); <immutable digraph with 3 vertices, 6 edges> gap> DigraphVertexLabels(y); [ 1, 4, 5 ] gap> A := AutomorphismGroup(x); Group([ (2,4)(3,5) ]) gap> S := McAlisterTripleSemigroup(A, x, y, OnPoints); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> T := McAlisterTripleSemigroup(A, x, y); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> S = T; false gap> IsIsomorphicSemigroup(S, T); true
‣ McAlisterTripleSemigroupGroup( S ) | ( attribute ) |
Returns: A group.
Returns the group used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (12.1-2).
‣ McAlisterTripleSemigroupPartialOrder( S ) | ( attribute ) |
Returns: A partial order digraph.
Returns the IsPartialOrderDigraph (Digraphs: IsPartialOrderDigraph) used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (12.1-2).
‣ McAlisterTripleSemigroupSemilattice( S ) | ( attribute ) |
Returns: A join-semilattice digraph.
Returns the IsJoinSemilatticeDigraph (Digraphs: IsJoinSemilatticeDigraph) used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (12.1-2).
‣ McAlisterTripleSemigroupAction( S ) | ( attribute ) |
Returns: A function.
Returns the action used to create the McAlister triple semigroup S via McAlisterTripleSemigroup (12.1-2).
‣ IsMcAlisterTripleSemigroupElement( x ) | ( filter ) |
‣ IsMTSE( x ) | ( filter ) |
Returns: true or false.
Returns true if x is an element of a McAlister triple semigroup; in particular, this returns true if x has been created by McAlisterTripleSemigroupElement (12.1-8). The functions IsMTSE and IsMcAlisterTripleSemigroupElement are synonyms. The mathematical description of these objects can be found in the introduction to Chapter 12.
‣ McAlisterTripleSemigroupElement( S, A, g ) | ( operation ) |
‣ MTSE( S, A, g ) | ( operation ) |
Returns: A McAlister triple semigroup element.
Returns the McAlister triple semigroup element of the McAlister triple semigroup S which corresponds to a label A of a vertex from the McAlisterTripleSemigroupSemilattice (12.1-5) of S and a group element g of the McAlisterTripleSemigroupGroup (12.1-3) of S. The pair (A,g) only represents an element of S if the following holds: A acted on by the inverse of g (via McAlisterTripleSemigroupAction (12.1-6)) is a vertex of the join-semilattice of S.
The functions MTSE and McAlisterTripleSemigroupElement are synonyms.
gap> x := Digraph([[1], [1, 2], [1, 2, 3], [1, 4], [1, 4, 5]]); <immutable digraph with 5 vertices, 11 edges> gap> y := InducedSubdigraph(x, [1, 2, 3]); <immutable digraph with 3 vertices, 6 edges> gap> A := AutomorphismGroup(x); Group([ (2,4)(3,5) ]) gap> S := McAlisterTripleSemigroup(A, x, y, OnPoints); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> T := McAlisterTripleSemigroup(A, x, y); <McAlister triple semigroup over Group([ (2,4)(3,5) ])> gap> S = T; false gap> IsIsomorphicSemigroup(S, T); true gap> a := MTSE(S, 1, (2, 4)(3, 5)); (1, (2,4)(3,5)) gap> b := MTSE(S, 2, ()); (2, ()) gap> a * a; (1, ()) gap> IsMTSE(a * a); true gap> a = MTSE(T, 1, (2, 4)(3, 5)); false gap> a * b; (1, (2,4)(3,5))
generated by GAPDoc2HTML