3
Bipartitions and blocks

3.5 Attributes for bipartitons

3.5-1 DegreeOfBipartition

3.5-2 RankOfBipartition

3.5-3 ExtRepOfObj

3.5-4 IntRepOfBipartition

3.5-5 RightBlocks

3.5-6 LeftBlocks

3.5-7 NrLeftBlocks

3.5-8 NrRightBlocks

3.5-9 NrBlocks

3.5-10 DomainOfBipartition

3.5-11 CodomainOfBipartition

3.5-12 IsTransBipartition

3.5-13 IsDualTransBipartition

3.5-14 IsPermBipartition

3.5-15 IsPartialPermBipartition

3.5-16 IsBlockBijection

3.5-17 IsUniformBlockBijection

3.5-18 CanonicalBlocks

3.5-1 DegreeOfBipartition

3.5-2 RankOfBipartition

3.5-3 ExtRepOfObj

3.5-4 IntRepOfBipartition

3.5-5 RightBlocks

3.5-6 LeftBlocks

3.5-7 NrLeftBlocks

3.5-8 NrRightBlocks

3.5-9 NrBlocks

3.5-10 DomainOfBipartition

3.5-11 CodomainOfBipartition

3.5-12 IsTransBipartition

3.5-13 IsDualTransBipartition

3.5-14 IsPermBipartition

3.5-15 IsPartialPermBipartition

3.5-16 IsBlockBijection

3.5-17 IsUniformBlockBijection

3.5-18 CanonicalBlocks

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. A partition of X is the collection of equivalence classes of an equivalence relation on X, and vice versa.

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, j∈mathbfn∪-mathbfn belong to the same block of a bipartition x, then we write (i, j)∈x.

Let x and y be bipartitions of degree n. Their product xy can be described as follows. Define mathbfn'= {1', 2', ..., n'}. From x, create a partition x' of the set mathbfn∪mathbfn' by replacing each negative point -i in a block of x by the point i', and create from y a partition y' of the set mathbfn'∪-mathbfn by replacing each positive point i in a block of y by the point i'. Then define a relation on the set mathbfn∪mathbfn'∪-mathbfn, where i and j are related if they are related in either x' or y', and let p be the transitive closure of this relation. Finally, define xy to be the bipartition of degree n defined by the restriction of the equivalence relation p to the set mathbfn∪-mathbfn.

Equivalently, the product xy is defined to be the bipartition where i,j∈mathbfn∪-mathbfn (we assume without loss of generality that i≥j) belong to the same block of xy if either:

i

`=`

j,i, j ∈ mathbfn and (i,j)∈ x, or

i, j ∈ -mathbfn and (i,j)∈ y;

or there exists r∈N and k(1), k(2),..., k(r)∈ mathbfn , and one of the following holds:

r=2s-1 for some s≥ 1 , i∈mathbfn, j∈ -mathbfn and

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

\qquad\ldots,\ (-k(2s-2),-k(2s-1))\in x,\ (k(2s-1),j)\in y;

r=2s for some s≥ 1 , and either i,j∈mathbfn, and

(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,j∈-mathbfn, and

(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 multiplication can be shown to be associative, and so the collection of all bipartitions of any particular degree is a monoid; the identity element of the partition monoid of degree n is the bipartition {{i,-i}:i∈mathbfn}. A bipartition is a unit if and only if each block is of the form {i,-j} for some i, j∈mathbfn. 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 i∈mathbfn. 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 do not exist distinct blocks A, U ∈ x, along with a, b ∈ A and u, v ∈ U, such that a < u < b < v. Define p to be the bipartition of degree n with blocks {{i, -(i+1)}:i∈{1,...,n-1}} and {n,-1} . Note that p is a unit. A bipartition x of degree n is called *annular* if x = p^i y p^j for some planar bipartition y of degree n, and some integers i and j.

From a graphical perspective, as on Page 873 in [HR05], a bipartition 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. Similarly, as shown in Figure 2 in [Aui12], a bipartition of degree n is annular if it can be represented as a graph without edges crossing inside an annulus.

`‣ IsBipartition` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

Every bipartition in **GAP** belongs to the category `IsBipartition`

. Basic operations for bipartitions are `RightBlocks`

(3.5-5), `LeftBlocks`

(3.5-6), `ExtRepOfObj`

(3.5-3), `LeftProjection`

(3.2-4), `RightProjection`

(3.2-5), `StarOp`

(3.2-6), `DegreeOfBipartition`

(3.5-1), `RankOfBipartition`

(3.5-2), multiplication of two bipartitions of equal degree is via `*`

.

`‣ IsBipartitionCollection` ( obj ) | ( category ) |

`‣ IsBipartitionCollColl` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

Every collection of bipartitions belongs to the category `IsBipartitionCollection`

. For example, bipartition semigroups belong to `IsBipartitionCollection`

.

Every collection of collections of bipartitions belongs to `IsBipartitionCollColl`

. For example, a list of bipartition semigroups belongs to `IsBipartitionCollColl`

.

There are several ways of creating bipartitions in **GAP**, which are described in this section. The maximum degree of a bipartition is set as 2 ^ 29 - 1. In reality, it is unlikely to be possible to create bipartitions of degrees as small as 2 ^ 24 because they require too much memory.

`‣ Bipartition` ( blocks ) | ( function ) |

Returns: A bipartition.

`Bipartition`

returns the bipartition `x`

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> x := Bipartition([[1, -1], [2, 3, -3], [-2]]); <bipartition: [ 1, -1 ], [ 2, 3, -3 ], [ -2 ]>

`‣ 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.

See also `IntRepOfBipartition`

(3.5-4).

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

`‣ 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 ]>

`‣ LeftOne` ( x ) | ( attribute ) |

`‣ LeftProjection` ( x ) | ( attribute ) |

Returns: A bipartition.

The `LeftProjection`

of a bipartition `x` is the bipartition

. It is so-named, since the left and right blocks of the left projection equal the left blocks of `x` * Star(`x`)`x`.

The left projection `e`

of `x` is also a bipartition with the property that `e * `

. `x` = `x``LeftOne`

and `LeftProjection`

are synonymous.

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

`‣ RightOne` ( x ) | ( attribute ) |

`‣ RightProjection` ( x ) | ( attribute ) |

Returns: A bipartition.

The `RightProjection`

of a bipartition `x` is the bipartition `Star(`

. It is so-named, since the left and right blocks of the right projection equal the right blocks of `x`) * `x``x`.

The right projection `e`

of `x` is also a bipartition with the property that

. `x` * e = `x``RightOne`

and `RightProjection`

are synonymous.

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

`‣ StarOp` ( x ) | ( operation ) |

`‣ Star` ( x ) | ( attribute ) |

Returns: A bipartition.

`StarOp`

returns the unique bipartition `g`

with the property that:

, `x` * g * `x` = `x``RightBlocks(`

, and `x`) = LeftBlocks(g)`LeftBlocks(`

. The star `x`) = RightBlocks(g)`g`

can be obtained from `x` by changing the sign of every integer in the external representation of `x`.

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

`‣ RandomBipartition` ( [rs, ]n ) | ( operation ) |

`‣ RandomBlockBijection` ( [rs, ]n ) | ( operation ) |

Returns: A bipartition.

If `n` is a positive integer, then `RandomBipartition`

returns a random bipartition of degree `n`, and `RandomBlockBijection`

returns a random block bijection of degree `n`.

If the optional first argument `rs` is a random source, then this is used to generate the bipartition returned by `RandomBipartition`

and `RandomBlockBijection`

.

Note that neither of these functions has a uniform distribution.

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

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`

(3.3-5), `AsPartialPerm`

(3.3-4), `AsTransformation`

(3.3-3) can be used to convert bipartitions into permutations, partial permutations, or transformations where appropriate.

`‣ AsBipartition` ( x[, n] ) | ( operation ) |

Returns: A bipartition.

`AsBipartition`

returns the bipartition, permutation, transformation, or partial permutation `x`, as a bipartition of degree `n`.

There are several possible arguments for `AsBipartition`

:

**permutations**If

`x`is a permutation and`n`is a positive integer, then`AsBipartition(`

returns the bipartition on`x`,`n`)`[1 ..`

with classes`n`]`[i, i ^`

for all`x`]`i = 1 .. n`

.If no positive integer

`n`is specified, then the largest moved point of`x`is used as the value for`n`; see`LargestMovedPoint`

(Reference: LargestMovedPoint for a permutation).**transformations**If

`x`is a transformation and`n`is a positive integer such that`x`is a transformation of`[1 ..`

, then`n`]`AsTransformation`

returns the bipartition with classes (i)f ^ -1∪ {i} for all`i`

in the image of`x`.If the positive integer

`n`is not specified, then the degree of`x`is used as the value for`n`.**partial permutations**If

`x`is a partial permutation and`n`is a positive integer, then`AsBipartition`

returns the bipartition with classes`[i, i ^`

for`x`]`i`

in`[1 ..`

. Thus the degree of the returned bipartition is the maximum of`n`]`n`and the values`i ^`

where`x``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`x`plus`1`

is used.**bipartitions**If

`x`is a bipartition and`n`is a non-negative integer, then`AsBipartition`

returns a bipartition corresponding to`x`with degree`n`.If

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

and`-i`

for all`i`

greater than the degree of`x`**pbrs**If

`x`is a pbr satisfying`IsBipartitionPBR`

(4.5-8) and`n`is a non-negative integer, then`AsBipartition`

returns the bipartition corresponding to`x`with degree`n`.

gap> x := Transformation([3, 5, 3, 4, 1, 2]);; gap> AsBipartition(x, 5); <bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ], [ -2 ]> gap> AsBipartition(x); <bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ], [ 6, -2 ], [ -6 ]> gap> AsBipartition(x, 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> x := PartialPerm([1, 2, 3, 4, 5, 6], [6, 7, 1, 4, 3, 2]);; gap> AsBipartition(x, 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(x); <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> x := Bipartition([[1, 2, -2], [3], [4, 5, 6, -1], > [-3, -4, -5, -6]]);; gap> AsBipartition(x, 0); <empty bipartition> gap> AsBipartition(x, 2); <bipartition: [ 1, 2, -2 ], [ -1 ]> gap> AsBipartition(x, 8); <bipartition: [ 1, 2, -2 ], [ 3 ], [ 4, 5, 6, -1 ], [ 7 ], [ 8 ], [ -3, -4, -5, -6 ], [ -7 ], [ -8 ]> gap> x := PBR( > [[-1, 1, 2, 3, 4], [-1, 1, 2, 3, 4], > [-1, 1, 2, 3, 4], [-1, 1, 2, 3, 4]], > [[-1, 1, 2, 3, 4], [-2], [-3], [-4]]);; gap> AsBipartition(x); <bipartition: [ 1, 2, 3, 4, -1 ], [ -2 ], [ -3 ], [ -4 ]> gap> AsBipartition(x, 2); <bipartition: [ 1, 2, -1 ], [ -2 ]> gap> AsBipartition(x, 4); <bipartition: [ 1, 2, 3, 4, -1 ], [ -2 ], [ -3 ], [ -4 ]> gap> AsBipartition(x, 5); <bipartition: [ 1, 2, 3, 4, -1 ], [ 5 ], [ -2 ], [ -3 ], [ -4 ], [ -5 ]> gap> AsBipartition(x, 0); <empty bipartition>

`‣ AsBlockBijection` ( x[, n] ) | ( operation ) |

Returns: A block bijection.

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

and one additional class which is the union the singleton classes of `x`, `n`)`g`

.

If the optional second argument `n` is not present, then the maximum of the degree and codegree of `x` plus 1 is used by default. If the second argument `n` is not greater than this maximum, then an error is given.

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

When the argument `x` is a partial perm bipartition (see `IsPartialPermBipartition`

(3.5-15)) then this operation returns `AsBlockBijection(AsPartialPerm(`

.`x`)[, `n`])

gap> x := PartialPerm([1, 2, 3, 6, 7, 10], [9, 5, 6, 1, 7, 8]); [2,5][3,6,1,9][10,8](7) gap> AsBipartition(x, 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(x, 10); Error, Semigroups: AsBlockBijection (for a partial perm and pos int): the 2nd argument must be strictly greater than the maximum of the degree and codegree of the 1st argument, gap> AsBlockBijection(x, 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 ]> gap> x := Bipartition([[1, -3], [2], [3, -2], [-1]]);; gap> IsPartialPermBipartition(x); true gap> AsBlockBijection(x); <block bijection: [ 1, -3 ], [ 2, 4, -1, -4 ], [ 3, -2 ]>

`‣ AsTransformation` ( x ) | ( attribute ) |

Returns: A transformation.

When the argument `x` is a bipartition, that mathematically defines a transformation, this function returns that transformation. A bipartition `x` 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 `x`.

See `IsTransBipartition`

(3.5-12).

gap> x := 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(x); Transformation( [ 3, 2, 7, 12, 7, 6, 6, 5, 11, 7, 10, 10 ] ) gap> IsTransBipartition(x); true gap> x := Bipartition([[1, 5], [2, 4, 8, 10], > [3, 6, 7, -1, -2], [9, -4, -6, -9], > [-3, -5], [-7, -8], [-10]]);; gap> AsTransformation(x); Error, Semigroups: AsTransformation (for a bipartition): the argument does not define a transformation,

`‣ AsPartialPerm` ( x ) | ( operation ) |

Returns: A partial perm.

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

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

See `IsPartialPermBipartition`

(3.5-15).

gap> x := Bipartition([[1, -4], [2, -2], [3, -10], [4, -5], > [5, -9], [6], [7], [8, -6], [9, -3], [10, -8], > [-1], [-7]]);; gap> IsPartialPermBipartition(x); true gap> AsPartialPerm(x); [1,4,5,9,3,10,8,6](2) gap> x := Bipartition([[1, -2, -4], [2, 3, 4, -3], [-1]]);; gap> IsPartialPermBipartition(x); false gap> AsPartialPerm(x); Error, Semigroups: AsPartialPerm (for a bipartition): the argument does not define a partial perm,

`‣ AsPermutation` ( x ) | ( attribute ) |

Returns: A permutation.

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

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

See `IsPermBipartition`

(3.5-14).

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

`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.

`‣ PartialPermLeqBipartition` ( x, y ) | ( operation ) |

Returns: `true`

or `false`

.

If `x` and `y` are partial perm bipartitions, i.e. they satisfy `IsPartialPermBipartition`

(3.5-15), then this function returns `AsPartialPerm(`

.`x`) < AsPartialPerm(`y`)

`‣ NaturalLeqPartialPermBipartition` ( x, y ) | ( operation ) |

Returns: `true`

or `false`

.

The *natural partial order* ≤ on an inverse semigroup `S`

is defined by `s`

≤ `t`

if there exists an idempotent `e`

in `S`

such that `s = et`

. Hence if `x` and `y` are partial perm bipartitions, then `x` ≤ `y` if and only if `AsPartialPerm(`

is a restriction of `x`)`AsPartialPerm(`

.`y`)

`NaturalLeqPartialPermBipartition`

returns `true`

if `AsPartialPerm(`

is a restriction of `x`)`AsPartialPerm(`

and `y`)`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.

`‣ NaturalLeqBlockBijection` ( x, y ) | ( operation ) |

Returns: `true`

or `false`

.

The *natural partial order* ≤ on an inverse semigroup `S`

is defined by `s`

≤ `t`

if there exists an idempotent `e`

in `S`

such that `s = et`

. Hence if `x` and `y` are block bijections, then `x` ≤ `y` 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

`‣ PermLeftQuoBipartition` ( x, y ) | ( operation ) |

Returns: A permutation.

If `x` and `y` are bipartitions with equal left and right blocks, then `PermLeftQuoBipartition`

returns the permutation of the indices of the right blocks of `x` (and `y`) induced by `Star(`

.`x`) * `y`

`PermLeftQuoBipartition`

verifies that `x` and `y` have equal left and right blocks, and returns an error if they do not.

gap> x := Bipartition([[1, 4, 6, 7, 8, 10], [2, 5, -1, -2, -8], > [3, -3, -6, -7, -9], [9, -4, -5], [-10]]);; gap> y := Bipartition([[1, 4, 6, 7, 8, 10], [2, 5, -3, -6, -7, -9], > [3, -4, -5], [9, -1, -2, -8], [-10]]);; gap> PermLeftQuoBipartition(x, y); (1,2,3) gap> Star(x) * y; <bipartition: [ 1, 2, 8, -3, -6, -7, -9 ], [ 3, 6, 7, 9, -4, -5 ], [ 4, 5, -1, -2, -8 ], [ 10 ], [ -10 ]>

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

`‣ DegreeOfBipartition` ( x ) | ( attribute ) |

`‣ DegreeOfBipartitionCollection` ( x ) | ( attribute ) |

Returns: A positive integer.

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

points, then the degree of `x` 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> x := Bipartition([[1, 7, -3, -8], [2, 6], > [3], [4, -7, -9], [5, 9, -2], > [8, -1, -4, -6], [-5]]);; gap> DegreeOfBipartition(x); 9 gap> S := BrauerMonoid(5); <regular bipartition *-monoid of degree 5 with 3 generators> gap> IsBipartitionCollection(S); true gap> DegreeOfBipartitionCollection(S); 5

`‣ RankOfBipartition` ( x ) | ( attribute ) |

`‣ NrTransverseBlocks` ( x ) | ( attribute ) |

Returns: The rank of a bipartition.

When the argument is a bipartition `x`, `RankOfBipartition`

returns the number of blocks of `x` containing both positive and negative entries, i.e. the number of transverse blocks of `x`.

`NrTransverseBlocks`

is just a synonym for `RankOfBipartition`

.

gap> x := 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(x); 4

`‣ ExtRepOfObj` ( x ) | ( operation ) |

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

.

If `n`

is the degree of the bipartition `x`, then `ExtRepOfObj`

returns the partition of `[-n .. -1]`

union `[1 .. n]`

corresponding to `x` as a sorted list of duplicate-free lists.

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

`‣ IntRepOfBipartition` ( x ) | ( attribute ) |

Returns: A list of positive integers.

If `x` is a bipartition with degree `n`

, then `IntRepOfBipartition`

returns the *internal representation* of `x`: a list of length `2 * n`

containing positive integers which correspond to the blocks of `x`.

If `i`

is in `[1 .. n]`

, then `list[i]`

refers to the point `i`

; if `i`

is in `[n + 1 .. 2 * n]`

, then `list[i]`

refers to the point `n - i`

(a negative point). Two points lie in the same block of the bipartition if and only if their entries in the list are equal.

See also `BipartitionByIntRep`

(3.2-2).

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

`‣ RightBlocks` ( x ) | ( attribute ) |

Returns: The right blocks of a bipartition.

`RightBlocks`

returns the right blocks of the bipartition `x`.

The *right blocks* of a bipartition `x` are just the intersections of the blocks of `x` with `[-n .. -1]`

where `n`

is the degree of `x`, the values in transverse blocks are positive, and the values in non-transverse blocks are negative.

The right blocks of a bipartition are **GAP** objects in their own right, and are not simply a list of blocks of `x`; see 3.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> x := Bipartition([[1, 4, 7, 8, -4], [2, 3, 5, -2, -7], > [6, -1], [-3], [-5, -6, -8]]);; gap> RightBlocks(x); <blocks: [ 1* ], [ 2*, 7* ], [ 3 ], [ 4* ], [ 5, 6, 8 ]> gap> LeftBlocks(x); <blocks: [ 1*, 4*, 7*, 8* ], [ 2*, 3*, 5* ], [ 6* ]>

`‣ LeftBlocks` ( x ) | ( attribute ) |

Returns: The left blocks of a bipartition.

`LeftBlocks`

returns the left blocks of the bipartition `x`.

The *left blocks* of a bipartition `x` are just the intersections of the blocks of `x` with `[1..n]`

where `n`

is the degree of `x`, the values in transverse blocks are positive, and the values in non-transverse blocks are negative.

The left blocks of a bipartition are **GAP** objects in their own right, and are not simply a list of blocks of `x`; see 3.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> x := Bipartition([[1, 4, 7, 8, -4], [2, 3, 5, -2, -7], > [6, -1], [-3], [-5, -6, -8]]);; gap> RightBlocks(x); <blocks: [ 1* ], [ 2*, 7* ], [ 3 ], [ 4* ], [ 5, 6, 8 ]> gap> LeftBlocks(x); <blocks: [ 1*, 4*, 7*, 8* ], [ 2*, 3*, 5* ], [ 6* ]>

`‣ NrLeftBlocks` ( x ) | ( attribute ) |

Returns: A non-negative integer.

When the argument is a bipartition `x`, `NrLeftBlocks`

returns the number of left blocks of `x`, i.e. the number of blocks of `x` intersecting `[1 .. n]`

non-trivially.

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

`‣ NrRightBlocks` ( x ) | ( attribute ) |

Returns: A non-negative integer.

When the argument is a bipartition `x`, `NrRightBlocks`

returns the number of right blocks of `x`, i.e. the number of blocks of `x` intersecting `[-n .. -1]`

non-trivially.

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

`‣ 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> x := 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(x); 4

`‣ DomainOfBipartition` ( x ) | ( attribute ) |

Returns: A list of positive integers.

If `x` is a bipartition, then `DomainOfBipartition`

returns the domain of `x`. The *domain* of `x` consists of those numbers `i`

in `[1 .. n]`

such that `i`

is contained in a transverse block of `x`, where `n`

is the degree of `x` (see `DegreeOfBipartition`

(3.5-1)).

gap> x := Bipartition([[1, 2], [3, 4, 5, -5], [6, -6], > [-1, -2, -3], [-4]]); <bipartition: [ 1, 2 ], [ 3, 4, 5, -5 ], [ 6, -6 ], [ -1, -2, -3 ], [ -4 ]> gap> DomainOfBipartition(x); [ 3, 4, 5, 6 ]

`‣ CodomainOfBipartition` ( x ) | ( attribute ) |

Returns: A list of positive integers.

If `x` is a bipartition, then `CodomainOfBipartition`

returns the codomain of `x`. The *codomain* of `x` consists of those numbers `i`

in `[-n .. -1]`

such that `i`

is contained in a transverse block of `x`, where `n`

is the degree of `x` (see `DegreeOfBipartition`

(3.5-1)).

gap> x := Bipartition([[1, 2], [3, 4, 5, -5], [6, -6], > [-1, -2, -3], [-4]]); <bipartition: [ 1, 2 ], [ 3, 4, 5, -5 ], [ 6, -6 ], [ -1, -2, -3 ], [ -4 ]> gap> CodomainOfBipartition(x); [ -5, -6 ]

`‣ IsTransBipartition` ( x ) | ( property ) |

Returns: `true`

or `false`

.

If the bipartition `x` defines a transformation, then `IsTransBipartition`

returns `true`

, and if not, then `false`

is returned.

A bipartition `x` 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> x := Bipartition([[1, 4, -2], [2, 5, -6], [3, -7], > [6, 7, -9], [8, 9, -1], [10, -5], > [-3], [-4], [-8], [-10]]);; gap> IsTransBipartition(x); true gap> x := Bipartition([[1, 4, -3, -6], [2, 5, -4, -5], > [3, 6, -1], [-2]]);; gap> IsTransBipartition(x); false gap> Number(PartitionMonoid(3), IsTransBipartition); 27

`‣ IsDualTransBipartition` ( x ) | ( property ) |

Returns: `true`

or `false`

.

If the star of the bipartition `x` 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> x := Bipartition([[1, -8, -9], [2, -1, -4], [3], > [4], [5, -10], [6, -2, -5], [7, -3], > [8], [9, -6, -7], [10]]);; gap> IsDualTransBipartition(x); true gap> x := Bipartition([[1, 4, -3, -6], [2, 5, -4, -5], > [3, 6, -1], [-2]]);; gap> IsTransBipartition(x); false gap> Number(PartitionMonoid(3), IsDualTransBipartition); 27

`‣ IsPermBipartition` ( x ) | ( property ) |

Returns: `true`

or `false`

.

If the bipartition `x` 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> x := Bipartition([ > [1, 4, -1], [2, -3], [3, 6, -5], [5, -2, -4, -6]]);; gap> IsPermBipartition(x); false gap> x := Bipartition([[1, -3], [2, -4], [3, -6], [4, -1], > [5, -5], [6, -2], [7, -8], [8, -7]]);; gap> IsPermBipartition(x); true

`‣ IsPartialPermBipartition` ( x ) | ( property ) |

Returns: `true`

or `false`

.

If the bipartition `x` defines a partial permutation, then `IsPartialPermBipartition`

returns `true`

, and if not, then `false`

is returned.

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

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

`‣ IsBlockBijection` ( x ) | ( property ) |

Returns: `true`

or `false`

.

If the bipartition `x` 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> x := Bipartition([[1, 4, 5, -2], [2, 3, -1], [6, -5, -6], > [-3, -4]]);; gap> IsBlockBijection(x); false gap> x := Bipartition([[1, 2, -3], [3, -1, -2], [4, -4], [5, -5]]);; gap> IsBlockBijection(x); true

`‣ 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

`‣ CanonicalBlocks` ( blocks ) | ( attribute ) |

Returns: Blocks of a bipartition.

If `blocks` is the blocks of a bipartition, then the function `CanonicalBlocks`

returns a canonical representative of `blocks`.

In particular, let `C(n)`

be a largest class such that any element of `C(n)`

is blocks of a bipartition of degree `n`

and such that for every pair of elements `x`

and `y`

of `C(n)`

the number of signed, and similarly unsigned, blocks of any given size in both `x`

and `y`

are the same. Then `CanonicalBlocks`

returns a canonical representative of a class `C(n)`

containing `blocks` where `n`

is the degree of `blocks`.

gap> B := BlocksNC([[-1, -3], [2, 4, 7], [5, 6]]); <blocks: [ 1, 3 ], [ 2*, 4*, 7* ], [ 5*, 6* ]> gap> CanonicalBlocks(B); <blocks: [ 1*, 2*, 3* ], [ 4, 5 ], [ 6*, 7* ]>

As described above the left and right blocks of a bipartition characterise Green's \(\mathscr{R}\)- and \(\mathscr{L}\)-relation of the partition monoid; see `LeftBlocks`

(3.5-6) and `RightBlocks`

(3.5-5). 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.

`‣ IsBlocks` ( obj ) | ( category ) |

Returns: `true`

or `false`

.

Every blocks object in **GAP** belongs to the category `IsBlocks`

. Basic operations for blocks are `ExtRepOfObj`

(3.6-3), `RankOfBlocks`

(3.6-4), `DegreeOfBlocks`

(3.6-5), `OnRightBlocks`

(3.7-1), and `OnLeftBlocks`

(3.7-2).

`‣ 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.

This method function does not check that its arguments are valid, and should be used with caution.

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

`‣ ExtRepOfObj` ( blocks ) | ( operation ) |

Returns: A list of integers.

If `n`

is the degree of a bipartition with left or right blocks `blocks`, then `ExtRepOfObj`

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> ExtRepOfObj(blocks); [ [ 1, 6 ], [ 2, 3, 7 ], [ 4, 5 ], [ -8 ] ]

`‣ 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

`‣ 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

`‣ ProjectionFromBlocks` ( blocks ) | ( attribute ) |

Returns: A bipartition.

When the argument `blocks` is the left or right blocks of a bipartition, this operation returns the unique bipartition whose left and right blocks are equal to `blocks`.

If `blocks` is the left blocks of a bipartition `x`

, then this operation returns a bipartition equal to the left projection of `x`

. The analogous statement holds when `blocks` is the right blocks of a bipartition.

gap> x := Bipartition([[1], [2, -2, -3], [3], [-1]]); <bipartition: [ 1 ], [ 2, -2, -3 ], [ 3 ], [ -1 ]> gap> ProjectionFromBlocks(LeftBlocks(x)); <bipartition: [ 1 ], [ 2, -2 ], [ 3 ], [ -1 ], [ -3 ]> gap> LeftProjection(x); <bipartition: [ 1 ], [ 2, -2 ], [ 3 ], [ -1 ], [ -3 ]> gap> ProjectionFromBlocks(RightBlocks(x)); <bipartition: [ 1 ], [ 2, 3, -2, -3 ], [ -1 ]> gap> RightProjection(x); <bipartition: [ 1 ], [ 2, 3, -2, -3 ], [ -1 ]>

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

`‣ OnRightBlocks` ( blocks, x ) | ( operation ) |

Returns: The blocks of a bipartition.

`OnRightBlocks`

returns the right blocks of the product `g * `

where `x``g`

is any bipartition whose right blocks are equal to `blocks`.

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

`‣ OnLeftBlocks` ( blocks, x ) | ( operation ) |

Returns: The blocks of a bipartition.

`OnLeftBlocks`

returns the left blocks of the product

where `x` * y`y`

is any bipartition whose left blocks are equal to `blocks`.

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

Semigroups and monoids of bipartitions can be created in the usual way in **GAP** using the functions `Semigroup`

(Reference: Semigroup) and `Monoid`

(Reference: Monoid); see Chapter 6 for more details.

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`

(3.5-16) and `IsPartialPermBipartition`

(3.5-15). Note that every bipartition semigroup in **Semigroups** is finite.

`‣ IsBipartitionSemigroup` ( S ) | ( filter ) |

`‣ IsBipartitionMonoid` ( S ) | ( filter ) |

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`

(3.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`

(3.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> x := Bipartition([ > [1, 4, -2], [2, 5, -6], [3, -7], [6, 7, -9], [8, 9, -1], > [10, -5], [-3], [-4], [-8], [-10]]);; gap> S := Semigroup(x, One(x)); <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).

`‣ IsBlockBijectionSemigroup` ( S ) | ( property ) |

`‣ IsBlockBijectionMonoid` ( S ) | ( filter ) |

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`

(3.5-16).

`‣ IsPartialPermBipartitionSemigroup` ( S ) | ( property ) |

`‣ IsPartialPermBipartitionMonoid` ( S ) | ( filter ) |

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`

(3.5-15).

`‣ IsPermBipartitionGroup` ( S ) | ( property ) |

Returns: `true`

or `false`

.

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

See `IsPermBipartition`

(3.5-14).

`‣ 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

generated by GAPDoc2HTML