Quellcode-Bibliothek chap3.html
Sprache: HTML
|
|
| products/sources/formale Sprachen/GAP/pkg/semigroups/doc/chap3.html |
 |
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (Semigroups) - Chapter 3:
Bipartitions and blocks
</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap3" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chap13.html">13</a> <a href="chap14.html">14</a> <a href="chap15.html">15</a> <a href="chap16.html">16</a> <a href="chap17.html">17</a> <a href="chap18.html">18</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap2.html">[Previous Chapter]</a> <a href="chap4.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap3_mj.html">[MathJax on]</a></p>
<p><a id="X7C18DB427C9C0917" name="X7C18DB427C9C0917"></a></p>
<div class="ChapSects"><a href="chap3.html#X7C18DB427C9C0917">3 <span class="Heading">
Bipartitions and blocks
</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7850845886902FBF">3.1 <span class="Heading">The family and categories of bipartitions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X80F11BEF856E7902">3.1-1 IsBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X82F5D10C85489832">3.1-2 IsBipartitionCollection</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X85D77073820C7E72">3.2 <span class="Heading">Creating bipartitions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7E052E6378A5B758">3.2-1 Bipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X846AA7568435D2CE">3.2-2 BipartitionByIntRep</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8379B0538101FBC8">3.2-3 IdentityBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X824EDD4582AAA8C7">3.2-4 LeftOne</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X790B71108070FAC2">3.2-5 RightOne</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7CE00E0C79F62745">3.2-6 StarOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8077265981409CCB">3.2-7 RandomBipartition</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7C2C44D281A0D2C9">3.3 <span class="Heading">Changing the representation of a bipartition</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X855126D98583C181">3.3-1 AsBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X85A5AD2B7F3B776F">3.3-2 AsBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7CE91D0C83865214">3.3-3 AsTransformation</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C5212EF7A200E63">3.3-4 AsPartialPerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C684CD38405DBEF">3.3-5 AsPermutation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X83F2C3C97E8FFA49">3.4 <span class="Heading">Operators for bipartitions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7A39D36086647536">3.4-1 PartialPermLeqBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8608D78F83D55108">3.4-2 NaturalLeqPartialPermBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X79E8FA077E24C1F4">3.4-3 NaturalLeqBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D9F5A248028FF52">3.4-4 PermLeftQuoBipartition</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X87F3A304814797CE">3.5 <span class="Heading">Attributes for bipartitons</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X780F5E00784FE58C">3.5-1 DegreeOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X82074756826AD2C2">3.5-2 RankOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X86F6506C780C6E08">3.5-3 ExtRepOfObj</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7ECD393A854C073B">3.5-4 IntRepOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X86A10B138230C2A4">3.5-5 RightBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B9B364379D8F4E8">3.5-6 LeftBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X79AEDB5382FD25CF">3.5-7 NrLeftBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X86385A3C8662E1A7">3.5-8 NrRightBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8110B6557A98FB5C">3.5-9 NrBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8657EE2B79E1DD02">3.5-10 DomainOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X84569A187A211332">3.5-11 CodomainOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X79C556827A578509">3.5-12 IsTransBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F0B8ACC7C9A937F">3.5-13 IsDualTransBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8031B53E7D0ECCFA">3.5-14 IsPermBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X87C771D37B1FE95C">3.5-15 IsPartialPermBipartition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X829494DF7FD6CFEC">3.5-16 IsBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X79D54AD8833B9551">3.5-17 IsUniformBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B87B9B081FF88BB">3.5-18 CanonicalBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X87684C148592F831">3.6 <span class="Heading">Creating blocks and their attributes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D77092078EC860C">3.6-1 IsBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81302B217DCAAE6F">3.6-2 BLOCKS_NC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D2CB12279623CE2">3.6-3 ExtRepOfObj</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X787D22AE7FA69239">3.6-4 RankOfBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8527DC6A8771C2BE">3.6-5 DegreeOfBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X815D99A983B2355F">3.6-6 ProjectionFromBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X7A45E0067F344683">3.7 <span class="Heading">Actions on blocks</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7B701DA37F75E77B">3.7-1 OnRightBlocks</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7A5A4AF57BEA2313">3.7-2 OnLeftBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X876C963F830719E2">3.8 <span class="Heading">
Semigroups of bipartitions
</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X810BFF647C4E191E">3.8-1 IsBipartitionSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X80C37124794636F3">3.8-2 IsBlockBijectionSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X79A706A582ABE558">3.8-3 IsPartialPermBipartitionSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7DEE07577D7379AC">3.8-4 IsPermBipartitionGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8162E2BB7CF144F5">3.8-5 DegreeOfBipartitionSemigroup</a></span>
</div></div>
</div>
<h3>3 <span class="Heading">
Bipartitions and blocks
</span></h3>
<p>In this chapter we describe the functions in <strong class="pkg">Semigroups</strong> for creating and manipulating bipartitions and semigroups of bipartitions. We begin by describing what these objects are.</p>
<p>A <em>partition</em> of a set <span class="SimpleMath">X</span> is a set of pairwise disjoint non-empty subsets of <span class="SimpleMath">X</span> whose union is <span class="SimpleMath">X</span> . A partition of <span class="SimpleMath">X</span> is the collection of equivalence classes of an equivalence relation on <span class="SimpleMath">X</span> , and vice versa.</p>
<p>Let <span class="SimpleMath">n∈</span><span class="SimpleMath">N</span> , let <span class="SimpleMath">mathbfn</span> <span class="SimpleMath">= {1, 2, ..., n}</span>, and let <span class="SimpleMath">-</span><span class="SimpleMath">mathbfn</span> <span class="SimpleMath">= {-1, -2, ..., -n}</span>.</p>
<p>The <em>partition monoid</em> of degree <span class="SimpleMath">n</span> is the set of all partitions of <span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span>-<span class="SimpleMath">mathbfn</span> with a multiplication we describe below. To avoid conflict with other uses of the word "partition" in <strong class="pkg">GAP</strong>, and to reflect their definition, we have opted to refer to the elements of the partition monoid as <em>bipartitions</em> of degree <span class="SimpleMath">n</span> ; we will do so from this point on.</p>
<p>Let <span class="SimpleMath">x</span> be any bipartition of degree <span class="SimpleMath">n</span> . Then <span class="SimpleMath">x</span> is a set of pairwise disjoint non-empty subsets of <span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span>-<span class="SimpleMath">mathbfn</span> whose union is <span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span>-<span class="SimpleMath">mathbfn</span> ; these subsets are called the <em>blocks</em> of <span class="SimpleMath">x</span> . A block containing elements of both <span class="SimpleMath">mathbfn</span> and -<span class="SimpleMath">mathbfn</span> is called a <em>transverse block</em>. If <span class="SimpleMath">i</span> , <span class="SimpleMath">j</span> <span class="SimpleMath">∈</span><span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span>-<span class="SimpleMath">mathbfn</span> belong to the same block of a bipartition <span class="SimpleMath">x</span> , then we write (<span class="SimpleMath">i</span> , <span class="SimpleMath">j</span> )<span class="SimpleMath">∈</span><span class="SimpleMath">x</span> .</p>
<p>Let <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> be bipartitions of degree <span class="SimpleMath">n</span> . Their product <span class="SimpleMath">x</span> <span class="SimpleMath">y</span> can be described as follows. Define <span class="SimpleMath">mathbfn</span> '= {1', 2', ..., n'}</span>. From <span class="SimpleMath">x</span> , create a partition <span class="SimpleMath">x</span> ' of the set mathbfn ∪mathbfn ' by replacing each negative point -<span class="SimpleMath">i</span> in a block of <span class="SimpleMath">x</span> by the point <span class="SimpleMath">i</span> ', and create from y a partition y ' of the set <span class="SimpleMath">mathbfn</span> '∪-mathbfn by replacing each positive point i in a block of y by the point i '. Then define a relation on the set <span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span><span class="SimpleMath">mathbfn</span> '∪-mathbfn , where i and j are related if they are related in either x ' or <span class="SimpleMath">y</span> ', 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 .
<p>Equivalently, the product <span class="SimpleMath">x</span> <span class="SimpleMath">y</span> is defined to be the bipartition where <span class="SimpleMath">i</span> ,<span class="SimpleMath">j</span> <span class="SimpleMath">∈</span><span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span>-<span class="SimpleMath">mathbfn</span> (we assume without loss of generality that <span class="SimpleMath">i</span> <span class="SimpleMath">≥</span><span class="SimpleMath">j</span> ) belong to the same block of <span class="SimpleMath">x</span> <span class="SimpleMath">y</span> if either:</p>
<ul>
<li><p><span class="SimpleMath">i</span> <code class="code">=</code><span class="SimpleMath">j</span> ,</p>
</li>
<li><p><span class="SimpleMath">i</span> , <span class="SimpleMath">j</span> <span class="SimpleMath">∈</span> <span class="SimpleMath">mathbfn</span> and <span class="SimpleMath">(</span><span class="SimpleMath">i</span> ,<span class="SimpleMath">j</span> <span class="SimpleMath">)</span><span class="SimpleMath">∈</span> <span class="SimpleMath">x</span> , or</p>
</li>
<li><p><span class="SimpleMath">i</span> , <span class="SimpleMath">j</span> <span class="SimpleMath">∈</span> -<span class="SimpleMath">mathbfn</span> and <span class="SimpleMath">(</span><span class="SimpleMath">i</span> ,<span class="SimpleMath">j</span> <span class="SimpleMath">)</span><span class="SimpleMath">∈</span> <span class="SimpleMath">y</span> ;</p>
</li>
</ul>
<p>or there exists <span class="SimpleMath">r∈</span><span class="SimpleMath">N</span> and <span class="SimpleMath">k(1), k(2),..., k(r)∈ mathbfn</span> , and one of the following holds:</p>
<ul>
<li><p><span class="SimpleMath">r=2s-1</span> for some <span class="SimpleMath">s≥ 1</span> , <span class="SimpleMath">i</span> <span class="SimpleMath">∈</span><span class="SimpleMath">mathbfn</span> , <span class="SimpleMath">j</span> <span class="SimpleMath">∈</span> -<span class="SimpleMath">mathbfn</span> and</p>
<p class="pcenter">(i,-k(1))\in x,\ (k(1),k(2))\in y,\ (-k(2),-k(3))\in x,\
\ldots,\qquad</p>
<p class="pcenter">\qquad\ldots,\ (-k(2s-2),-k(2s-1))\in x,\
(k(2s-1),j)\in y;</p>
</li>
<li><p><span class="SimpleMath">r=2s</span> for some <span class="SimpleMath">s≥ 1</span> , and either <span class="SimpleMath">i</span> ,<span class="SimpleMath">j</span> <span class="SimpleMath">∈</span><span class="SimpleMath">mathbfn</span> , and</p>
<p class="pcenter">(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,</p>
<p>or <span class="SimpleMath">i</span> ,<span class="SimpleMath">j</span> <span class="SimpleMath">∈</span>-<span class="SimpleMath">mathbfn</span> , and</p>
<p class="pcenter">(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.</p>
</li>
</ul>
<p>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 <span class="SimpleMath">n</span> is the bipartition <span class="SimpleMath">{{i,-i}:i∈mathbfn}</span>. A bipartition is a unit if and only if each block is of the form <span class="SimpleMath">{</span><span class="SimpleMath">i</span> ,-<span class="SimpleMath">j</span> <span class="SimpleMath">}</span> for some <span class="SimpleMath">i</span> , <span class="SimpleMath">j</span> <span class="SimpleMath">∈</span><span class="SimpleMath">mathbfn</span> . Hence the group of units is isomorphic to the symmetric group on <span class="SimpleMath">mathbfn</span> .</p>
<p>Let <span class="SimpleMath">x</span> be a bipartition of degree <span class="SimpleMath">n</span> . Then we define <span class="SimpleMath">x</span> <span class="SimpleMath">^*</span> to be the bipartition obtained from <span class="SimpleMath">x</span> by replacing <span class="SimpleMath">i</span> by -<span class="SimpleMath">i</span> and -<span class="SimpleMath">i</span> by <span class="SimpleMath">i</span> in every block of <span class="SimpleMath">x</span> for all <span class="SimpleMath">i</span> <span class="SimpleMath">∈</span><span class="SimpleMath">mathbfn</span> . It is routine to verify that if <span class="SimpleMath">x</span> and <span class="SimpleMath">y</span> are arbitrary bipartitions of equal degree, then</p>
<p class="pcenter">
(x^*)^*=x,\quad xx^*x=x,\quad x^*xx^*=x^*,\quad (xy)^*=y^*x^*.
</p>
<p>In this way, the partition monoid is a <em>regular *-semigroup</em>.</p>
<p>A bipartition <span class="SimpleMath">x</span> of degree <span class="SimpleMath">n</span> is called <em>planar</em> if there do not exist distinct blocks <span class="SimpleMath">A, U ∈</span> <span class="SimpleMath">x</span> , along with <span class="SimpleMath">a, b ∈ A</span> and <span class="SimpleMath">u, v ∈ U</span>, such that <span class="SimpleMath">a < u < b < v</span>. Define <span class="SimpleMath">p</span> to be the bipartition of degree <span class="SimpleMath">n</span> with blocks <span class="SimpleMath">{{i, -(i+1)}:i∈{1,...,n-1}}</span> and <span class="SimpleMath">{n,-1}</span> . Note that <span class="SimpleMath">p</span> is a unit. A bipartition <span class="SimpleMath">x</span> of degree <span class="SimpleMath">n</span> is called <em>annular</em> if <span class="SimpleMath">x = p^i y p^j</span> for some planar bipartition <span class="SimpleMath">y</span> of degree <span class="SimpleMath">n</span> , and some integers <span class="SimpleMath">i</span> and <span class="SimpleMath">j</span> .</p>
<p>From a graphical perspective, as on Page 873 in <a href="chapBib.html#biBHalverson2005PartitionAlgebras">[HR05]</a>, a bipartition of degree <span class="SimpleMath">n</span> is planar if it can be represented as a graph without edges crossing inside of the rectangle formed by its vertices <span class="SimpleMath">mathbfn</span> <span class="SimpleMath">∪</span>-<span class="SimpleMath">mathbfn</span> . Similarly, as shown in Figure 2 in <a href="chapBib.html#biBauinger2012krohn">[Aui12]</a>, a bipartition of degree <span class="SimpleMath">n</span> is annular if it can be represented as a graph without edges crossing inside an annulus.</p>
<p><a id="X7850845886902FBF" name="X7850845886902FBF"></a></p>
<h4>3.1 <span class="Heading">The family and categories of bipartitions</span></h4>
<p><a id="X80F11BEF856E7902" name="X80F11BEF856E7902"></a></p>
<h5>3.1-1 IsBipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBipartition</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Every bipartition in <strong class="pkg">GAP</strong> belongs to the category <code class="code">IsBipartition</code>. Basic operations for bipartitions are <code class="func">RightBlocks</code> (<a href="chap3.html#X86A10B138230C2A4"><span class="RefLink">3.5-5</span></a>), <code class="func">LeftBlocks</code> (<a href="chap3.html#X7B9B364379D8F4E8"><span class="RefLink">3.5-6</span></a>), <code class="func">ExtRepOfObj</code> (<a href="chap3.html#X86F6506C780C6E08"><span class="RefLink">3.5-3</span></a>), <code class="func">LeftProjection</code> (<a href="chap3.html#X824EDD4582AAA8C7"><span class="RefLink">3.2-4</span></a>), <code class="func">RightProjection</code> (<a href="chap3.html#X790B71108070FAC2"><span class="RefLink">3.2-5</span></a>), <code class="func">StarOp</code> (<a href="chap3.html#X7CE00E0C79F62745"><span class="RefLink">3.2-6</span></a>), <code class="func">DegreeOfBipartition</code> (<a href="chap3.html#X780F5E00784FE58C"><span class="RefLink">3.5-1</span></a>), <code class="func">RankOfBipartition</code> (<a href="chap3.html#X82074756826AD2C2"><span class="RefLink">3.5-2</span></a>), multiplication of two bipartitions of equal degree is via <code class="keyw">*</code>.</p>
<p><a id="X82F5D10C85489832" name="X82F5D10C85489832"></a></p>
<h5>3.1-2 IsBipartitionCollection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBipartitionCollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBipartitionCollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Every collection of bipartitions belongs to the category <code class="code">IsBipartitionCollection</code>. For example, bipartition semigroups belong to <code class="code">IsBipartitionCollection</code>.</p>
<p>Every collection of collections of bipartitions belongs to <code class="code">IsBipartitionCollColl</code>. For example, a list of bipartition semigroups belongs to <code class="code">IsBipartitionCollColl</code>.</p>
<p><a id="X85D77073820C7E72" name="X85D77073820C7E72"></a></p>
<h4>3.2 <span class="Heading">Creating bipartitions</span></h4>
<p>There are several ways of creating bipartitions in <strong class="pkg">GAP</strong>, 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.</p>
<p><a id="X7E052E6378A5B758" name="X7E052E6378A5B758"></a></p>
<h5>3.2-1 Bipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Bipartition</code>( <var class="Arg">blocks</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p><code class="code">Bipartition</code> returns the bipartition <code class="code">x</code> with equivalence classes <var class="Arg">blocks</var>, which should be a list of duplicate-free lists whose union is <code class="code">[-n .. -1]</code> union <code class="code">[1 .. n]</code> for some positive integer <code class="code">n</code>.</p>
<p><code class="code">Bipartition</code> returns an error if the argument does not define a bipartition.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -1], [2, 3, -3], [-2]]);</span>
<bipartition: [ 1, -1 ], [ 2, 3, -3 ], [ -2 ]></pre></div>
<p><a id="X846AA7568435D2CE" name="X846AA7568435D2CE"></a></p>
<h5>3.2-2 BipartitionByIntRep</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BipartitionByIntRep</code>( <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p>It is possible to create a bipartition using its internal representation. The argument <var class="Arg">list</var> must be a list of positive integers not greater than <code class="code">n</code>, of length <code class="code">2 * n</code>, and where <code class="code">i</code> appears in the list only if <code class="code">i-1</code> occurs earlier in the list.</p>
<p>For example, the internal representation of the bipartition with blocks</p>
<div class="example"><pre>[1, -1], [2, 3, -2], [-3]</pre></div>
<p>has internal representation</p>
<div class="example"><pre>[1, 2, 2, 1, 2, 3]</pre></div>
<p>The internal representation indicates that the number <code class="code">1</code> is in class <code class="code">1</code>, the number <code class="code">2</code> is in class <code class="code">2</code>, the number <code class="code">3</code> is in class <code class="code">2</code>, the number <code class="code">-1</code> is in class <code class="code">1</code>, the number <code class="code">-2</code> is in class <code class="code">2</code>, and <code class="code">-3</code> is in class <code class="code">3</code>. As another example, <code class="code">[1, 3, 2, 1]</code> is not the internal representation of any bipartition since there is no <code class="code">2</code> before the <code class="code">3</code> in the second position.</p>
<p>In its first form <code class="code">BipartitionByIntRep</code> verifies that the argument <var class="Arg">list</var> is the internal representation of a bipartition.</p>
<p>See also <code class="func">IntRepOfBipartition</code> (<a href="chap3.html#X7ECD393A854C073B"><span class="RefLink">3.5-4</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">BipartitionByIntRep([1, 2, 2, 1, 3, 4]);</span>
<bipartition: [ 1, -1 ], [ 2, 3 ], [ -2 ], [ -3 ]></pre></div>
<p><a id="X8379B0538101FBC8" name="X8379B0538101FBC8"></a></p>
<h5>3.2-3 IdentityBipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IdentityBipartition</code>( <var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: The identity bipartition.</p>
<p>Returns the identity bipartition with degree <var class="Arg">n</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IdentityBipartition(10);</span>
<block bijection: [ 1, -1 ], [ 2, -2 ], [ 3, -3 ], [ 4, -4 ],
[ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ]></pre></div>
<p><a id="X824EDD4582AAA8C7" name="X824EDD4582AAA8C7"></a></p>
<h5>3.2-4 LeftOne</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftOne</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftProjection</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p>The <code class="code">LeftProjection</code> of a bipartition <var class="Arg">x</var> is the bipartition <code class="code"><var class="Arg">x</var> * Star(<var class="Arg">x</var>)</code>. It is so-named, since the left and right blocks of the left projection equal the left blocks of <var class="Arg">x</var>.</p>
<p>The left projection <code class="code">e</code> of <var class="Arg">x</var> is also a bipartition with the property that <code class="code">e * <var class="Arg">x</var> = <var class="Arg">x</var></code>. <code class="code">LeftOne</code> and <code class="code">LeftProjection</code> are synonymous.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [1, 4, -1, -2, -6], [2, 3, 5, -4], [6, -3], [-5]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftOne(x);</span>
<block bijection: [ 1, 4, -1, -4 ], [ 2, 3, 5, -2, -3, -5 ],
[ 6, -6 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftBlocks(x);</span>
<blocks: [ 1*, 4* ], [ 2*, 3*, 5* ], [ 6* ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightBlocks(LeftOne(x));</span>
<blocks: [ 1*, 4* ], [ 2*, 3*, 5* ], [ 6* ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftBlocks(LeftOne(x));</span>
<blocks: [ 1*, 4* ], [ 2*, 3*, 5* ], [ 6* ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftOne(x) * x = x;</span>
true</pre></div>
<p><a id="X790B71108070FAC2" name="X790B71108070FAC2"></a></p>
<h5>3.2-5 RightOne</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightOne</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightProjection</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p>The <code class="code">RightProjection</code> of a bipartition <var class="Arg">x</var> is the bipartition <code class="code">Star(<var class="Arg">x</var>) * <var class="Arg">x</var></code>. It is so-named, since the left and right blocks of the right projection equal the right blocks of <var class="Arg">x</var>.</p>
<p>The right projection <code class="code">e</code> of <var class="Arg">x</var> is also a bipartition with the property that <code class="code"><var class="Arg">x</var> * e = <var class="Arg">x</var></code>. <code class="code">RightOne</code> and <code class="code">RightProjection</code> are synonymous.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -1, -4], [2, -2, -3], [3, 4], [5, -5]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightOne(x);</span>
<block bijection: [ 1, 4, -1, -4 ], [ 2, 3, -2, -3 ], [ 5, -5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightBlocks(RightOne(x));</span>
<blocks: [ 1*, 4* ], [ 2*, 3* ], [ 5* ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftBlocks(RightOne(x));</span>
<blocks: [ 1*, 4* ], [ 2*, 3* ], [ 5* ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">RightBlocks(x);</span>
<blocks: [ 1*, 4* ], [ 2*, 3* ], [ 5* ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x * RightOne(x) = x;</span>
true</pre></div>
<p><a id="X7CE00E0C79F62745" name="X7CE00E0C79F62745"></a></p>
<h5>3.2-6 StarOp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StarOp</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Star</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p><code class="code">StarOp</code> returns the unique bipartition <code class="code">g</code> with the property that: <code class="code"><var class="Arg">x</var> * g * <var class="Arg">x</var> = <var class="Arg">x</var></code>, <code class="code">RightBlocks(<var class="Arg">x</var>) = LeftBlocks(g)</code>, and <code class="code">LeftBlocks(<var class="Arg">x</var>) = RightBlocks(g)</code>. The star <code class="code">g</code> can be obtained from <var class="Arg">x</var> by changing the sign of every integer in the external representation of <var class="Arg">x</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -4], [2, 3, 4], [5], [-1], [-2, -3], [-5]]);</span>
<bipartition: [ 1, -4 ], [ 2, 3, 4 ], [ 5 ], [ -1 ], [ -2, -3 ],
[ -5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := Star(x);</span>
<bipartition: [ 1 ], [ 2, 3 ], [ 4, -1 ], [ 5 ], [ -2, -3, -4 ],
[ -5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x * y * x = x;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">LeftBlocks(x) = RightBlocks(y);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">RightBlocks(x) = LeftBlocks(y);</span>
true</pre></div>
<p><a id="X8077265981409CCB" name="X8077265981409CCB"></a></p>
<h5>3.2-7 RandomBipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomBipartition</code>( [<var class="Arg">rs</var>, ]<var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RandomBlockBijection</code>( [<var class="Arg">rs</var>, ]<var class="Arg">n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p>If <var class="Arg">n</var> is a positive integer, then <code class="code">RandomBipartition</code> returns a random bipartition of degree <var class="Arg">n</var>, and <code class="code">RandomBlockBijection</code> returns a random block bijection of degree <var class="Arg">n</var>.</p>
<p>If the optional first argument <var class="Arg">rs</var> is a random source, then this is used to generate the bipartition returned by <code class="code">RandomBipartition</code> and <code class="code">RandomBlockBijection</code>.</p>
<p>Note that neither of these functions has a uniform distribution.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := RandomBipartition(6);</span>
<bipartition: [ 1, 2, 3, 4 ], [ 5 ], [ 6, -2, -3, -4 ], [ -1, -5 ], [ -6 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := RandomBlockBijection(4);</span>
<block bijection: [ 1, 4, -2 ], [ 2, -4 ], [ 3, -1, -3 ]></pre></div>
<p><a id="X7C2C44D281A0D2C9" name="X7C2C44D281A0D2C9"></a></p>
<h4>3.3 <span class="Heading">Changing the representation of a bipartition</span></h4>
<p>It is possible that a bipartition can be represented as another type of object, or that another type of <strong class="pkg">GAP</strong> object can be represented as a bipartition. In this section, we describe the functions in the <strong class="pkg">Semigroups</strong> package for changing the representation of bipartition, or for changing the representation of another type of object to that of a bipartition.</p>
<p>The operations <code class="func">AsPermutation</code> (<a href="chap3.html#X7C684CD38405DBEF"><span class="RefLink">3.3-5</span></a>), <code class="func">AsPartialPerm</code> (<a href="chap3.html#X7C5212EF7A200E63"><span class="RefLink">3.3-4</span></a>), <code class="func">AsTransformation</code> (<a href="chap3.html#X7CE91D0C83865214"><span class="RefLink">3.3-3</span></a>) can be used to convert bipartitions into permutations, partial permutations, or transformations where appropriate.</p>
<p><a id="X855126D98583C181" name="X855126D98583C181"></a></p>
<h5>3.3-1 AsBipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsBipartition</code>( <var class="Arg">x</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A bipartition.</p>
<p><code class="code">AsBipartition</code> returns the bipartition, permutation, transformation, or partial permutation <var class="Arg">x</var>, as a bipartition of degree <var class="Arg">n</var>.</p>
<p>There are several possible arguments for <code class="code">AsBipartition</code>:</p>
<dl>
<dt><strong class="Mark">permutations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a permutation and <var class="Arg">n</var> is a positive integer, then <code class="code">AsBipartition(<var class="Arg">x</var>, <var class="Arg">n</var>)</code> returns the bipartition on <code class="code">[1 .. <var class="Arg">n</var>]</code> with classes <code class="code">[i, i ^ <var class="Arg">x</var>]</code> for all <code class="code">i = 1 .. n</code>.</p>
<p>If no positive integer <var class="Arg">n</var> is specified, then the largest moved point of <var class="Arg">x</var> is used as the value for <var class="Arg">n</var>; see <code class="func">LargestMovedPoint</code> (<a href="../../../doc/ref/chap42_mj.html#X84AA603987C94AC0"><span class="RefLink">Reference: LargestMovedPoint for a permutation</span></a>).</p>
</dd>
<dt><strong class="Mark">transformations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a transformation and <var class="Arg">n</var> is a positive integer such that <var class="Arg">x</var> is a transformation of <code class="code">[1 .. <var class="Arg">n</var>]</code>, then <code class="code">AsTransformation</code> returns the bipartition with classes <span class="SimpleMath">(i)f ^ -1∪ {i}</span> for all <code class="code">i</code> in the image of <var class="Arg">x</var>.</p>
<p>If the positive integer <var class="Arg">n</var> is not specified, then the degree of <var class="Arg">x</var> is used as the value for <var class="Arg">n</var>.</p>
</dd>
<dt><strong class="Mark">partial permutations</strong></dt>
<dd><p>If <var class="Arg">x</var> is a partial permutation and <var class="Arg">n</var> is a positive integer, then <code class="code">AsBipartition</code> returns the bipartition with classes <code class="code">[i, i ^ <var class="Arg">x</var>]</code> for <code class="code">i</code> in <code class="code">[1 .. <var class="Arg">n</var>]</code>. Thus the degree of the returned bipartition is the maximum of <var class="Arg">n</var> and the values <code class="code">i ^ <var class="Arg">x</var></code> where <code class="code">i</code> in <code class="code">[1 .. <var class="Arg">n</var>]</code>.</p>
<p>If the optional argument <var class="Arg">n</var> is not present, then the default value of the maximum of the largest moved point and the largest image of a moved point of <var class="Arg">x</var> plus <code class="code">1</code> is used.</p>
</dd>
<dt><strong class="Mark">bipartitions</strong></dt>
<dd><p>If <var class="Arg">x</var> is a bipartition and <var class="Arg">n</var> is a non-negative integer, then <code class="code">AsBipartition</code> returns a bipartition corresponding to <var class="Arg">x</var> with degree <var class="Arg">n</var>.</p>
<p>If <var class="Arg">n</var> equals the degree of <var class="Arg">x</var>, then <var class="Arg">x</var> is returned. If <var class="Arg">n</var> is less than the degree of <var class="Arg">x</var>, then this function returns the bipartition obtained from <var class="Arg">x</var> by removing the values exceeding <var class="Arg">n</var> or less than <var class="Arg">-n</var> from the blocks of <var class="Arg">x</var>. If <var class="Arg">n</var> is greater than the degree of <var class="Arg">x</var>, then this function returns the bipartition with the same blocks as <var class="Arg">x</var> and the singleton blocks <code class="code">i</code> and <code class="code">-i</code> for all <code class="code">i</code> greater than the degree of <var class="Arg">x</var></p>
</dd>
<dt><strong class="Mark">pbrs</strong></dt>
<dd><p>If <var class="Arg">x</var> is a pbr satisfying <code class="func">IsBipartitionPBR</code> (<a href="chap4.html#X81EC86397E098BC8"><span class="RefLink">4.5-8</span></a>) and <var class="Arg">n</var> is a non-negative integer, then <code class="code">AsBipartition</code> returns the bipartition corresponding to <var class="Arg">x</var> with degree <var class="Arg">n</var>.</p>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Transformation([3, 5, 3, 4, 1, 2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 5);</span>
<bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ], [ -2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x);</span>
<bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ],
[ 6, -2 ], [ -6 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 10);</span>
<bipartition: [ 1, 3, -3 ], [ 2, -5 ], [ 4, -4 ], [ 5, -1 ],
[ 6, -2 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ], [ -6 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition((1, 3)(2, 4));</span>
<block bijection: [ 1, -3 ], [ 2, -4 ], [ 3, -1 ], [ 4, -2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition((1, 3)(2, 4), 10);</span>
<block bijection: [ 1, -3 ], [ 2, -4 ], [ 3, -1 ], [ 4, -2 ],
[ 5, -5 ], [ 6, -6 ], [ 7, -7 ], [ 8, -8 ], [ 9, -9 ], [ 10, -10 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([1, 2, 3, 4, 5, 6], [6, 7, 1, 4, 3, 2]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 11);</span>
<bipartition: [ 1, -6 ], [ 2, -7 ], [ 3, -1 ], [ 4, -4 ], [ 5, -3 ],
[ 6, -2 ], [ 7 ], [ 8 ], [ 9 ], [ 10 ], [ 11 ], [ -5 ], [ -8 ],
[ -9 ], [ -10 ], [ -11 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x);</span>
<bipartition: [ 1, -6 ], [ 2, -7 ], [ 3, -1 ], [ 4, -4 ], [ 5, -3 ],
[ 6, -2 ], [ 7 ], [ -5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(Transformation([1, 1, 2]), 1);</span>
<block bijection: [ 1, -1 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 2, -2], [3], [4, 5, 6, -1],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [-3, -4, -5, -6]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 0);</span>
<empty bipartition>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 2);</span>
<bipartition: [ 1, 2, -2 ], [ -1 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 8);</span>
<bipartition: [ 1, 2, -2 ], [ 3 ], [ 4, 5, 6, -1 ], [ 7 ], [ 8 ],
[ -3, -4, -5, -6 ], [ -7 ], [ -8 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PBR(</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[-1, 1, 2, 3, 4], [-1, 1, 2, 3, 4],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [-1, 1, 2, 3, 4], [-1, 1, 2, 3, 4]],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[[-1, 1, 2, 3, 4], [-2], [-3], [-4]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x);</span>
<bipartition: [ 1, 2, 3, 4, -1 ], [ -2 ], [ -3 ], [ -4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 2);</span>
<bipartition: [ 1, 2, -1 ], [ -2 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 4);</span>
<bipartition: [ 1, 2, 3, 4, -1 ], [ -2 ], [ -3 ], [ -4 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 5);</span>
<bipartition: [ 1, 2, 3, 4, -1 ], [ 5 ], [ -2 ], [ -3 ], [ -4 ],
[ -5 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 0);</span>
<empty bipartition></pre></div>
<p><a id="X85A5AD2B7F3B776F" name="X85A5AD2B7F3B776F"></a></p>
<h5>3.3-2 AsBlockBijection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsBlockBijection</code>( <var class="Arg">x</var>[, <var class="Arg">n</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A block bijection.</p>
<p>When the argument <var class="Arg">x</var> is a partial perm and <var class="Arg">n</var> is a positive integer which is greater than the maximum of the degree and codegree of <var class="Arg">x</var>, this function returns a block bijection corresponding to <var class="Arg">x</var>. This block bijection has the same non-singleton classes as <code class="code">g := AsBipartition(<var class="Arg">x</var>, <var class="Arg">n</var>)</code> and one additional class which is the union the singleton classes of <code class="code">g</code>.</p>
<p>If the optional second argument <var class="Arg">n</var> is not present, then the maximum of the degree and codegree of <var class="Arg">x</var> plus 1 is used by default. If the second argument <var class="Arg">n</var> is not greater than this maximum, then an error is given.</p>
<p>This is the value at <var class="Arg">x</var> of the embedding of the symmetric inverse monoid into the dual symmetric inverse monoid given in the FitzGerald-Leech Theorem <a href="chapBib.html#biBFitzgerald1998aa">[FL98]</a>.</p>
<p>When the argument <var class="Arg">x</var> is a partial perm bipartition (see <code class="func">IsPartialPermBipartition</code> (<a href="chap3.html#X87C771D37B1FE95C"><span class="RefLink">3.5-15</span></a>)) then this operation returns <code class="code">AsBlockBijection(AsPartialPerm(<var class="Arg">x</var>)[, <var class="Arg">n</var>])</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := PartialPerm([1, 2, 3, 6, 7, 10], [9, 5, 6, 1, 7, 8]);</span>
[2,5][3,6,1,9][10,8](7)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(x, 11);</span>
<bipartition: [ 1, -9 ], [ 2, -5 ], [ 3, -6 ], [ 4 ], [ 5 ],
[ 6, -1 ], [ 7, -7 ], [ 8 ], [ 9 ], [ 10, -8 ], [ 11 ], [ -2 ],
[ -3 ], [ -4 ], [ -10 ], [ -11 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBlockBijection(x, 10);</span>
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)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBlockBijection(x, 11);</span>
<block bijection: [ 1, -9 ], [ 2, -5 ], [ 3, -6 ],
[ 4, 5, 8, 9, 11, -2, -3, -4, -10, -11 ], [ 6, -1 ], [ 7, -7 ],
[ 10, -8 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -3], [2], [3, -2], [-1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPartialPermBipartition(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBlockBijection(x);</span>
<block bijection: [ 1, -3 ], [ 2, 4, -1, -4 ], [ 3, -2 ]></pre></div>
<p><a id="X7CE91D0C83865214" name="X7CE91D0C83865214"></a></p>
<h5>3.3-3 AsTransformation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsTransformation</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A transformation.</p>
<p>When the argument <var class="Arg">x</var> is a bipartition, that mathematically defines a transformation, this function returns that transformation. A bipartition <var class="Arg">x</var> defines a transformation if and only if its right blocks are the image list of a permutation of <code class="code">[1 .. n]</code> where <code class="code">n</code> is the degree of <var class="Arg">x</var>.</p>
<p>See <code class="func">IsTransBipartition</code> (<a href="chap3.html#X79C556827A578509"><span class="RefLink">3.5-12</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -3], [2, -2], [3, 5, 10, -7],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [4, -12], [6, 7, -6], [8, -5], [9, -11],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [11, 12, -10], [-1], [-4], [-8], [-9]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsTransformation(x);</span>
Transformation( [ 3, 2, 7, 12, 7, 6, 6, 5, 11, 7, 10, 10 ] )
<span class="GAPprompt">gap></span> <span class="GAPinput">IsTransBipartition(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 5], [2, 4, 8, 10],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [3, 6, 7, -1, -2], [9, -4, -6, -9],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [-3, -5], [-7, -8], [-10]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsTransformation(x);</span>
Error, the argument (a bipartition) does not define a transformation</pre></div>
<p><a id="X7C5212EF7A200E63" name="X7C5212EF7A200E63"></a></p>
<h5>3.3-4 AsPartialPerm</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsPartialPerm</code>( <var class="Arg">x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A partial perm.</p>
<p>When the argument <var class="Arg">x</var> is a bipartition that mathematically defines a partial perm, this function returns that partial perm.</p>
<p>A bipartition <var class="Arg">x</var> defines a partial perm if and only if its numbers of left and right blocks both equal its degree.</p>
<p>See <code class="func">IsPartialPermBipartition</code> (<a href="chap3.html#X87C771D37B1FE95C"><span class="RefLink">3.5-15</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -4], [2, -2], [3, -10], [4, -5],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [5, -9], [6], [7], [8, -6], [9, -3], [10, -8],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [-1], [-7]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPartialPermBipartition(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPartialPerm(x);</span>
[1,4,5,9,3,10,8,6](2)
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -2, -4], [2, 3, 4, -3], [-1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPartialPermBipartition(x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPartialPerm(x);</span>
Error, the argument (a bipartition) does not define a partial perm</pre></div>
<p><a id="X7C684CD38405DBEF" name="X7C684CD38405DBEF"></a></p>
<h5>3.3-5 AsPermutation</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsPermutation</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A permutation.</p>
<p>When the argument <var class="Arg">x</var> is a bipartition that mathematically defines a permutation, this function returns that permutation.</p>
<p>A bipartition <var class="Arg">x</var> defines a permutation if and only if its numbers of left, right, and transverse blocks all equal its degree.</p>
<p>See <code class="func">IsPermBipartition</code> (<a href="chap3.html#X8031B53E7D0ECCFA"><span class="RefLink">3.5-14</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, -6], [2, -4], [3, -2], [4, -5],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [5, -3], [6, -1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPermBipartition(x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPermutation(x);</span>
(1,6)(2,4,5,3)
<span class="GAPprompt">gap></span> <span class="GAPinput">AsBipartition(last) = x;</span>
true</pre></div>
<p><a id="X83F2C3C97E8FFA49" name="X83F2C3C97E8FFA49"></a></p>
<h4>3.4 <span class="Heading">Operators for bipartitions</span></h4>
<dl>
<dt><strong class="Mark"><code class="code"><var class="Arg">f</var> * <var class="Arg">g</var></code></strong></dt>
<dd><p>returns the composition of <var class="Arg">f</var> and <var class="Arg">g</var> when <var class="Arg">f</var> and <var class="Arg">g</var> are bipartitions.</p>
</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">f</var> < <var class="Arg">g</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the internal representation of <var class="Arg">f</var> is lexicographically less than the internal representation of <var class="Arg">g</var> and <code class="keyw">false</code> if it is not.</p>
</dd>
<dt><strong class="Mark"><code class="code"><var class="Arg">f</var> = <var class="Arg">g</var></code></strong></dt>
<dd><p>returns <code class="keyw">true</code> if the bipartition <var class="Arg">f</var> equals the bipartition <var class="Arg">g</var> and returns <code class="keyw">false</code> if it does not.</p>
</dd>
</dl>
<p><a id="X7A39D36086647536" name="X7A39D36086647536"></a></p>
<h5>3.4-1 PartialPermLeqBipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PartialPermLeqBipartition</code>( <var class="Arg">x</var>, <var class="Arg">y</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>If <var class="Arg">x</var> and <var class="Arg">y</var> are partial perm bipartitions, i.e. they satisfy <code class="func">IsPartialPermBipartition</code> (<a href="chap3.html#X87C771D37B1FE95C"><span class="RefLink">3.5-15</span></a>), then this function returns <code class="code">AsPartialPerm(<var class="Arg">x</var>) < AsPartialPerm(<var class="Arg">y</var>)</code>.</p>
<p><a id="X8608D78F83D55108" name="X8608D78F83D55108"></a></p>
<h5>3.4-2 NaturalLeqPartialPermBipartition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NaturalLeqPartialPermBipartition</code>( <var class="Arg">x</var>, <var class="Arg">y</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>The <em>natural partial order</em> <span class="SimpleMath">≤</span> on an inverse semigroup <code class="code">S</code> is defined by <code class="code">s</code> <span class="SimpleMath">≤</span> <code class="code">t</code> if there exists an idempotent <code class="code">e</code> in <code class="code">S</code> such that <code class="code">s = et</code>. Hence if <var class="Arg">x</var> and <var class="Arg">y</var> are partial perm bipartitions, then <var class="Arg">x</var> <span class="SimpleMath">≤</span> <var class="Arg">y</var> if and only if <code class="code">AsPartialPerm(<var class="Arg">x</var>)</code> is a restriction of <code class="code">AsPartialPerm(<var class="Arg">y</var>)</code>.</p>
<p><code class="code">NaturalLeqPartialPermBipartition</code> returns <code class="keyw">true</code> if <code class="code">AsPartialPerm(<var class="Arg">x</var>)</code> is a restriction of <code class="code">AsPartialPerm(<var class="Arg">y</var>)</code> and <code class="keyw">false</code> if it is not. Note that since this is a partial order and not a total order, it is possible that <var class="Arg">x</var> and <var class="Arg">y</var> are incomparable with respect to the natural partial order.</p>
<p><a id="X79E8FA077E24C1F4" name="X79E8FA077E24C1F4"></a></p>
<h5>3.4-3 NaturalLeqBlockBijection</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NaturalLeqBlockBijection</code>( <var class="Arg">x</var>, <var class="Arg">y</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>The <em>natural partial order</em> <span class="SimpleMath">≤</span> on an inverse semigroup <code class="code">S</code> is defined by <code class="code">s</code> <span class="SimpleMath">≤</span> <code class="code">t</code> if there exists an idempotent <code class="code">e</code> in <code class="code">S</code> such that <code class="code">s = et</code>. Hence if <var class="Arg">x</var> and <var class="Arg">y</var> are block bijections, then <var class="Arg">x</var> <span class="SimpleMath">≤</span> <var class="Arg">y</var> if and only if <var class="Arg">x</var> contains <var class="Arg">y</var>.</p>
<p><code class="code">NaturalLeqBlockBijection</code> returns <code class="keyw">true</code> if <var class="Arg">x</var> is contained in <var class="Arg">y</var> and <code class="keyw">false</code> if it is not. Note that since this is a partial order and not a total order, it is possible that <var class="Arg">x</var> and <var class="Arg">y</var> are incomparable with respect to the natural partial order.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 2, -3], [3, -1, -2], [4, -4],</ | |
