Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 29.7.2025 mit Größe 112 kB image not shown  

Quelle  chap3_mj.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/semigroups/doc/chap3_mj.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>
<script type="text/javascript"
  src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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_mj.html">Top</a>  <a href="chap1_mj.html">1</a>  <a href="chap2_mj.html">2</a>  <a href="chap3_mj.html">3</a>  <a href="chap4_mj.html">4</a>  <a href="chap5_mj.html">5</a>  <a href="chap6_mj.html">6</a>  <a href="chap7_mj.html">7</a>  <a href="chap8_mj.html">8</a>  <a href="chap9_mj.html">9</a>  <a href="chap10_mj.html">10</a>  <a href="chap11_mj.html">11</a>  <a href="chap12_mj.html">12</a>  <a href="chap13_mj.html">13</a>  <a href="chap14_mj.html">14</a>  <a href="chap15_mj.html">15</a>  <a href="chap16_mj.html">16</a>  <a href="chap17_mj.html">17</a>  <a href="chap18_mj.html">18</a>  <a href="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap2_mj.html">[Previous Chapter]</a>    <a href="chap4_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3.html">[MathJax off]</a></p>
<p><a id="X7C18DB427C9C0917" name="X7C18DB427C9C0917"></a></p>
<div class="ChapSects"><a href="chap3_mj.html#X7C18DB427C9C0917">3 <span class="Heading">
    Bipartitions and blocks
  </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X80F11BEF856E7902">3.1-1 IsBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X82F5D10C85489832">3.1-2 IsBipartitionCollection</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X7E052E6378A5B758">3.2-1 Bipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X846AA7568435D2CE">3.2-2 BipartitionByIntRep</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8379B0538101FBC8">3.2-3 IdentityBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X824EDD4582AAA8C7">3.2-4 LeftOne</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X790B71108070FAC2">3.2-5 RightOne</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7CE00E0C79F62745">3.2-6 StarOp</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8077265981409CCB">3.2-7 RandomBipartition</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X855126D98583C181">3.3-1 AsBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X85A5AD2B7F3B776F">3.3-2 AsBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7CE91D0C83865214">3.3-3 AsTransformation</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7C5212EF7A200E63">3.3-4 AsPartialPerm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7C684CD38405DBEF">3.3-5 AsPermutation</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X7A39D36086647536">3.4-1 PartialPermLeqBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8608D78F83D55108">3.4-2 NaturalLeqPartialPermBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X79E8FA077E24C1F4">3.4-3 NaturalLeqBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7D9F5A248028FF52">3.4-4 PermLeftQuoBipartition</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X780F5E00784FE58C">3.5-1 DegreeOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X82074756826AD2C2">3.5-2 RankOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X86F6506C780C6E08">3.5-3 ExtRepOfObj</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7ECD393A854C073B">3.5-4 IntRepOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X86A10B138230C2A4">3.5-5 RightBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7B9B364379D8F4E8">3.5-6 LeftBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X79AEDB5382FD25CF">3.5-7 NrLeftBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X86385A3C8662E1A7">3.5-8 NrRightBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8110B6557A98FB5C">3.5-9 NrBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8657EE2B79E1DD02">3.5-10 DomainOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X84569A187A211332">3.5-11 CodomainOfBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X79C556827A578509">3.5-12 IsTransBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7F0B8ACC7C9A937F">3.5-13 IsDualTransBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8031B53E7D0ECCFA">3.5-14 IsPermBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X87C771D37B1FE95C">3.5-15 IsPartialPermBipartition</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X829494DF7FD6CFEC">3.5-16 IsBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X79D54AD8833B9551">3.5-17 IsUniformBlockBijection</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7B87B9B081FF88BB">3.5-18 CanonicalBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X7D77092078EC860C">3.6-1 IsBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X81302B217DCAAE6F">3.6-2 BLOCKS_NC</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7D2CB12279623CE2">3.6-3 ExtRepOfObj</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X787D22AE7FA69239">3.6-4 RankOfBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X8527DC6A8771C2BE">3.6-5 DegreeOfBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X815D99A983B2355F">3.6-6 ProjectionFromBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X7B701DA37F75E77B">3.7-1 OnRightBlocks</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7A5A4AF57BEA2313">3.7-2 OnLeftBlocks</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3_mj.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_mj.html#X810BFF647C4E191E">3.8-1 IsBipartitionSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X80C37124794636F3">3.8-2 IsBlockBijectionSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X79A706A582ABE558">3.8-3 IsPartialPermBipartitionSemigroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.html#X7DEE07577D7379AC">3.8-4 IsPermBipartitionGroup</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3_mj.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\in\)</span><span class="SimpleMath">\(\mathbb{N}\)</span> , let <span class="SimpleMath">\(\mathbf{n}\)</span> <span class="SimpleMath">\( = \{1, 2, \ldots, n\}\)</span>, and let <span class="SimpleMath">\(-\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> <span class="SimpleMath">\( = \{-1, -2, \ldots, -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">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</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">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</span> whose union is <span class="SimpleMath">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</span> ; these subsets are called the <em>blocks</em> of <span class="SimpleMath">\(x\)</span> . A block containing elements of both <span class="SimpleMath">\(\mathbf{n}\)</span> and -<span class="SimpleMath">\(\mathbf{n}\)</span> is called a <em>transverse block</em>. If <span class="SimpleMath">\(i\)</span> , <span class="SimpleMath">\(j\)</span> <span class="SimpleMath">\(\in\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</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">\(\in\)</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">\(\mathbf{n}\)</span> '\( = \{1', 2', \ldots, n'\}\)</span>. From <span class="SimpleMath">\(x\)</span> , create a partition <span class="SimpleMath">\(x\)</span> ' of the set \(\mathbf{n}\) \(\cup\)\(\mathbf{n}\) ' 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">\(\mathbf{n}\)</span> '\(\cup\)-\(\mathbf{n}\) by replacing each positive point \(i\) in a block of \(y\) by the point \(i\) '. Then define a relation on the set <span class="SimpleMath">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> '\(\cup\)-\(\mathbf{n}\) , 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 \(\mathbf{n}\) \(\cup\)-\(\mathbf{n}\) .



<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">\(\in\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</span> (we assume without loss of generality that <span class="SimpleMath">\(i\)</span> <span class="SimpleMath">\(\geq\)</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">\(\in\)</span> <span class="SimpleMath">\(\mathbf{n}\)</span> and <span class="SimpleMath">\((\)</span><span class="SimpleMath">\(i\)</span> ,<span class="SimpleMath">\(j\)</span> <span class="SimpleMath">\()\)</span><span class="SimpleMath">\(\in\)</span> <span class="SimpleMath">\(x\)</span> , or</p>

</li>
<li><p><span class="SimpleMath">\(i\)</span> , <span class="SimpleMath">\(j\)</span> <span class="SimpleMath">\(\in\)</span> -<span class="SimpleMath">\(\mathbf{n}\)</span> and <span class="SimpleMath">\((\)</span><span class="SimpleMath">\(i\)</span> ,<span class="SimpleMath">\(j\)</span> <span class="SimpleMath">\()\)</span><span class="SimpleMath">\(\in\)</span> <span class="SimpleMath">\(y\)</span> ;</p>

</li>
</ul>
<p>or there exists <span class="SimpleMath">\(r\in\)</span><span class="SimpleMath">\(\mathbb{N}\)</span> and <span class="SimpleMath">\(k(1), k(2),\ldots, k(r)\in \mathbf{n}\)</span> , and one of the following holds:</p>


<ul>
<li><p><span class="SimpleMath">\(r=2s-1\)</span> for some <span class="SimpleMath">\(s\geq 1\)</span> , <span class="SimpleMath">\(i\)</span> <span class="SimpleMath">\(\in\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> , <span class="SimpleMath">\(j\)</span> <span class="SimpleMath">\(\in\)</span> -<span class="SimpleMath">\(\mathbf{n}\)</span> and</p>

<p class="center">\[(i,-k(1))\in x,\ (k(1),k(2))\in y,\ (-k(2),-k(3))\in x,\
          \ldots,\qquad\]</p>

<p class="center">\[\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\geq 1\)</span> , and either <span class="SimpleMath">\(i\)</span> ,<span class="SimpleMath">\(j\)</span> <span class="SimpleMath">\(\in\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> , and</p>

<p class="center">\[(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">\(\in\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</span> , and</p>

<p class="center">\[(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">\(\left\{\{i,-i\}:i\in\mathbf{n}\right\}\)</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">\(\in\)</span><span class="SimpleMath">\(\mathbf{n}\)</span> . Hence the group of units is isomorphic to the symmetric group on <span class="SimpleMath">\(\mathbf{n}\)</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">\(\in\)</span><span class="SimpleMath">\(\mathbf{n}\)</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="center">\[
      (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 \in\)</span> <span class="SimpleMath">\(x\)</span> , along with <span class="SimpleMath">\(a, b \in A\)</span> and <span class="SimpleMath">\(u, v \in 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">\(\left\{\{i, -(i+1)\}:i\in\{1,\ldots,n-1\right\}\}\)</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_mj.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">\(\mathbf{n}\)</span> <span class="SimpleMath">\(\cup\)</span>-<span class="SimpleMath">\(\mathbf{n}\)</span> . Similarly, as shown in Figure 2 in <a href="chapBib_mj.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_mj.html#X86A10B138230C2A4"><span class="RefLink">3.5-5</span></a>), <code class="func">LeftBlocks</code> (<a href="chap3_mj.html#X7B9B364379D8F4E8"><span class="RefLink">3.5-6</span></a>), <code class="func">ExtRepOfObj</code> (<a href="chap3_mj.html#X86F6506C780C6E08"><span class="RefLink">3.5-3</span></a>), <code class="func">LeftProjection</code> (<a href="chap3_mj.html#X824EDD4582AAA8C7"><span class="RefLink">3.2-4</span></a>), <code class="func">RightProjection</code> (<a href="chap3_mj.html#X790B71108070FAC2"><span class="RefLink">3.2-5</span></a>), <code class="func">StarOp</code> (<a href="chap3_mj.html#X7CE00E0C79F62745"><span class="RefLink">3.2-6</span></a>), <code class="func">DegreeOfBipartition</code> (<a href="chap3_mj.html#X780F5E00784FE58C"><span class="RefLink">3.5-1</span></a>), <code class="func">RankOfBipartition</code> (<a href="chap3_mj.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_mj.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_mj.html#X7C684CD38405DBEF"><span class="RefLink">3.3-5</span></a>), <code class="func">AsPartialPerm</code> (<a href="chap3_mj.html#X7C5212EF7A200E63"><span class="RefLink">3.3-4</span></a>), <code class="func">AsTransformation</code> (<a href="chap3_mj.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}\cup \{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_mj.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_mj.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_mj.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_mj.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_mj.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_mj.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_mj.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">\(\leq\)</span> on an inverse semigroup <code class="code">S</code> is defined by <code class="code">s</code> <span class="SimpleMath">\(\leq\)</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">\(\leq\)</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">\(\leq\)</span> on an inverse semigroup <code class="code">S</code> is defined by <code class="code">s</code> <span class="SimpleMath">\(\leq\)</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">\(\leq\)</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],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [5, -5], [6, -6], [7, -7],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [8, -8], [9, -9], [10, -10]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := Bipartition([[1, -2], [2, -1], [3, -3],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [4, -4], [5, -5], [6, -6], [7, -7],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [8, -8], [9, -9], [10, -10]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">z := Bipartition([Union([1 .. 10], [-10 .. -1])]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">NaturalLeqBlockBijection(x, y);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">NaturalLeqBlockBijection(y, x);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">NaturalLeqBlockBijection(z, x);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">NaturalLeqBlockBijection(z, y);</span>
true</pre></div>

<p><a id="X7D9F5A248028FF52" name="X7D9F5A248028FF52"></a></p>

<h5>3.4-4 PermLeftQuoBipartition</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermLeftQuoBipartition</code>( <var class="Arg">x</var>, <var class="Arg">y</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: A permutation.</p>

<p>If <var class="Arg">x</var> and <var class="Arg">y</var> are bipartitions with equal left and right blocks, then <code class="code">PermLeftQuoBipartition</code> returns the permutation of the indices of the right blocks of <var class="Arg">x</var> (and <var class="Arg">y</var>) induced by <code class="code">Star(<var class="Arg">x</var>) * <var class="Arg">y</var></code>.</p>

<p><code class="code">PermLeftQuoBipartition</code> verifies that <var class="Arg">x</var> and <var class="Arg">y</var> have equal left and right blocks, and returns an error if they do not.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 4, 6, 7, 8, 10], [2, 5, -1, -2, -8],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [3, -3, -6, -7, -9], [9, -4, -5], [-10]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">y := Bipartition([[1, 4, 6, 7, 8, 10], [2, 5, -3, -6, -7, -9],</span>
<span class="GAPprompt">></span> <span class="GAPinput">                     [3, -4, -5], [9, -1, -2, -8], [-10]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">PermLeftQuoBipartition(x, y);</span>
(1,2,3)
<span class="GAPprompt">gap></span> <span class="GAPinput">Star(x) * y;</span>
<bipartition: [ 1, 2, 8, -3, -6, -7, -9 ], [ 3, 6, 7, 9, -4, -5 ],
 [ 4, 5, -1, -2, -8 ], [ 10 ], [ -10 ]></pre></div>

<p><a id="X87F3A304814797CE" name="X87F3A304814797CE"></a></p>

<h4>3.5 <span class="Heading">Attributes for bipartitons</span></h4>

<p>In this section we describe various attributes that a bipartition can possess.</p>

<p><a id="X780F5E00784FE58C" name="X780F5E00784FE58C"></a></p>

<h5>3.5-1 DegreeOfBipartition</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DegreeOfBipartition</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">‣ DegreeOfBipartitionCollection</code>( <var class="Arg">x</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A positive integer.</p>

<p>The degree of a bipartition is, roughly speaking, the number of points where it is defined. More precisely, if <var class="Arg">x</var> is a bipartition defined on <code class="code">2 * n</code> points, then the degree of <var class="Arg">x</var> is <code class="code">n</code>.</p>

<p>The degree of a collection <var class="Arg">coll</var> of bipartitions of equal degree is just the degree of any (and every) bipartition in <var class="Arg">coll</var>. The degree of collection of bipartitions of unequal degrees is not defined.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x := Bipartition([[1, 7, -3, -8], [2, 6],</span>
--> --------------------

--> maximum size reached

--> --------------------

100%


¤ Dauer der Verarbeitung: 0.28 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Normalansicht

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.