====== Category of partitions ======

This page is about //easy// categories of partitions in the sense of Banica and Speicher [(ref:BS09)]. If we equip those with a linear structure, we get [[linear_category_of_partitions|linear categories of partitions]].


===== Definition =====

==== Partitions ====

Let $k,l\in\mathbb{N}_0$, by a [[partition|partition]] of $k$ upper and $l$ lower points we mean herre a partition of the set $\{1,\dots,k\}\sqcup\{1,\dots,l\}\approx\{1,\dots,k+l\}$, that is, a decomposition of the set of $k+l$ points into non-empty disjoint subsets, called **blocks**. The first $k$ points are called **upper** and the last $l$ points are called **lower**. The set of all partitions on $k$ upper and $l$ lower points is denoted $\Pscr(k,l)$. We denote the union $\Pscr:=\bigcup_{k,l\in\N_0}\Pscr(k,l)$.

We illustrate partitions graphically by putting $k$ points in one row and $l$ points on another row below and connecting by lines those points that are grouped in one block. All lines are drawn between those two rows.

Below, we give an example of two partitions $p\in\Pscr(3,4)$ and $q\in\Pscr(4,4)$ defined by their graphical representation. The first set of points is decomposed into three blocks, whereas the second one is into five blocks. In addition, the first one is an example of a **non-crossing** partition, i.e. a partition that can be drawn in a way that lines connecting different blocks do not intersect (following the rule that all lines are between the two rows of points). On the other hand, the second partition has one crossing.
$$
p=
\BigPartition{
\Pblock 0 to 0.25:2,3
\Pblock 1 to 0.75:1,2,3
\Psingletons 0 to 0.25:1,4
\Pline (2.5,0.25) (2.5,0.75)
}
\qquad
q=
\BigPartition{
\Psingletons 0 to 0.25:1,4
\Psingletons 1 to 0.75:1,4
\Pline (2,0) (3,1)
\Pline (3,0) (2,1)
\Pline (2.75,0.25) (4,0.25)
}
$$

A block containing a single point is called a **singleton**. In particular, the partitions containing only one point are called singletons and for clarity denoted by an arrow $\singleton\in\Pscr(0,1)$ and $\upsingleton\in\Pscr(1,0)$.

==== The category structure ====

The set of all [[Partition|partitions]] $\Pscr$ can be given the structure of a monoidal involutive category by introducing the following operations.

  * The **tensor product** of two partitions $p\in\Pscr(k,l)$ and $q\in\Pscr(k',l')$ is the partition $p\otimes q\in \Pscr(k+k',l+l')$ obtained by writing the graphical representations of $p$ and $q$ "side by side".
$$
\BigPartition{
\Pblock 0 to 0.25:2,3
\Pblock 1 to 0.75:1,2,3
\Psingletons 0 to 0.25:1,4
\Pline (2.5,0.25) (2.5,0.75)
}
\otimes
\BigPartition{
\Psingletons 0 to 0.25:1,4
\Psingletons 1 to 0.75:1,4
\Pline (2,0) (3,1)
\Pline (3,0) (2,1)
\Pline (2.75,0.25) (4,0.25)
}
=
\BigPartition{
\Pblock 0 to 0.25:2,3
\Pblock 1 to 0.75:1,2,3
\Psingletons 0 to 0.25:1,4,5,8
\Psingletons 1 to 0.75:5,8
\Pline (2.5,0.25) (2.5,0.75)
\Pline (6,0) (7,1)
\Pline (7,0) (6,1)
\Pline (6.75,0.25) (8,0.25)
}
$$
  * For $p\in\Pscr(k,l)$, $q\in\Pscr(l,m)$ we define their **composition** $qp\in\Pscr(k,m)$ by putting the graphical representation of $q$ below $p$ identifying the lower row of $p$ with the upper row of $q$. The upper row of $p$ now represents the upper row of the composition and the lower row of $q$ represents the lower row of the composition.
$$
\BigPartition{
\Psingletons 0 to 0.25:1,4
\Psingletons 1 to 0.75:1,4
\Pline (2,0) (3,1)
\Pline (3,0) (2,1)
\Pline (2.75,0.25) (4,0.25)
}
\cdot
\BigPartition{
\Pblock 0 to 0.25:2,3
\Pblock 1 to 0.75:1,2,3
\Psingletons 0 to 0.25:1,4
\Pline (2.5,0.25) (2.5,0.75)
}
=
\BigPartition{
\Pblock 0.5 to 0.75:2,3
\Pblock 1.5 to 1.25:1,2,3
\Psingletons  0.5 to  0.75:1,4
\Pline (2.5,0.75) (2.5,1.25)
\Psingletons -0.5 to -0.25:1,4
\Psingletons  0.5 to  0.25:1,4
\Pline (2,-0.5) (3,0.5)
\Pline (3,-0.5) (2,0.5)
\Pline (2.75,-0.25) (4,-0.25)
}
=
\BigPartition{
\Pblock 0 to 0.25:2,3,4
\Pblock 1 to 0.75:1,2,3
\Psingletons 0 to 0.25:1
\Pline (2.5,0.25) (2.5,0.75)
}
$$
  * For $p\in\Pscr(k,l)$ we define its **involution** $p^*\in\Pscr(l,k)$ by reversing its graphical representation with respect to the horizontal axis.
$$
\left(
\BigPartition{
\Pblock 0 to 0.25:2,3
\Pblock 1 to 0.75:1,2,3
\Psingletons 0 to 0.25:1,4
\Pline (2.5,0.25) (2.5,0.75)
}
\right)^*
=
\BigPartition{
\Pblock 1 to 0.75:2,3
\Pblock 0 to 0.25:1,2,3
\Psingletons 1 to 0.75:1,4
\Pline (2.5,0.25) (2.5,0.75)
}
$$


The set of all natural numbers with zero $\N_0$ as a set of objects together with the sets of partitions $\Part_\delta(k,l)$ as sets of morphisms between $k\in\N_0$ and $l\in\N_0$ with respect to those operations form a monoidal involutive category. All objects in the category are self-dual. This category is called the **category of all partitions**.

Any monoidal involutive subcategory with duals $\Cscr$ is called a **category of partitions**. That is, a category of partitions is a collection of subsets $\Cscr(k,l)\subset\Pscr(k,l)$ containing the identity partition $\idpart\in\Cscr(1,1)$ and the pair partition $\pairpart\in\Cscr(0,2)$, which is closed under the category operations.

For given $p_1,\dots,p_n\in\Pscr$, we denote by $\langle p_1,\dots,p_n\rangle$ the smallest linear category of partitions containing $p_1,\dots,p_n$. We say that $p_1,\dots,p_n$ **generate** $\langle p_1,\dots,p_n\rangle$. Note that the pair partition is contained in the category by definition and hence will not be explicitly listed as a generator. Any element in $\langle p_1,\dots,p_n\rangle$ can be obtained from the generators $p_1,\dots,p_n$ and the pair partition $\pairpart$ by performing a finite amount of category operations and linear combinations. 

===== Relation with linear categories =====

Consider a category of partitions $\Cscr$. Put $\Kscr(k,l):=\spanlin\Cscr(k,l)\subset\Part_\delta(k,l)$. Then $\Kscr$ is a [[linear_category_of_partitions|linear category of partitions]]. Moreover, supposing $\delta\neq 0$, if $\Cscr=\langle p_1,\dots,p_n\rangle$, then $\Kscr=\langle p_1,\dots,p_n\rangle_\delta$.

Conversely, a [[linear_category_of_partitions|linear category of partitions]] $\Kscr$ is called **easy** if it is //spanned by partitions//. That is, if there is a collection of sets $\Cscr(k,l)\subset\Pscr(k,l)$ such that $\Kscr(k,l)=\spanlin\Cscr(k,l)$. Then the collection $\Cscr(k,l)$ is a category of partition.

This means that categories of partitions can be understood as an //easy// subclass of linear categories of partitions. Their advantage is that they are much easier to work with. In particular, a complete classification of categories is available, which serves as a source of many examples of linear categories of partitions. Since any linear category of partitions induces a [[compact_matrix_quantum_group|compact matrix quantum group]] through the [[Tannaka–Krein duality|Tannaka–Krein duality]], categories of partitions can also serve as a source of many examples of quantum groups. Quantum groups corresponding to categories of partitions are called **easy**.

===== Classification of categories of partitions =====

In this section, we summarize the classification results for categories of partitions. More information is provided in the separate articles.

==== Non-crossing partitions ====

There are the following seven easy [[Non-crossing category of partitions|non-crossing categories]] of partitions [(ref:BS09)],[(ref:Web13)].
$$NC_2=\langle\rangle\subset\Big\{\begin{matrix}\langle\singleton\otimes\singleton\rangle\subset\langle\Labac\rangle\subset\langle\singleton\rangle\\\langle\fourpart\rangle\subset\langle\fourpart,\singleton\otimes\singleton\rangle\end{matrix}\Big\}\subset\langle\fourpart,\singleton\rangle=NC$$

Here, we denote by $NC$ the [[Category of all non-crossing partitions|category of all non-crossing partitions]]. The smallest category $\langle\rangle$ is  $NC_2$, the [[Temperley–Lieb category|category of non-crossing pairings]].

==== The group categories ====

A category of partition $\Cscr$ is called a **group category** if it contains the **crossing partition** $\crosspart$. It is called a //group category// because the crossing partition corresponds to commutativity relation. So, a quantum group corresponding to a group category is actually a group.

For any group category $\Cscr$ it holds that $\Cscr':=\Cscr\cap NC$ is a non-crossing category of partitions. Conversely, it holds that $\Cscr=\langle\Cscr',\crosspart\rangle$. Thus, all categories with the crossing partition arise by adding the crossing to a non-crossing category. The seven non-crossing categories induce the following six categories with crossing [(ref:BS09)],[(ref:Web13)]

$$\Pscr_2=\langle\crosspart\rangle\subset\Big\{\begin{matrix}\langle\crosspart,\singleton\otimes\singleton\rangle\subset\langle\crosspart,\singleton\rangle\\\langle\crosspart,\fourpart\rangle\subset\langle\crosspart,\fourpart,\singleton\otimes\singleton\rangle\end{matrix}\Big\}\subset\langle\crosspart,\fourpart,\singleton\rangle=\Pscr$$

Here, we denote by $\Pscr_2$ the [[Brauer category|category of all pairings]]. The largest category is of course the [[category_of_all_partitions|category of all partitions]] $\Pscr$.

==== The half-liberated categories ====

A category of partitions $\Cscr$ is called **half-liberated** if $\halflibpart\in\Cscr$, but $\crosspart\not\in\Cscr$. Their classification [(ref:Web13)] consists of the categories $\langle\halflibpart\rangle$, $\langle\halflibpart,\singleton\otimes\singleton\rangle$, $\halflibpart,\fourpart\rangle$ and an infinite series $\langle\halflibpart,\fourpart,h_s\rangle$ for $s\ge 3$. Here, $h_s$ is a partition on $2s$ points consisting of two blocks, where all odd points are in one block and all even points are in the second block (in the [[partition#Word representation|word representation]] $h_s=(\mathsf{ab})^s=\mathsf{ab}\,\mathsf{ab}\cdots\mathsf{ab}$).

==== The hyperoctahedral categories ====

A category of partitions $\Cscr$ is called **hyperoctahedral** if $\fourpart\in\Cscr$ but $\singleton\otimes\singleton\not\in\Cscr$. We have the following classification of hyperoctahedral categories [(ref:RW16)].

If $\Paabaab\not\in\Cscr$, then $\Cscr$ is equal to either $\langle \pi_k\rangle$ or $\langle \pi_l\mid l\in\N\rangle$, where $\pi_k\in\Pscr(0,4k)$ is a partition, whose [[partition#word_representation|word representation]] can be written as
$$\pi_k=\mathsf{a}_1\mathsf{a}_2\cdots\mathsf{a}_k\mathsf{a}_k\cdots\mathsf{a}_2\mathsf{a}_1\mathsf{a}_1\mathsf{a}_2\cdots\mathsf{a}_k\mathsf{a}_k\cdots\mathsf{a}_2\mathsf{a}_1.$$
Note that $\pi_1=\fourpart$ is a non-crossing partition. All the $\pi_k$ for $k>2$ have a crossing and the corresponding categories are pairwise distinct and also different from the above mentioned.

If $\Paabaab\in\Cscr$, then $\Cscr$ is so-called [[Group-theoretical category|group-theoretical category]]. There is a certain normal subgroup $A\subset\Z_2^{*n}$ such that the set of all partitions in $\Cscr$ written in the [[partition#word_representation|word representation]] using the generators of $\Z_2^{*n}$ as the alphabet coincide with $A$ [(ref:RW14)], [(ref:RW15)].

===== Further reading =====

  * Moritz Weber, //Introduction to compact (matrix) quantum groups and Banica–Speicher (easy) quantum groups//, [[https://doi.org/10.1007/s12044-017-0362-3|Proceedings – Mathematical Sciences, Vol. 127, No. 5, pp. 881–933, 2017]]. [[https://www.ias.ac.in/article/fulltext/pmsc/127/05/0881-0933|Full text online.]]

===== References =====

[(ref:BS09>>
title     : Liberation of orthogonal Lie groups
journal   : Advances in Mathematics
volume    : 222
number    : 4
pages     : 1461--1501
year      : 2009
url       : http://dx.doi.org/10.1016/j.aim.2009.06.009
author    : Teodor Banica and Roland Speicher
)]

[(ref:Web13>>
title     : On the classification of easy quantum groups
journal   : Advances in Mathematics
volume    : 245
pages     : 500--533
year      : 2013
url       : http://dx.doi.org/10.1016/j.aim.2013.06.019
author    : Moritz Weber
)]

[(ref:RW14>>
author    : Sven Raum and Moritz Weber
title     : The combinatorics of an algebraic class of easy quantum groups
journal   : Infinite Dimensional Analysis, Quantum Probability and Related Topics
volume    : 17
number    : 03
pages     : 1450016
year      : 2014
url       : http://dx.doi.org/10.1142/S0219025714500167
)]

[(ref:RW15>>
author    : Sven Raum and Moritz Weber
title     : Easy quantum groups and quantum subgroups of a semi-direct product quantum group
journal   : Journal of Noncommutative Geometry
volume    : 9
number    : 4
pages     : 1261--1293
year      : 2015
url       : http://dx.doi.org/10.4171/JNCG/223
)]

[(ref:RW16>>
author    : Sven Raum and Moritz Weber
title     : The Full Classification of Orthogonal Easy Quantum Groups
journal   : Communications in Mathematical Physics
year      : 2016
volume    : 341
number    : 3
pages     : 751--779
url       : http://dx.doi.org/10.1007/s00220-015-2537-z
)]

~~REFNOTES ref ~~