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\in\)\(\mathbb{N}\), let \(\mathbf{n}\)\( = \{1, 2, \ldots, n\}\), and let \(-\)\(\mathbf{n}\)\( = \{-1, -2, \ldots, -n\}\).

The *partition monoid* of degree \(n\) is the set of all partitions of \(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\) 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 \(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\) whose union is \(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\); these subsets are called the *blocks* of \(x\). A block containing elements of both \(\mathbf{n}\) and -\(\mathbf{n}\) is called a *transverse block*. If \(i\), \(j\)\(\in\)\(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\) belong to the same block of a bipartition \(x\), then we write (\(i\), \(j\))\(\in\)\(x\).

Let \(x\) and \(y\) be bipartitions of degree \(n\). Their product \(x\)\(y\) can be described as follows. Define \(\mathbf{n}\)'\( = \{1', 2', \ldots, n'\}\). From \(x\), create a partition \(x\)' of the set \(\mathbf{n}\)\(\cup\)\(\mathbf{n}\)' 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 \(\mathbf{n}\)'\(\cup\)-\(\mathbf{n}\) by replacing each positive point \(i\) in a block of \(y\) by the point \(i\)'. Then define a relation on the set \(\mathbf{n}\)\(\cup\)\(\mathbf{n}\)'\(\cup\)-\(\mathbf{n}\), 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 \(x\)\(y\) to be the bipartition of degree \(n\) defined by the restriction of the equivalence relation \(p\) to the set \(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\).

Equivalently, the product \(x\)\(y\) is defined to be the bipartition where \(i\),\(j\)\(\in\)\(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\) (we assume without loss of generality that \(i\)\(\geq\)\(j\)) belong to the same block of \(x\)\(y\) if either:

\(i\)

`=`

\(j\),\(i\), \(j\) \(\in\) \(\mathbf{n}\) and \((\)\(i\),\(j\)\()\)\(\in\) \(x\), or

\(i\), \(j\) \(\in\) -\(\mathbf{n}\) and \((\)\(i\),\(j\)\()\)\(\in\) \(y\);

or there exists \(r\in\)\(\mathbb{N}\) and \(k(1), k(2),\ldots, k(r)\in \mathbf{n}\) , and one of the following holds:

\(r=2s-1\) for some \(s\geq 1\) , \(i\)\(\in\)\(\mathbf{n}\), \(j\)\(\in\) -\(\mathbf{n}\) 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\geq 1\) , and either \(i\),\(j\)\(\in\)\(\mathbf{n}\), 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\)\(\in\)-\(\mathbf{n}\), 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 \(\left\{\{i,-i\}:i\in\mathbf{n}\right\}\). A bipartition is a unit if and only if each block is of the form \(\{\)\(i\),-\(j\)\(\}\) for some \(i\), \(j\)\(\in\)\(\mathbf{n}\). Hence the group of units is isomorphic to the symmetric group on \(\mathbf{n}\).

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\)\(\in\)\(\mathbf{n}\). 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 \in\) \(x\), along with \(a, b \in A\) and \(u, v \in U\), such that \(a < u < b < v\). Define \(p\) to be the bipartition of degree \(n\) with blocks \(\left\{\{i, -(i+1)\}:i\in\{1,\ldots,n-1\right\}\}\) 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 \(\mathbf{n}\)\(\cup\)-\(\mathbf{n}\). 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}\cup \{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* \(\leq\) on an inverse semigroup `S`

is defined by `s`

\(\leq\) `t`

if there exists an idempotent `e`

in `S`

such that `s = et`

. Hence if `x` and `y` are partial perm bipartitions, then `x` \(\leq\) `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* \(\leq\) on an inverse semigroup `S`

is defined by `s`

\(\leq\) `t`

if there exists an idempotent `e`

in `S`

such that `s = et`

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