Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind

5 Bipartitions and blocks

In this chapter we describe the functions in Semigroups for creating and manipulating bipartitions and semigroups of bipartitions. We begin by describing what these objects are.

A partition of a set X is a set of pairwise disjoint non-empty subsets of X whose union is X.

Let n∈N, let mathbfn={1,2,...,n}, and let -mathbfn={-1,-2,...,-n}.

The partition monoid of degree n is the set of all partitions of mathbfn-mathbfn with a multiplication we describe below. To avoid conflict with other uses of the word "partition" in GAP, and to reflect their definition, we have opted to refer to the elements of the partition monoid as bipartitions of degree n; we will do so from this point on.

Let x be any bipartition of degree n. Then x is a set of pairwise disjoint non-empty subsets of mathbfn-mathbfn whose union is mathbfn-mathbfn; these subsets are called the blocks of x. A block containing elements of both mathbfn and -mathbfn is called a transverse block. If i,jmathbfn-mathbfn belong to the same block of a bipartition x, then we write (i,j)x.

Let x and y be bipartitions of equal degree. Then xy is the bipartition where i,jmathbfn-mathbfn belong to the same block of xy if there exist k(1), k(2),..., k(r)∈ mathbfn ; and one of the following holds:

• r=0 and either (i,j)∈x or (-i,-j)∈y;

• r=2s-1 for some s≥ 1 and

(i,-k(1))\in x,\ (k(1),k(2))\in y,\ (-k(2),-k(3))\in x,\ \ldots,\ (-k(2s-2),-k(2s-1))\in x,\ (k(2s-1),-j)\in y

• r=2s for some s≥ 1 and either:

(i,-k(1))\in x,\ (k(1),k(2))\in y,\ (-k(2),-k(3))\in x,\ \ldots, (k(2s-1), k(2s))\in y,\ (-k(2s), j)\in x

or

(-i,k(1))\in y,\ (-k(1),-k(2))\in x,\ (k(2),k(3))\in y,\ \ldots, (-k(2s-1), -k(2s))\in x,\ (k(2s), -j)\in y.

This product can be shown to be associative, and so the collection of bipartitions of any particular degree is a monoid; the identity element is the partition {{i,-i}:i∈mathbfn}. A bipartition is a unit if and only if each block is of the form {i,-j} for some i, jmathbfn. Hence the group of units is isomorphic to the symmetric group on mathbfn.

Let x be a bipartition of degree n. Then we define x^* to be the bipartition obtained from x by replacing i by -i and -i by -i in every block of x for all imathbfn. It is routine to verify that if x and y are arbitrary bipartitions of equal degree, then

(x^*)^*=x,\quad xx^*x=x,\quad x^*xx^*=x^*,\quad (xy)^*=y^*x^*.

In this way, the partition monoid is a regular *-semigroup.

A bipartition x of degree n is called planar if there does not exist distinct blocks A, B ∈ x, along with a, a' ∈ A and b, b' ∈ B such that a < a', b < b' and either:

• a < b < a' < b'; or

• b < a < b' < a'.

Or equivalently, x is planar if for each distinct blocks A, B ∈ x, and each a, a' ∈ A and b, b' ∈ B such that a < a' and b < b', either:

• a < a' < b < b';

• a < b < b' < a';

• b < a < a' < b'; or

• b < b' < a < a'.

From a graphical perspective, as on Page 873 in [HR05], a bipartition x of degree n is planar if it can be represented as a graph without edges crossing inside of the rectangle formed by its vertices mathbfn-mathbfn.

5.1 The family and categories of bipartitions

5.1-1 IsBipartition
 ‣ IsBipartition( obj ) ( category )

Returns: true or false.

Every bipartition in GAP belongs to the category IsBipartition. Basic operations for bipartitions are RightBlocks (5.5-4), LeftBlocks (5.5-5), ExtRepOfBipartition (5.5-3), LeftProjection (5.2-4), RightProjection (5.2-5), StarOp (5.2-6), DegreeOfBipartition (5.5-1), RankOfBipartition (5.5-2), multiplication of two bipartitions of equal degree is via *.

5.1-2 IsBipartitionCollection
 ‣ IsBipartitionCollection( obj ) ( category )

Returns: true or false.

Every collection of bipartitions belongs to the category IsBipartitionCollection. For example, bipartition semigroups belong to IsBipartitionCollection.

5.1-3 BipartitionFamily
 ‣ BipartitionFamily ( family )

The family of all bipartitions is BipartitionFamily.

5.2 Creating bipartitions

There are several ways of creating bipartitions in GAP, which are described in this section.

5.2-1 Bipartition
 ‣ Bipartition( blocks ) ( function )

Returns: A bipartition.

Bipartition returns the bipartition f with equivalence classes blocks, which should be a list of duplicate-free lists whose union is [-n..-1] union [1..n] for some positive integer n.

Bipartition returns an error if the argument does not define a bipartition.

gap> f:=Bipartition( [ [ 1, -1 ],[ 2, 3, -3 ], [ -2 ] ] );
<bipartition: [ 1, -1 ], [ 2, 3, -3 ], [ -2 ]>

5.2-2 BipartitionByIntRep
 ‣ BipartitionByIntRep( list ) ( operation )

Returns: A bipartition.

It is possible to create a bipartition using its internal representation. The argument list must be a list of positive integers not greater than n, of length 2*n, and where i appears in the list only if i-1 occurs earlier in the list.

For example, the internal representation of the bipartition with blocks

[ 1, -1 ], [ 2, 3, -2 ], [ -3 ]

has internal representation

[ 1, 2, 2, 1, 2, 3 ]

The internal representation indicates that the number 1 is in class 1, the number 2 is in class 2, the number 3 is in class 2, the number -1 is in class 1, the number -2 is in class 2, and -3 is in class 3. As another example, [ 1, 3, 2, 1 ] is not the internal representation of any bipartition since there is no 2 before the 3 in the second position.

In its first form BipartitionByIntRep verifies that the argument list is the internal representation of a bipartition.

gap> BipartitionByIntRep([ 1, 2, 2, 1, 3, 4 ]);
<bipartition: [ 1, -1 ], [ 2, 3 ], [ -2 ], [ -3 ]>

5.2-3 IdentityBipartition
 ‣ IdentityBipartition( n ) ( operation )

Returns: The identity bipartition.

Returns the identity bipartition with degree n.

gap> IdentityBipartition(10);
<block bijection: [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ],
[ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ]>

5.2-4 LeftOne
 ‣ LeftOne( f ) ( attribute )
 ‣ LeftProjection( f ) ( attribute )

Returns: A bipartition.

The LeftProjection of a bipartition f is the bipartition f*Star(f). It is so-named, since the left and right blocks of the left projection equal the left blocks of f.

The left projection e of f is also a bipartition with the property that e*f=f. LeftOne and LeftProjection are synonymous.

gap> f:=Bipartition( [ [ 1, 4, -1, -2, -6 ], [ 2, 3, 5, -4 ],
> [ 6, -3 ], [ -5 ] ] );;
gap> LeftOne(f);
<block bijection: [ 1, 4, -1, -4 ], [ 2, 3, 5, -2, -3, -5 ],
[ 6, -6 ]>
gap> LeftBlocks(f);
<blocks: [ 1, 4 ], [ 2, 3, 5 ], [ 6 ]>
gap> RightBlocks(LeftOne(f));
<blocks: [ 1, 4 ], [ 2, 3, 5 ], [ 6 ]>
gap> LeftBlocks(LeftOne(f));
<blocks: [ 1, 4 ], [ 2, 3, 5 ], [ 6 ]>
gap> LeftOne(f)*f=f;
true

5.2-5 RightOne
 ‣ RightOne( f ) ( attribute )
 ‣ RightProjection( f ) ( attribute )

Returns: A bipartition.

The RightProjection of a bipartition f is the bipartition Star(f)*f. It is so-named, since the left and right blocks of the right projection equal the right blocks of f.

The right projection e of f is also a bipartition with the property that f*e=f. RightOne and RightProjection are synonymous.

gap> f:=Bipartition( [ [ 1, -1, -4 ], [ 2, -2, -3 ], [ 3, 4 ],
> [ 5, -5 ] ] );;
gap> RightOne(f);
<block bijection: [ 1, 4, -1, -4 ], [ 2, 3, -2, -3 ], [ 5, -5 ]>
gap> RightBlocks(RightOne(f));
<blocks: [ 1, 4 ], [ 2, 3 ], [ 5 ]>
gap> LeftBlocks(RightOne(f));
<blocks: [ 1, 4 ], [ 2, 3 ], [ 5 ]>
gap> RightBlocks(f);
<blocks: [ 1, 4 ], [ 2, 3 ], [ 5 ]>
gap> f*RightOne(f)=f;
true

5.2-6 StarOp
 ‣ StarOp( f ) ( operation )
 ‣ Star( f ) ( attribute )

Returns: A bipartition.

StarOp returns the unique bipartition g with the property that: f*g*f=f, RightBlocks(f)=LeftBlocks(g), and LeftBlocks(f)=RightBlocks(g). The star g can be obtained from f by changing the sign of every integer in the external representation of f.

gap> f:=Bipartition( [ [ 1, -4 ], [ 2, 3, 4 ], [ 5 ], [ -1 ],
> [ -2, -3 ], [ -5 ] ] );
<bipartition: [ 1, -4 ], [ 2, 3, 4 ], [ 5 ], [ -1 ], [ -2, -3 ],
[ -5 ]>
gap> g:=Star(f);
<bipartition: [ 1 ], [ 2, 3 ], [ 4, -1 ], [ 5 ], [ -2, -3, -4 ],
[ -5 ]>
gap> f*g*f=f;
true
gap> LeftBlocks(f)=RightBlocks(g);
true
gap> RightBlocks(f)=LeftBlocks(g);
true

5.2-7 RandomBipartition
 ‣ RandomBipartition( n ) ( operation )

Returns: A bipartition.

If n is a positive integer, then RandomBipartition returns a random bipartition of degree n.

gap> f:=RandomBipartition(6);
<bipartition: [ 1, 2, 3, 4 ], [ 5 ], [ 6, -2, -3, -4 ], [ -1, -5 ], [ -6 ]>


5.3 Changing the representation of a bipartition

It is possible that a bipartition can be represented as another type of object, or that another type of GAP object can be represented as a bipartition. In this section, we describe the functions in the Semigroups package for changing the representation of bipartition, or for changing the representation of another type of object to that of a bipartition.

The operations AsPermutation (5.3-5), AsPartialPerm (5.3-4), AsTransformation (5.3-3) can be used to convert bipartitions into permutations, partial permutations, or transformations where appropriate.

5.3-1 AsBipartition
 ‣ AsBipartition( f[, n] ) ( operation )

Returns: A bipartition.

AsBipartition returns the bipartition, permutation, transformation, or partial permutation f, as a bipartition of degree n. There are several possible arguments for AsBipartition:

permutations

If f is a permutation and n is a positive integer, then AsBipartition(f, n) returns the bipartition on [1..n] with classes [i, i^f] for all i=1..n.

If no positive integer n is specified, then the largest moved point of f is used as the value for n; see LargestMovedPoint (Reference: LargestMovedPoint (for a permutation)).

transformations

If f is a transformation and n is a positive integer such that f is a transformation of [1..n], then AsTransformation returns the bipartition with classes (i)f^-1∪ {i} for all i in the image of f.

If the positive integer n is not specified, then the internal degree of f is used as the value for n.

partial permutations

If f is a partial permutation f and n is a positive integer, then AsBipartition returns the bipartition with classes [i, i^f] for i in [1..n]. Thus the degree of the returned bipartition is the maximum of n and the values i^f where i in [1..n].

If the optional argument n is not present, then the default value of the maximum of the largest moved point and the largest image of a moved point of f plus 1 is used.

bipartitions

If f is a bipartition and n is a non-negative integer, then AsBipartition returns a bipartition corresponding to f with degree n.

If n equals the degree of f, then f is returned. If n is less than the degree of f, then this function returns the bipartition obtained from f by removing the values exceeding n or less than -n from the blocks of f. If n is greater than the degree of f, then this function returns the bipartition with the same blocks as f and the singleton blocks i and -i for all i greater than the degree of f

gap> f:=Transformation( [ 3, 5, 3, 4, 1, 2 ] );;
gap> AsBipartition(f, 5);
<bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ], [ -2 ]>
gap> AsBipartition(f);
<bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ],
[ 6, -2 ], [ -6 ]>
gap> AsBipartition(f, 10);
<bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ],
[ 6, -2 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ], [ -6 ]>
gap> AsBipartition((1, 3)(2, 4));
<block bijection: [ 1, -3 ], [ 2, -4 ], [ 3, -1 ], [ 4, -2 ]>
gap> AsBipartition((1, 3)(2, 4), 10);
<block bijection: [ 1, -3 ], [ 2, -4 ], [ 3, -1 ], [ 4, -2 ],
[ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ]>
gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 6 ], [ 6, 7, 1, 4, 3, 2 ] );;
gap> AsBipartition(f, 11);
<bipartition: [ 1, -6 ], [ 2, -7 ], [ 3, -1 ], [ 4, -4 ], [ 5, -3 ],
[ 6, -2 ], [ 7 ], [ 8 ], [ 9 ], [ 10 ], [ 11 ], [ -5 ], [ -8 ],
[ -9 ], [ -10 ], [ -11 ]>
gap> AsBipartition(f);
<bipartition: [ 1, -6 ], [ 2, -7 ], [ 3, -1 ], [ 4, -4 ], [ 5, -3 ],
[ 6, -2 ], [ 7 ], [ -5 ]>
gap> AsBipartition(Transformation( [ 1, 1, 2 ] ), 1);
<block bijection: [ 1, -1 ]>
gap> f:=Bipartition( [ [ 1, 2, -2 ], [ 3 ], [ 4, 5, 6, -1 ],
> [ -3, -4, -5, -6 ] ] );;
gap> AsBipartition(f, 0);
<empty bipartition>
gap> AsBipartition(f, 2);
<bipartition: [ 1, 2, -2 ], [ -1 ]>
gap> AsBipartition(f, 8);
<bipartition: [ 1, 2, -2 ], [ 3 ], [ 4, 5, 6, -1 ], [ 7 ], [ 8 ],
[ -3, -4, -5, -6 ], [ -7 ], [ -8 ]>

5.3-2 AsBlockBijection
 ‣ AsBlockBijection( f[, n] ) ( operation )

Returns: A block bijection or fail.

When the argument f is a partial perm and n is a positive integer which is greater than the maximum of the degree and codegree of f, this function returns a block bijection corresponding to f. This block bijection has the same non-singleton classes as g:=AsBipartition(f, n) and one additional class which is the union the singleton classes of g.

If the optional second argument n is not present, then the maximum of the degree and codegree of f plus 1 is used by default. If the second argument n is not greater than this maximum, then fail is returned.

This is the value at f of the embedding of the symmetric inverse monoid into the dual symmetric inverse monoid given in the FitzGerald-Leech Theorem [FL98].

gap> f:=PartialPerm( [ 1, 2, 3, 6, 7, 10 ], [ 9, 5, 6, 1, 7, 8 ] ) ;
[2,5][3,6,1,9][10,8](7)
gap> AsBipartition(f, 11);
<bipartition: [ 1, -9 ], [ 2, -5 ], [ 3, -6 ], [ 4 ], [ 5 ],
[ 6, -1 ], [ 7, -7 ], [ 8 ], [ 9 ], [ 10, -8 ], [ 11 ], [ -2 ],
[ -3 ], [ -4 ], [ -10 ], [ -11 ]>
gap> AsBlockBijection(f, 10);
fail
gap> AsBlockBijection(f, 11);
<block bijection: [ 1, -9 ], [ 2, -5 ], [ 3, -6 ],
[ 4, 5, 8, 9, 11, -2, -3, -4, -10, -11 ], [ 6, -1 ], [ 7, -7 ],
[ 10, -8 ]>

5.3-3 AsTransformation
 ‣ AsTransformation( f ) ( operation )

Returns: A transformation or fail.

When the argument f is a bipartition, that mathematically defines a transformation, this function returns that transformation. A bipartition f defines a transformation if and only if its right blocks are the image list of a permutation of [1..n] where n is the degree of f.

See IsTransBipartition (5.5-9).

gap> f:=Bipartition([[ 1, -3 ], [ 2, -2 ], [ 3, 5, 10, -7 ], [ 4, -12 ],
> [ 6, 7, -6 ], [ 8, -5 ], [ 9, -11 ], [ 11, 12, -10 ], [ -1 ], [ -4 ],
> [ -8 ], [ -9 ]]);;
gap> AsTransformation(f);
Transformation( [ 3, 2, 7, 12, 7, 6, 6, 5, 11, 7, 10, 10 ] )
gap> IsTransBipartition(f);
true
gap> f:=Bipartition([[ 1, 5 ], [ 2, 4, 8, 10 ], [ 3, 6, 7, -1, -2 ],
> [ 9, -4, -6, -9 ], [ -3, -5 ], [ -7, -8 ], [ -10 ]]);;
gap> AsTransformation(f);
fail

5.3-4 AsPartialPerm
 ‣ AsPartialPerm( f ) ( operation )

Returns: A partial perm or fail.

When the argument f is a bipartition that mathematically defines a partial perm, this function returns that partial perm.

A bipartition f defines a partial perm if and only if its numbers of left and right blocks both equal its degree.

See IsPartialPermBipartition (5.5-12).

gap> f:=Bipartition( [ [ 1, -4 ], [ 2, -2 ], [ 3, -10 ], [ 4, -5 ],
> [ 5, -9 ], [ 6 ], [ 7 ], [ 8, -6 ], [ 9, -3 ], [ 10, -8 ],
> [ -1 ], [ -7 ] ] );;
gap> IsPartialPermBipartition(f);
true
gap> AsPartialPerm(f);
[1,4,5,9,3,10,8,6](2)
gap> f:=Bipartition([[ 1, -2, -4 ], [ 2, 3, 4, -3 ], [ -1 ]]);;
gap> IsPartialPermBipartition(f);
false
gap> AsPartialPerm(f);
fail

5.3-5 AsPermutation
 ‣ AsPermutation( f ) ( operation )

Returns: A permutation or fail.

When the argument f is a bipartition that mathematically defines a permutation, this function returns that permutation.

A bipartition f defines a permutation if and only if its numbers of left, right, and transverse blocks all equal its degree.

See IsPermBipartition (5.5-11).

gap> f:=Bipartition( [ [ 1, -6 ], [ 2, -4 ], [ 3, -2 ], [ 4, -5 ],
> [ 5, -3 ], [ 6, -1 ] ] );;
gap> IsPermBipartition(f);
true
gap> AsPermutation(f);
(1,6)(2,4,5,3)
gap> AsBipartition(last)=f;
true

5.4 Operators for bipartitions

f * g

returns the composition of f and g when f and g are bipartitions.

f < g

returns true if the internal representation of f is lexicographically less than the internal representation of g and false if it is not.

f = g

returns true if the bipartition f equals the bipartition g and returns false if it does not.

5.4-1 PartialPermLeqBipartition
 ‣ PartialPermLeqBipartition( x, y ) ( operation )

Returns: true or false.

If x and y are partial perm bipartitions, i.e. they satisfy IsPartialPermBipartition (5.5-12), then this function returns AsPartialPerm(x)<AsPartialPerm(y).

5.4-2 NaturalLeqPartialPermBipartition
 ‣ NaturalLeqPartialPermBipartition( x, y ) ( operation )

Returns: true or false.

The natural partial order on an inverse semigroup S is defined by st if there exists an idempotent e in S such that s=et. Hence if x and y are partial perm bipartitions, then xy if and only if AsPartialPerm(x) is a restriction of AsPartialPerm(y).

NaturalLeqPartialPermBipartition returns true if AsPartialPerm(x) is a restriction of AsPartialPerm(y) and false if it is not. Note that since this is a partial order and not a total order, it is possible that x and y are incomparable with respect to the natural partial order.

5.4-3 NaturalLeqBlockBijection
 ‣ NaturalLeqBlockBijection( x, y ) ( operation )

Returns: true or false.

The natural partial order on an inverse semigroup S is defined by st if there exists an idempotent e in S such that s=et. Hence if x and y are block bijections, then xy if and only if x contains y.

NaturalLeqBlockBijection returns true if x is contained in y and false if it is not. Note that since this is a partial order and not a total order, it is possible that x and y are incomparable with respect to the natural partial order.

gap> x:=Bipartition( [ [ 1, 2, -3 ], [ 3, -1, -2 ], [ 4, -4 ],
> [ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ],
> [ 10, -10 ] ] );;
gap> y:=Bipartition( [ [ 1, -2 ], [ 2, -1 ], [ 3, -3 ], [ 4, -4 ],
> [ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ] ] );;
gap> z:=Bipartition([Union([1..10],[-10..-1])]);;
gap> NaturalLeqBlockBijection(x, y);
false
gap> NaturalLeqBlockBijection(y, x);
false
gap> NaturalLeqBlockBijection(z, x);
true
gap> NaturalLeqBlockBijection(z, y);
true

5.4-4 PermLeftQuoBipartition
 ‣ PermLeftQuoBipartition( f, g ) ( operation )

Returns: A permutation.

If f and g are bipartitions with equal left and right blocks, then PermLeftQuoBipartition returns the permutation of the indices of the right blocks of f (and g) induced by Star(f)*g.

PermLeftQuoBipartition verifies that f and g have equal left and right blocks, and returns an error if they do not. The value returned by PermLeftQuoBipartition(f,g) is the same as that returned by PermRightBlocks(RightBlocks(f), Star(f)*g). See also PermRightBlocks (5.7-3) and OnRightBlocksBipartitionByPerm (5.4-5).

gap> f:=Bipartition( [ [ 1, 4, 6, 7, 8, 10 ], [ 2, 5, -1, -2, -8 ],
> [ 3, -3, -6, -7, -9 ], [ 9, -4, -5 ], [ -10 ] ] );;
gap> g:=Bipartition( [ [ 1, 4, 6, 7, 8, 10 ], [ 2, 5, -3, -6, -7, -9 ],
> [ 3, -4, -5 ], [ 9, -1, -2, -8 ], [ -10 ] ] );;
gap> PermLeftQuoBipartition(f, g);
(1,2,3)
gap> Star(f)*g;
<bipartition: [ 1, 2, 8, -3, -6, -7, -9 ], [ 3, 6, 7, 9, -4, -5 ],
[ 4, 5, -1, -2, -8 ], [ 10 ], [ -10 ]>
gap> PermRightBlocks(RightBlocks(f), last);
(1,2,3)

5.4-5 OnRightBlocksBipartitionByPerm
 ‣ OnRightBlocksBipartitionByPerm( f, p ) ( function )

Returns: A bipartition.

If f is a bipartition and p is a permutation of the indices of the right blocks of f, then OnRightBlocksBipartitionByPerm returns the bipartition obtained from f by rearranging the right blocks of f according to p.

gap> f:=Bipartition( [ [ 1, 4, 6, 7, 8, 10 ], [ 2, 5, -1, -2, -8 ],
> [ 3, -3, -6, -7, -9 ], [ 9, -4, -5 ], [ -10 ] ] );;
gap> OnRightBlocksBipartitionByPerm(f, (1,2,3));
<bipartition: [ 1, 4, 6, 7, 8, 10 ], [ 2, 5, -3, -6, -7, -9 ],
[ 3, -4, -5 ], [ 9, -1, -2, -8 ], [ -10 ]>

5.5 Attributes for bipartitons

In this section we describe various attributes that a bipartition can possess.

5.5-1 DegreeOfBipartition
 ‣ DegreeOfBipartition( f ) ( attribute )
 ‣ DegreeOfBipartitionCollection( f ) ( attribute )

Returns: A positive integer.

The degree of a bipartition is, roughly speaking, the number of points where it is defined. More precisely, if f is a bipartition defined on 2*n points, then the degree of f is n.

The degree of a collection coll of bipartitions of equal degree is just the degree of any (and every) bipartition in coll. The degree of collection of bipartitions of unequal degrees is not defined.

gap> f:=Bipartition( [ [ 1, 7, -3, -8 ], [ 2, 6 ], [ 3 ], [ 4, -7, -9 ],
> [ 5, 9, -2 ], [ 8, -1, -4, -6 ], [ -5 ] ] );;
gap> DegreeOfBipartition(f);
9
gap> s:=BrauerMonoid(5);
<regular bipartition monoid of degree 5 with 3 generators>
gap> IsBipartitionCollection(s);
true
gap> DegreeOfBipartitionCollection(s);
5

5.5-2 RankOfBipartition
 ‣ RankOfBipartition( f ) ( attribute )
 ‣ NrTransverseBlocks( f ) ( attribute )

Returns: The rank of a bipartition.

When the argument is a bipartition f, RankOfBipartition returns the number of blocks of f containing both positive and negative entries, i.e. the number of transverse blocks of f.

NrTransverseBlocks is just a synonym for RankOfBipartition.

gap> f:=Bipartition( [ [ 1, 2, 6, 7, -4, -5, -7 ], [ 3, 4, 5, -1, -3 ],
> [ 8, -9 ], [ 9, -2 ], [ -6 ], [ -8 ] ] );
<bipartition: [ 1, 2, 6, 7, -4, -5, -7 ], [ 3, 4, 5, -1, -3 ],
[ 8, -9 ], [ 9, -2 ], [ -6 ], [ -8 ]>
gap> RankOfBipartition(f);
4

5.5-3 ExtRepOfBipartition
 ‣ ExtRepOfBipartition( f ) ( attribute )

Returns: A partition of [1..2*n].

If n is the degree of the bipartition f, then ExtRepOfBipartition returns the partition of [-n..-1] union [1..n] corresponding to f as a sorted list of duplicate-free lists.

gap> f:=Bipartition( [ [ 1, 5, -3 ], [ 2, 4, -2, -4 ], [ 3, -1, -5 ] ] );
<block bijection: [ 1, 5, -3 ], [ 2, 4, -2, -4 ], [ 3, -1, -5 ]>
gap> ExtRepOfBipartition(f);
[ [ 1, 5, -3 ], [ 2, 4, -2, -4 ], [ 3, -1, -5 ] ]

5.5-4 RightBlocks
 ‣ RightBlocks( f ) ( attribute )

Returns: The right blocks of a bipartition.

RightBlocks returns the right blocks of the bipartition f.

The right blocks of a bipartition f are just the intersections of the blocks of f with [-n..-1] where n is the degree of f, the values in transverse blocks are positive, and the values in non-transverse blocks are negative.

The right blocks of bipartition are GAP objects in their own right, and are not simply a list of blocks of f; see 5.6 for more information.

The significance of this notion lies in the fact that bipartitions x and y are $$\mathscr{L}$$-related in the partition monoid if and only if they have equal right blocks.

gap> f:=Bipartition( [ [ 1, 4, 7, 8, -4 ], [ 2, 3, 5, -2, -7 ],
> [ 6, -1 ], [ -3 ], [ -5, -6, -8 ] ] );;
gap> RightBlocks(f);
<blocks: [ 1 ], [ 2, 7 ], [ -3 ], [ 4 ], [ -5, -6, -8 ]>
gap> LeftBlocks(f);
<blocks: [ 1, 4, 7, 8 ], [ 2, 3, 5 ], [ 6 ]>

5.5-5 LeftBlocks
 ‣ LeftBlocks( f ) ( attribute )

Returns: The left blocks of a bipartition.

LeftBlocks returns the left blocks of the bipartition f.

The left blocks of a bipartition f are just the intersections of the blocks of f with [1..n] where n is the degree of f, the values in transverse blocks are positive, and the values in non-transverse blocks are negative.

The left blocks of bipartition are GAP objects in their own right, and are not simply a list of blocks of f; see 5.6 for more information.

The significance of this notion lies in the fact that bipartitions x and y are $$\mathscr{R}$$-related in the partition monoid if and only if they have equal left blocks.

gap> f:=Bipartition( [ [ 1, 4, 7, 8, -4 ], [ 2, 3, 5, -2, -7 ],
> [ 6, -1 ], [ -3 ], [ -5, -6, -8 ] ] );;
gap> RightBlocks(f);
<blocks: [ 1 ], [ 2, 7 ], [ -3 ], [ 4 ], [ -5, -6, -8 ]>
gap> LeftBlocks(f);
<blocks: [ 1, 4, 7, 8 ], [ 2, 3, 5 ], [ 6 ]>

5.5-6 NrLeftBlocks
 ‣ NrLeftBlocks( f ) ( attribute )

Returns: A non-negative integer.

When the argument is a bipartition f, NrLeftBlocks returns the number of left blocks of f, i.e. the number of blocks of f intersecting [1..n] non-trivially.

gap> f:=Bipartition( [ [ 1, 2, 3, 4, 5, 6, 8 ], [ 7, -2, -3 ],
> [ -1, -4, -7, -8 ], [ -5, -6 ] ] );;
gap> NrLeftBlocks(f);
2
gap> LeftBlocks(f);
<blocks: [ -1, -2, -3, -4, -5, -6, -8 ], [ 7 ]>

5.5-7 NrRightBlocks
 ‣ NrRightBlocks( f ) ( attribute )

Returns: A non-negative integer.

When the argument is a bipartition f, NrRightBlocks returns the number of right blocks of f, i.e. the number of blocks of f intersecting [-n..-1] non-trivially.

gap> f:=Bipartition( [ [ 1, 2, 3, 4, 6, -2, -7 ], [ 5, -1, -3, -8 ],
> [ 7, -4, -6 ], [ 8 ], [ -5 ] ] );;
gap> RightBlocks(f);
<blocks: [ 1, 3, 8 ], [ 2, 7 ], [ 4, 6 ], [ -5 ]>
gap> NrRightBlocks(f);
4

5.5-8 NrBlocks
 ‣ NrBlocks( blocks ) ( attribute )
 ‣ NrBlocks( f ) ( attribute )

Returns: A positive integer.

If blocks is some blocks or f is a bipartition, then NrBlocks returns the number of blocks in blocks or f, respectively.

gap> blocks:=BlocksNC([[ -1, -2, -3, -4 ], [ -5 ], [ 6 ]]);
<blocks: [ -1, -2, -3, -4 ], [ -5 ], [ 6 ]>
gap> NrBlocks(blocks);
3
gap> f:=Bipartition( [ [ 1, 5 ], [ 2, 4, -2, -4 ], [ 3, 6, -1, -5, -6 ],
> [ -3 ] ] );
<bipartition: [ 1, 5 ], [ 2, 4, -2, -4 ], [ 3, 6, -1, -5, -6 ],
[ -3 ]>
gap> NrBlocks(f);
4

5.5-9 IsTransBipartition
 ‣ IsTransBipartition( f ) ( property )

Returns: true or false.

If the bipartition f defines a transformation, then IsTransBipartition returns true, and if not, then false is returned.

A bipartition f defines a transformation if and only if the number of left blocks equals the number of transverse blocks and the number of right blocks equals the degree.

gap> f:=Bipartition( [ [ 1, 4, -2 ], [ 2, 5, -6 ], [ 3, -7 ], [ 6, 7, -9 ],
> [ 8, 9, -1 ], [ 10, -5 ], [ -3 ], [ -4 ], [ -8 ], [ -10 ] ] );;
gap> IsTransBipartition(f);
true
gap> f:=Bipartition( [ [ 1, 4, -3, -6 ], [ 2, 5, -4, -5 ], [ 3, 6, -1 ],
> [ -2 ] ] );;
gap> IsTransBipartition(f);
false
gap> Number(PartitionMonoid(3), IsTransBipartition);
27

5.5-10 IsDualTransBipartition
 ‣ IsDualTransBipartition( f ) ( property )

Returns: true or false.

If the star of the bipartition f defines a transformation, then IsDualTransBipartition returns true, and if not, then false is returned.

A bipartition is the dual of a transformation if and only if its number of right blocks equals its number of transverse blocks and its number of left blocks equals its degree.

gap> f:=Bipartition( [ [ 1, -8, -9 ], [ 2, -1, -4 ], [ 3 ], [ 4 ],
> [ 5, -10 ], [ 6, -2, -5 ], [ 7, -3 ], [ 8 ], [ 9, -6, -7 ], [ 10 ] ] );;
gap> IsDualTransBipartition(f);
true
gap> f:=Bipartition( [ [ 1, 4, -3, -6 ], [ 2, 5, -4, -5 ], [ 3, 6, -1 ],
> [ -2 ] ] );;
gap> IsTransBipartition(f);
false
gap> Number(PartitionMonoid(3), IsDualTransBipartition);
27

5.5-11 IsPermBipartition
 ‣ IsPermBipartition( f ) ( property )

Returns: true or false.

If the bipartition f defines a permutation, then IsPermBipartition returns true, and if not, then false is returned.

A bipartition is a permutation if its numbers of left, right, and transverse blocks all equal its degree.

gap> f:=Bipartition( [ [ 1, 4, -1 ], [ 2, -3 ], [ 3, 6, -5 ],
> [ 5, -2, -4, -6 ] ] );;
gap> IsPermBipartition(f);
false
gap> f:=Bipartition( [ [ 1, -3 ], [ 2, -4 ], [ 3, -6 ],
> [ 4, -1 ], [ 5, -5 ], [ 6, -2 ], [ 7, -8 ], [ 8, -7 ] ] );;
gap> IsPermBipartition(f);
true

5.5-12 IsPartialPermBipartition
 ‣ IsPartialPermBipartition( f ) ( property )

Returns: true or false.

If the bipartition f defines a partial permutation, then IsPartialPermBipartition returns true, and if not, then false is returned.

A bipartition f defines a partial permutation if and only if the numbers of left and right blocks of f equal the degree of f.

gap> f:=Bipartition( [ [ 1, 4, -1 ], [ 2, -3 ], [ 3, 6, -5 ],
> [ 5, -2, -4, -6 ] ] );;
gap> IsPartialPermBipartition(f);
false
gap> f:=Bipartition( [ [ 1, -3 ], [ 2 ], [ -4 ], [ 3, -6 ], [ 4, -1 ],
> [ 5, -5 ], [ 6, -2 ], [ 7, -8 ], [ 8, -7 ] ] );;
gap> IsPermBipartition(f);
false
gap> IsPartialPermBipartition(f);
true

5.5-13 IsBlockBijection
 ‣ IsBlockBijection( f ) ( property )

Returns: true or false.

If the bipartition f induces a bijection from the quotient of [1..n] by the blocks of f to the quotient of [-n..-1] by the blocks of f, then IsBlockBijection return true, and if not, then it returns false.

A bipartition is a block bijection if and only if its number of blocks, left blocks and right blocks are equal.

gap> f:=Bipartition( [ [ 1, 4, 5, -2 ], [ 2, 3, -1 ],
> [ 6, -5, -6 ], [ -3, -4 ] ] );;
gap> IsBlockBijection(f);
false
gap> f:=Bipartition( [ [ 1, 2, -3 ], [ 3, -1, -2 ], [ 4, -4 ],
> [ 5, -5 ] ] );;
gap> IsBlockBijection(f);
true

5.5-14 IsUniformBlockBijection
 ‣ IsUniformBlockBijection( x ) ( property )

Returns: true or false.

If the bipartition x is a block bijection where every block contains an equal number of positive and negative entries, then IsUniformBlockBijection returns true, and otherwise it returns false.

gap> x:=Bipartition( [ [ 1, 2, -3, -4 ], [ 3, -5 ], [ 4, -6 ],
> [ 5, -7 ], [ 6, -8 ], [ 7, -9 ], [ 8, -1 ], [ 9, -2 ] ] );;
gap> IsBlockBijection(x);
true
gap> x:=Bipartition( [ [ 1, 2, -3 ], [ 3, -1, -2 ], [ 4, -4 ],
> [ 5, -5 ] ] );;
gap> IsUniformBlockBijection(x);
false

5.6 Creating blocks and their attributes

As described above the left and right blocks of a bipartition characterise Green's $$\mathscr{R}$$- and $$\mathscr{L}$$-relation on the partition monoid; see LeftBlocks (5.5-5) and RightBlocks (5.5-4). The left or right blocks of a bipartition are GAP objects in their own right.

In this section, we describe the functions in the Semigroups package for creating and manipulating the left or right blocks of a bipartition.

5.6-1 BlocksNC
 ‣ BlocksNC( classes ) ( function )

Returns: A blocks.

This function makes it possible to create a GAP object corresponding to the left or right blocks of a bipartition without reference to any bipartitions.

BlocksNC returns the blocks with equivalence classes classes, which should be a list of duplicate-free lists consisting solely of positive or negative integers, where the union of the absolute values of the lists is [1..n] for some n. The blocks with positive entries correspond to transverse blocks and the classes with negative entries correspond to non-transverse blocks.

gap> BlocksNC([[ 1 ], [ 2 ], [ -3, -6 ], [ -4, -5 ]]);
<blocks: [ 1 ], [ 2 ], [ -3, -6 ], [ -4, -5 ]>

5.6-2 ExtRepOfBlocks
 ‣ ExtRepOfBlocks( blocks ) ( attribute )

Returns: A list of integers.

If n is the degree of a bipartition with left or right blocks blocks, then ExtRepOfBlocks returns the partition corresponding to blocks as a sorted list of duplicate-free lists.

gap> blocks:=BlocksNC([[ 1, 6 ], [ 2, 3, 7 ], [ 4, 5 ], [ -8 ] ]);;
gap> ExtRepOfBlocks(blocks);
[ [ 1, 6 ], [ 2, 3, 7 ], [ 4, 5 ], [ -8 ] ]

5.6-3 RankOfBlocks
 ‣ RankOfBlocks( blocks ) ( attribute )
 ‣ NrTransverseBlocks( blocks ) ( attribute )

Returns: A non-negative integer.

When the argument blocks is the left or right blocks of a bipartition, RankOfBlocks returns the number of blocks of blocks containing only positive entries, i.e. the number of transverse blocks in blocks.

NrTransverseBlocks is a synonym of RankOfBlocks in this context.

gap> blocks:=BlocksNC([ [ -1, -2, -4, -6 ], [ 3, 10, 12 ], [ 5, 7 ],
> [ 8 ], [ 9 ], [ -11 ] ]);;
gap> RankOfBlocks(blocks);
4

5.6-4 DegreeOfBlocks
 ‣ DegreeOfBlocks( blocks ) ( attribute )

Returns: A non-negative integer.

The degree of blocks is the number of points n where it is defined, i.e. the union of the blocks in blocks will be [1..n] after taking the absolute value of every element.

gap> blocks:=BlocksNC([ [ -1, -11 ], [ 2 ], [ 3, 5, 6, 7 ], [ 4, 8 ],
> [ 9, 10 ], [ 12 ] ]);;
gap> DegreeOfBlocks(blocks);
12

5.7 Actions on blocks

Bipartitions act on left and right blocks in several ways, which are described in this section.

5.7-1 OnRightBlocks
 ‣ OnRightBlocks( blocks, f ) ( function )

Returns: The blocks of a bipartition.

OnRightBlocks returns the right blocks of the product g*f where g is any bipartition whose right blocks are equal to blocks.

gap> f:=Bipartition( [ [ 1, 4, 5, 8 ], [ 2, 3, 7 ], [ 6, -3, -4, -5 ],
>  [ -1, -2, -6 ], [ -7, -8 ] ] );;
gap> g:=Bipartition( [ [ 1, 5 ], [ 2, 4, 8, -2 ], [ 3, 6, 7, -3, -4 ],
>  [ -1, -6, -8 ], [ -5, -7 ] ] );;
gap> RightBlocks(g*f);
<blocks: [ -1, -2, -6 ], [ 3, 4, 5 ], [ -7, -8 ]>
gap> OnRightBlocks(RightBlocks(g), f);
<blocks: [ -1, -2, -6 ], [ 3, 4, 5 ], [ -7, -8 ]>

5.7-2 OnLeftBlocks
 ‣ OnLeftBlocks( blocks, f ) ( function )

Returns: The blocks of a bipartition.

OnLeftBlocks returns the left blocks of the product f*g where g is any bipartition whose left blocks are equal to blocks.

gap> f:=Bipartition( [ [ 1, 5, 7, -1, -3, -4, -6 ], [ 2, 3, 6, 8 ],
> [ 4, -2, -5, -8 ], [ -7 ] ] );;
gap> g:=Bipartition( [ [ 1, 3, -4, -5 ], [ 2, 4, 5, 8 ], [ 6, -1, -3 ],
> [ 7, -2, -6, -7, -8 ] ] );;
gap> LeftBlocks(f*g);
<blocks: [ 1, 4, 5, 7 ], [ -2, -3, -6, -8 ]>
gap> OnLeftBlocks(LeftBlocks(g), f);
<blocks: [ 1, 4, 5, 7 ], [ -2, -3, -6, -8 ]>

5.7-3 PermRightBlocks
 ‣ PermRightBlocks( blocks, f ) ( operation )
 ‣ PermLeftBlocks( blocks, f ) ( operation )

Returns: A permutation.

If f is a bipartition that stabilises blocks, i.e. OnRightBlocks(blocks, f)=blocks, then PermRightBlocks returns the permutation of the indices of the transverse blocks of blocks under the action of f.

PermLeftBlocks is the analogue of PermRightBlocks with respect to OnLeftBlocks (5.7-2).

gap> f:=Bipartition( [ [ 1, 10 ], [ 2, -7, -9 ], [ 3, 4, 6, 8 ], [ 5, -5 ],
> [ 7, 9, -2 ], [ -1, -10 ], [ -3, -4, -6, -8 ] ] );;
gap> blocks:=BlocksNC([[ -1, -10 ], [ 2 ], [ -3, -4, -6, -8 ], [ 5 ],
> [ 7, 9 ]]);;
gap> OnRightBlocks(blocks, f)=blocks;
true
gap> PermRightBlocks(blocks, f);
(2,5)

5.7-4 InverseRightBlocks
 ‣ InverseRightBlocks( blocks, f ) ( function )

Returns: A bipartition.

If OnRightBlocks(blocks, f) has rank equal to the rank of blocks, then InverseRightBlocks returns a bipartition g such that OnRightBlocks(blocks, f*g)=blocks and where PermRightBlocks(blocks, f*g) is the identity permutation.

See PermRightBlocks (5.7-3) and OnRightBlocks (5.7-1).

gap> f:=Bipartition( [ [ 1, 4, 7, 8, -4 ], [ 2, 3, 5, -2, -7 ],
> [ 6, -1 ], [ -3 ], [ -5, -6, -8 ] ] );;
gap> blocks:=BlocksNC([[ -1, -4, -5, -8 ], [ -2, -3, -7 ], [ 6 ]]);;
gap> RankOfBlocks(blocks);
1
gap> RankOfBlocks(OnRightBlocks(blocks, f));
1
gap> g:=InverseRightBlocks(blocks, f);
<bipartition: [ 1, -6 ], [ 2, 3, 4, 5, 6, 7, 8 ], [ -1, -4, -5, -8 ],
[ -2, -3, -7 ]>
gap> blocks;
<blocks: [ -1, -4, -5, -8 ], [ -2, -3, -7 ], [ 6 ]>
gap> OnRightBlocks(blocks, f*g);
<blocks: [ -1, -4, -5, -8 ], [ -2, -3, -7 ], [ 6 ]>
gap> PermRightBlocks(blocks, f*g);
()

5.7-5 InverseLeftBlocks
 ‣ InverseLeftBlocks( blocks, f ) ( function )

Returns: A bipartition.

If OnLeftBlocks(blocks, f) has rank equal to the rank of blocks, then InverseLeftBlocks returns a bipartition g such that OnLeftBlocks(blocks, g*f)=blocks and where PermLeftBlocks(blocks, g*f) is the identity permutation.

See PermLeftBlocks (5.7-3) and OnLeftBlocks (5.7-2).

gap> f:=Bipartition( [ [ 1, 4, 7, 8, -4 ], [ 2, 3, 5, -2, -7 ],
> [ 6, -1 ], [ -3 ], [ -5, -6, -8 ] ] );;
gap> blocks:=BlocksNC([[ -1, -2, -6 ], [ 3, 4, 5 ], [ -7, -8 ]]);;
gap> RankOfBlocks(OnLeftBlocks(blocks, f));
1
gap> g:=InverseLeftBlocks(blocks, f);
<bipartition: [ 1, 2, 6 ], [ 3, 4, 5, -1, -2, -3, -4, -5, -6, -7, -8 ]
, [ 7, 8 ]>
gap> OnLeftBlocks(blocks, g*f);
<blocks: [ -1, -2, -6 ], [ 3, 4, 5 ], [ -7, -8 ]>
gap> PermLeftBlocks(blocks, g*f);
()

5.8 Visualising blocks and bipartitions

There are some functions in Semigroups for creating LaTeX pictures of bipartitions and blocks. Descriptions of these methods can be found in this section.

The functions described in this section return a string, which can be written to a file using the function FileString (GAPDoc: FileString) or viewed using Splash (4.8-1).

5.8-1 TikzBipartition
 ‣ TikzBipartition( f[, opts] ) ( function )

Returns: A string.

This function produces a graphical representation of the bipartition f using the tikz package for LaTeX. More precisely, this function outputs a string containing a minimal LaTeX document which can be compiled using LaTeX to produce a picture of f.

If the optional second argument opts is a record with the component colors set to true, then the blocks of f will be colored using the standard tikz colors. Due to the limited number of colors available in tikz this option only works when the degree of f is less than 20.

gap> f:=Bipartition( [ [ 1, 5 ], [ 2, 4, -3, -5 ], [ 3, -1, -2 ],
> [ -4 ] ] );;
gap> TikzBipartition(f);
"%tikz\n\\documentclass{minimal}\n\\usepackage{tikz}\n\\begin{documen\
t}\n\\begin{tikzpicture}\n\n  %block #1\n  %vertices and labels\n  \\\
fill(1,2)circle(.125);\n  \\draw(0.95, 2.2) node [above] {{ $1$}};\n \
\\fill(5,2)circle(.125);\n  \\draw(4.95, 2.2) node [above] {{ $5$}};\
\n\n  %lines\n  \\draw(1,1.875) .. controls (1,1.1) and (5,1.1) .. (5\
,1.875);\n\n  %block #2\n  %vertices and labels\n  \\fill(2,2)circle(\
.125);\n  \\draw(1.95, 2.2) node [above] {{ $2$}};\n  \\fill(4,2)circ\
le(.125);\n  \\draw(3.95, 2.2) node [above] {{ $4$}};\n  \\fill(3,0)c\
ircle(.125);\n  \\draw(3, -0.2) node [below] {{ $-3$}};\n  \\fill(5,0\
)circle(.125);\n  \\draw(5, -0.2) node [below] {{ $-5$}};\n\n  %lines\
\n  \\draw(2,1.875) .. controls (2,1.3) and (4,1.3) .. (4,1.875);\n  \
\\draw(3,0.125) .. controls (3,0.7) and (5,0.7) .. (5,0.125);\n  \\dr\
aw(2,2)--(3,0);\n\n  %block #3\n  %vertices and labels\n  \\fill(3,2)\
circle(.125);\n  \\draw(2.95, 2.2) node [above] {{ $3$}};\n  \\fill(1\
,0)circle(.125);\n  \\draw(1, -0.2) node [below] {{ $-1$}};\n  \\fill\
(2,0)circle(.125);\n  \\draw(2, -0.2) node [below] {{ $-2$}};\n\n  %l\
ines\n  \\draw(1,0.125) .. controls (1,0.6) and (2,0.6) .. (2,0.125);\
\n  \\draw(3,2)--(2,0);\n\n  %block #4\n  %vertices and labels\n  \\f\
ill(4,0)circle(.125);\n  \\draw(4, -0.2) node [below] {{ $-4$}};\n\n \
%lines\n\\end{tikzpicture}\n\n\\end{document}"

5.8-2 TikzBlocks
 ‣ TikzBlocks( blocks ) ( function )

Returns: A string.

This function produces a graphical representation of the blocks blocks of a bipartition using the tikz package for LaTeX. More precisely, this function outputs a string containing a minimal LaTeX document which can be compiled using LaTeX to produce a picture of blocks.

gap> f:=Bipartition( [ [ 1, 4, -2, -3 ], [ 2, 3, 5, -5 ], [ -1, -4 ] ] );;
gap> TikzBlocks(RightBlocks(f));
"%tikz\n\\documentclass{minimal}\n\\usepackage{tikz}\n\\begin{documen\
t}\n\\begin{tikzpicture}\n  \\draw[ultra thick](5,2)circle(.115);\n  \
\\draw(1.8,5) node [top] {{$1$}};\n  \\fill(4,2)circle(.125);\n  \\dr\
aw(1.8,4) node [top] {{$2$}};\n  \\fill(3,2)circle(.125);\n  \\draw(1\
.8,3) node [top] {{$3$}};\n  \\draw[ultra thick](2,2)circle(.115);\n \
\\draw(1.8,2) node [top] {{$4$}};\n  \\fill(1,2)circle(.125);\n  \\d\
raw(1.8,1) node [top] {{$5$}};\n\n  \\draw (5,2.125) .. controls (5,2\
.8) and (2,2.8) .. (2,2.125);\n  \\draw (4,2.125) .. controls (4,2.6)\
and (3,2.6) .. (3,2.125);\n\\end{tikzpicture}\n\n\\end{document}"

5.9 Semigroups of bipartitions

Semigroups and monoids of bipartitions can be created in the usual way in GAP using the functions Semigroup (Reference: Semigroup) and Monoid (Reference: Monoid).

It is possible to create inverse semigroups and monoids of bipartitions using InverseSemigroup (Reference: InverseSemigroup) and InverseMonoid (Reference: InverseMonoid) when the argument is a collection of block bijections or partial perm bipartions; see IsBlockBijection (5.5-13) and IsPartialPermBipartition (5.5-12).

5.9-1 IsBipartitionSemigroup
 ‣ IsBipartitionSemigroup( S ) ( property )
 ‣ IsBipartitionMonoid( S ) ( property )

Returns: true or false.

A bipartition semigroup is simply a semigroup consisting of bipartitions. An object obj is a bipartition semigroup in GAP if it satisfies IsSemigroup (Reference: IsSemigroup) and IsBipartitionCollection (5.1-2).

A bipartition monoid is a monoid consisting of bipartitions. An object obj is a bipartition monoid in GAP if it satisfies IsMonoid (Reference: IsMonoid) and IsBipartitionCollection (5.1-2).

Note that it is possible for a bipartition semigroup to have a multiplicative neutral element (i.e. an identity element) but not to satisfy IsBipartitionMonoid. For example,

gap> f:=Bipartition( [ [ 1, 4, -2 ], [ 2, 5, -6 ], [ 3, -7 ],
> [ 6, 7, -9 ], [ 8, 9, -1 ], [ 10, -5 ], [ -3 ], [ -4 ],
> [ -8 ], [ -10 ] ] );;
gap> S:=Semigroup(f, One(f));
<commutative bipartition monoid of degree 10 with 1 generator>
gap> IsMonoid(S);
true
gap> IsBipartitionMonoid(S);
true
gap> S:=Semigroup( Bipartition( [ [ 1, -3 ], [ 2, -8 ], [ 3, 8, -1 ],
> [ 4, -4 ], [ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 9, 10, -10 ],
> [ -2 ], [ -9 ] ] ),
> Bipartition( [ [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ],
> [ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, 10, -10 ],
> [ -9 ] ] ) );;
gap> One(S);
fail
gap> MultiplicativeNeutralElement(S);
<bipartition: [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ], [ 5, -5 ],
[ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, 10, -10 ], [ -9 ]>
gap> IsMonoid(S);
false

In this example S cannot be converted into a monoid using AsMonoid (Reference: AsMonoid) since the One (Reference: One) of any element in S differs from the multiplicative neutral element.

For more details see IsMagmaWithOne (Reference: IsMagmaWithOne).

5.9-2 IsBlockBijectionSemigroup
 ‣ IsBlockBijectionSemigroup( S ) ( property )
 ‣ IsBlockBijectionMonoid( S ) ( property )

Returns: true or false.

A block bijection semigroup is simply a semigroup consisting of block bijections. A block bijection monoid is a monoid consisting of block bijections.

An object in GAP is a block bijection monoid if it satisfies IsMonoid (Reference: IsMonoid) and IsBlockBijectionSemigroup.

See IsBlockBijection (5.5-13).

5.9-3 IsPartialPermBipartitionSemigroup
 ‣ IsPartialPermBipartitionSemigroup( S ) ( property )
 ‣ IsPartialPermBipartitionMonoid( S ) ( property )

Returns: true or false.

A partial perm bipartition semigroup is simply a semigroup consisting of partial perm bipartitions. A partial perm bipartition monoid is a monoid consisting of partial perm bipartitions.

An object in GAP is a partial perm bipartition monoid if it satisfies IsMonoid (Reference: IsMonoid) and IsPartialPermBipartitionSemigroup.

See IsPartialPermBipartition (5.5-12).

5.9-4 IsPermBipartitionGroup
 ‣ IsPermBipartitionGroup( S ) ( property )

Returns: true or false.

A perm bipartition group is simply a semigroup consisting of perm bipartitions.

See IsPermBipartition (5.5-11).

5.9-5 DegreeOfBipartitionSemigroup
 ‣ DegreeOfBipartitionSemigroup( S ) ( attribute )

Returns: A non-negative integer.

The degree of a bipartition semigroup S is just the degree of any (and every) element of S.

gap> DegreeOfBipartitionSemigroup(JonesMonoid(8));
8
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 Bib Ind

generated by GAPDoc2HTML