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 x y 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 x y to be the bipartition of degree n defined by the restriction of the equivalence relation p to the set mathbfn ∪-mathbfn .
Equivalently, the product x y 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 x y 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 x * Star(x). It is so-named, since the left and right blocks of the left projection equal the left blocks of 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(x) * x. It is so-named, since the left and right blocks of the right projection equal the right blocks of 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(x) = LeftBlocks(g), and LeftBlocks(x) = RightBlocks(g). The star 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:
If x is a permutation and n is a positive integer, then AsBipartition(x, n) returns the bipartition on [1 .. n] with classes [i, i ^ x] for all 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).
If x is a transformation and n is a positive integer such that x is a transformation of [1 .. n], then 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.
If x is a partial permutation and n is a positive integer, then AsBipartition returns the bipartition with classes [i, i ^ x] for i in [1 .. n]. Thus the degree of the returned bipartition is the maximum of n and the values i ^ x 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 x plus 1 is used.
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
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(x, 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 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, the 2nd argument (a pos. int.) is less than or equal to the max\ imum of the degree and codegree of the 1st argument (a partial perm) 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, the argument (a bipartition) 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, the argument (a bipartition) 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 * greturns the composition of f and g when f and g are bipartitions.
f < greturns true if the internal representation of f is lexicographically less than the internal representation of g and false if it is not.
f = greturns 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(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.
‣ 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 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 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 := BLOCKS_NC([[-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 := BLOCKS_NC([[-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 R- and 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).
‣ BLOCKS_NC( 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.
BLOCKS_NC 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> BLOCKS_NC([[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 := BLOCKS_NC([[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 := BLOCKS_NC([[-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 := BLOCKS_NC([[-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 * x where 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 x * y where 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