The classification of tensor categories of two-colored noncrossing partitions

Pierre Tarrago, Moritz Weber

Introduction

Before speaking about the main results of this article, let us briefly mention our main application of categories of partitions. In 1987, Woronowicz introduced compact (matrix) quantum groups [Wor87]. These are operator algebraic objects generalizing the notion of compact groups and they are most suitable to describe symmetries arising in the noncommutative framework of operator algebras. By a Tannaka-Krein type result of Woronowicz [Wor88] compact matrix quantum groups are completely determined by their intertwiner spaces. In 2009, Banica and Speicher observed that one can define the above mentioned operations on partitions and that they translate one-to-one to natural operations on the intertwiner spaces via some functor. Thus, any category of partitions gives rise to a compact matrix quantum group by modelling its intertwiner space. This lead them to the definition of orthogonal easy quantum groups [BS09], a quite combinatorial class of quantum groups. One of the nice features of these easy quantum groups is, that many operator algebraic or quantum algebraic properties may be seen already in the underlying combinatorics of partitions, see for instance [FW14], [RW15]. Using our approach involving colors, we may define easy quantum groups also in the unitary case. This is done in a separate article [TW15].

The classification is then summarized in Section 7. While there are only seven categories of one-colored noncrossing partitions [Web13], we obtain ten series of categories in the two-colored case, each indexed by one or two parameters from the natural numbers, plus two additional categories. In this sense, the world of unitary easy quantum groups is way richer than the one of orthogonal easy quantum groups. Note that all categories of one-colored partitions (including possibly crossing ones) have recently been found in [RW13]. In the two-colored case however, little is known and the present article constitutes only the beginning of a longer investigation. At the end of this article, we also cover the case of categories containing the crossing partition $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ$ $\circ$ , see Section 8. This is the analog of the group case in Woronowicz’s theory. Finally, we comment on further aspects and applications of our work in Section 9.

Acknowledgements

We thank Teo Banica, Stephen Curran and Roland Speicher for sending us an unpublished draft [BCS12] of their work on the definition and classification of unitary easy quantum groups. Some parts of this article may be found in their draft, too.

The first author was supported by the Université Franco-Allemande. Both authors were partially funded by the ERC Advanced Grant on Non-Commutative Distributions in Free Probability, held by Roland Speicher.

Categories of two-colored partitions

The basics on non-colored partitions presented in this section are well-known to experts in (orthogonal) easy quantum groups. The main ideas may be found in the initial paper [BS09] on easy quantum groups. However, we need to formulate it for partitions involving a coloring of the points. Attempts in this direction may be found in [FW14], [Fre14a], [Fre14b], [Lem14] or earlier in [BC07] and [Ban08].

In the sequel, the following examples of partitions will play a special role.

It is often convenient to associate words to partitions $p\in P^{\circ\bullet}(0,l)$ having no upper points in the sense that each block $V$ is represented by a unique letter $a,b,c,\ldots$ . Furthermore, we use the notation $a$ and $a^{-1}$ for points having inverse colors but belonging to the same block. As an example, the partition $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet$ $\bullet$ corresponds to the word $aaa^{-1}a^{-1}$ whereas ↑↑ $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet$ $\bullet$ is $abcb^{-1}$ . This representation is not unique since we do not specify whether $a$ is white and $a^{-1}$ is black or vice versa. Also, we sometimes use capital letters $X,Y,Z,\ldots$ in order to denote subwords of a partition seen as a word.

2. Operations on partitions

Let us now turn to operations on the set $P^{\circ\bullet}$ .

The tensor product of two partitions $p\in P^{\circ\bullet}(k,l)$ and $q\in P^{\circ\bullet}(k^{\prime},l^{\prime})$ is the partition $p\otimes q\in P^{\circ\bullet}(k+k^{\prime},l+l^{\prime})$ obtained by horizontal concatenation (writing $p$ and $q$ side by side), i.e. the first $k$ of the $k+k^{\prime}$ upper points are connected by $p$ to the first $l$ of the $l+l^{\prime}$ lower points, whereas $q$ connects the remaining $k^{\prime}$ upper points with the remaining $l^{\prime}$ lower points.

The composition of two partitions $q\in P^{\circ\bullet}(k,l)$ and $p\in P^{\circ\bullet}(l,m)$ is the partition $pq\in P^{\circ\bullet}(k,m)$ obtained by vertical concatenation (writing $p$ below $q$ ): First connect $k$ upper points by $q$ to $l$ middle points and then connect these points by $p$ to $m$ lower points. This yields a partition, connecting $k$ upper points with $m$ lower points. The $l$ middle points are removed.

Note that we can compose two partitions $q\in P^{\circ\bullet}(k,l)$ and $p\in P^{\circ\bullet}(l^{\prime},m)$ only if

the numbers $l$ and $l^{\prime}$ coincide,

the colorings match, i.e. the color of the $j$ -th lower point of $q$ coincides with the color of the $j$ -th upper point of $p$ , for all $1\leq j\leq l$ .

The vertical reflection of a partition $p\in P^{\circ\bullet}(k,l)$ is given by the reflection $R_{v}(p)\in P^{\circ\bullet}(k,l)$ at the vertical axis.

The horizontal reflection of a partition $p\in P^{\circ\bullet}(k,l)$ is given by the reflection $R_{h}(p)\in P^{\circ\bullet}(l,k)$ at the horizontal axis. We also call it the involution of the partition $p$ and denote it by $p^{*}:=R_{h}(p)$ .

The inversion of colors of a partition $p\in P^{\circ\bullet}(k,l)$ is given by the partition $R_{c}(p)\in P^{\circ\bullet}(k,l)$ where all colors of the points are inverted.

We also have a rotation on partitions. Let $p\in P^{\circ\bullet}(k,l)$ be a partition connecting $k$ upper points with $l$ lower points. Shifting the very left upper point to the left of the lower points and inverting its color gives rise to a partition in $P^{\circ\bullet}(k-1,l+1)$ , a rotated version of $p$ . Note that the point still belongs to the same block after rotation. We may also rotate the leftmost lower point to the very left of the upper line (again inverting its color), and we may as well rotate in the right hand side of the lines. In particular, for a partition $p\in P^{\circ\bullet}(0,l)$ , we may rotate the very left point to the very right and vice versa. Such a rotation on one line does not change the colors of the points.

Here are some examples of these operations.

3. Categories of partitions

Let $\mathcal{C}\subseteq P^{\circ\bullet}$ be a category of partitions.

$\mathcal{C}$ is closed under rotation and verticolor reflection.

If $p\in P^{\circ\bullet}(k,l)$ is a partition in $\mathcal{C}$ , we can erase two neighbouring points of $p$ if they have different (!) colors, i.e. if the $j$ -th and the $(j+1)$ -th of the lower points have inverse colors, then the partition $p^{\prime}\in P^{\circ\bullet}(k,l-2)$ is in $\mathcal{C}$ which is obtained from $p$ by first connecting the blocks to which the $j$ -th and the $(j+1)$ -th lower points belong respectively, and then erasing these two points. We may also erase neighbouring points of inverse colors on the upper line.

Let $p\in\mathcal{C}(0,l)$ and $q\in\mathcal{C}(0,m)$ . Every partition obtained from placing $q$ between two legs of $p$ is in $\mathcal{C}$ .

, $\in\mathcal{C}<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\Longrightarrow<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo></mrow><annotation encoding="application/x-tex">=</annotation></semantics></math>=\otimes<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>⊗</mo></mrow><annotation encoding="application/x-tex">\otimes</annotation></semantics></math>⊗\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\in\mathcal{C}$ ∎

We will often refer to “composing a partition $q\in P^{\circ\bullet}(k,l)$ with a partition $p\in P^{\circ\bullet}(n,m)$ ” where $l\geq n$ . By this we mean the composition $(r_{1}\otimes p\otimes r_{2})q$ where $r_{i}\in P^{\circ\bullet}(a_{i},a_{i})$ are suitable tensor products of the identity partitions respecting the coloring of the lower points of $q$ and moreover $a_{1}+n+a_{2}=l$ . In this sense, composing a partition $p\in P^{\circ\bullet}(k,l)$ with $\bullet$ $\circ$ or $\circ$ $\bullet$ yields Lemma 1.1(b).

Tensor product, composition, involution, and the operations of the preceding lemma are called the category operations.

4. Special operations on partitions

The category operations may be performed in any category of partitions. Other procedures are allowed only if certain key partitions are contained in the category.

Let $\mathcal{C}$ be a category of partitions and let $p\in P^{\circ\bullet}(0,l)$ be a partition without upper points.

(d) We argue as in (c), but we may only use $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ$ $\bullet$ and $\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet$ $\circ$ .

(e) Check that $\uparrow$ $\circ$ $\circ$ $\circ$ $\downarrow$ $\circ$ , $\uparrow$ $\bullet$ $\bullet$ $\bullet$ $\downarrow$ $\bullet$ , $\uparrow$ $\circ$ $\bullet$ $\bullet$ $\downarrow$ $\circ$ , $\uparrow$ $\bullet$ $\circ$ $\circ$ $\downarrow$ $\bullet$ etc are in $\mathcal{C}$ using rotation and verticolor reflection.

(f) Use $\uparrow$ $\circ$ $\bullet$ $\circ$ $\downarrow$ $\bullet$ or $\uparrow$ $\bullet$ $\circ$ $\bullet$ $\downarrow$ $\circ$ etc.

Here are some examples concerning the above operations.

$\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\otimes<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>⊗</mo></mrow><annotation encoding="application/x-tex">\otimes</annotation></semantics></math>⊗=<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet$ $\circ$ permutationof colors(a) $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\otimes<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>⊗</mo></mrow><annotation encoding="application/x-tex">\otimes</annotation></semantics></math>⊗=<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet$ $\circ$ disconnectinga point(b) $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\otimes<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>=</mo></mrow><annotation encoding="application/x-tex">=</annotation></semantics></math>=\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ$ connectingblocks(c) $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\otimes<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>⊗</mo></mrow><annotation encoding="application/x-tex">\otimes</annotation></semantics></math>⊗=<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ$ shifting a singletonwith color swapping(f) ∎

We formulated the above lemma only for partitions having no upper points, but the statements may be extended to arbitrary partitions $p\in P^{\circ\bullet}(k,l)$ . We then have to take into account that the colors are inverted whenever they are rotated from the upper line to the lower line or the converse.

5. The non- (or one-) colored case

Let us end this section with a comparison to the case of categories of non-colored partitions, which were studied in [BS09, BCS10, Web13, RW14, RW15] and in other articles and which were completely classified in [RW13]. For the classification in the noncrossing case, see [BS09] and [Web13]. Recall that there are exactly seven categories, given by:

By $P(k,l)$ we denote the set of non-colored partitions where all points have no color. Likewise we use the notations $P$ for all non-colored partitions and $NC$ for all non-colored noncrossing partitions. Categories of non-colored partitions are defined like categories of two-colored partitions when forgetting all colors, see for instance [BS09] or [RW13]. The key link between non-colored categories and two-colored categories is given by the partition $\circ$ $\circ$ as may be seen in the next proposition. Note that $\bullet$ $\circ$ and $\circ$ $\bullet$ are rotated and possibly verticolor reflected versions of $\circ$ $\circ$ . Composing a partition $p$ with these partitions, we can change the colors of the points of $p$ to every possible color pattern. Hence, categories containing $\circ$ $\circ$ are non-colored categories, in this sense.

To be more precise, let $\Psi:P^{\circ\bullet}\to P$ be the map given by forgetting the colors of a two-colored partition. For a set $\mathcal{C}\subseteq P$ , we denote by $\Psi^{-1}(\mathcal{C})\subseteq P^{\circ\bullet}$ its preimage under $\Psi$ .

Let $\mathcal{C}\subseteq P$ be a category of non-colored partitions. Then $\Psi^{-1}(\mathcal{C})\subseteq P^{\circ\bullet}$ is a category of two-colored partitions containing the unicolored pair partition $\circ$ $\circ$ (or equivalently $\bullet$ $\bullet$ ).

Let $\mathcal{C}\subseteq P^{\circ\bullet}$ be a category of two-colored partitions containing the unicolored pair partition $\circ$ $\circ$ (or equivalently $\bullet$ $\bullet$ ). Then $\Psi(\mathcal{C})\subseteq P$ is a category of non-colored partitions and $\Psi^{-1}(\Psi(\mathcal{C}))=\mathcal{C}$ .

Hence, there is a one-to-one correspondence between categories of non-colored partitions and categories of two-colored partitions containing $\circ$ $\circ$ .

(b) It is easy to see that $\Psi(\mathcal{C})$ is closed under tensor product and involution and that it contains the pair partition and the identity partition $|$ . The composition is a bit more subtle. If $p,q\in\Psi(\mathcal{C})$ , their composition is in $\Psi(\mathcal{C})$ only if we can lift $p$ and $q$ to partitions in $\mathcal{C}$ whose color patterns allow the composition in $P^{\circ\bullet}$ . But since $\bullet$ $\circ$ and $\circ$ $\bullet$ are in $\mathcal{C}$ (by rotation), we can do so: If $p\in\Psi(\mathcal{C})$ , there is a partition $p_{0}\in\mathcal{C}$ such that $\Psi(p_{0})=p$ . Composing it with tensor products of $\bullet$ $\circ$ and $\circ$ $\bullet$ , we may assume that all points of $p_{0}$ are white. Now, $\Psi(\mathcal{C})$ is closed under composition since $\mathcal{C}$ is. Similarly, we prove $\Psi^{-1}(\Psi(\mathcal{C}))\subseteq\mathcal{C}$ using $\bullet$ $\circ$ and $\circ$ $\bullet$ ; the converse direction is trivial. ∎

Dividing the categories into cases

The classification of categories of noncrossing partitions is given by a detailed case study which we will now prepare.

The first division into cases is given by the sizes of blocks. The next lemma is formulated for arbitrary categories of partitions (not necessarily noncrossing ones).

Let $\mathcal{C}\subseteq P^{\circ\bullet}$ be a category of partitions.

(b) Let $p\in\mathcal{C}$ be a partition containing a block of size at least three. By rotation, it is of the form $p=a^{\varepsilon_{1}}X_{1}a^{\varepsilon_{2}}X_{2}a^{\varepsilon_{3}}X_{3}$ with no upper points, where the points $a^{\varepsilon_{i}}$ belong to the same block, and $\varepsilon_{i}\in\{1,-1\}$ depending on the color. The subwords $X_{1},X_{2}$ and $X_{3}$ are possibly connected to the block on the $a^{\varepsilon_{i}}$ . By verticolor reflection, we infer that the following partition is in $\mathcal{C}$ .

Let $\mathcal{C}\subseteq P^{\circ\bullet}$ be a category of partitions. We say that:

The coice of the letters $\mathcal{O},\mathcal{B},\mathcal{H},\mathcal{S}$ comes from the non-colored situation, [Web13].

2. Global and local colorization

A category of partitions $\mathcal{C}\subseteq P^{\circ\bullet}$ is

3. The global parameter k(𝒞)𝑘𝒞k(\mathcal{C})

By Lemma 1.3, we may permute the colors of the points of partitions in globally colorized categories. Hence the coloring of partitions turns out to be of a global nature – the difference between the number of white and black points is the only number that matters for the coloring of a partition in such categories.

Denote by $c_{\circ}(p)$ the sum of the number of white points on the lower line of $p$ and the number of black points on the upper line.

Denote by $c_{\bullet}(p)$ the sum of the number of black points on the lower line of $p$ and the number of white points on the upper line.

We will mainly consider partitions $p\in P^{\circ\bullet}(0,l)$ with no upper points. In this case $c_{\circ}$ is counting the white points whereas $c_{\bullet}$ is counting the black points of a partition. Recall that rotating black points from the upper line to the lower line turns them into white points.

Let $\mathcal{C}$ be a category of partitions. We set $k(\mathcal{C})$ as the minimum of all numbers $c(p)$ such that $c(p)>0$ and $p\in\mathcal{C}$ , if such a partition exists in $\mathcal{C}$ . Otherwise $k(\mathcal{C}):=0$ . The parameter $k(\mathcal{C})$ is called the degree of reflection of $\mathcal{C}$ . It is the global parameter of $\mathcal{C}$ .

$c(p^{\prime})=c(p)$ , if $p^{\prime}$ is obtained from $p$ by rotation.

From the definition it is clear that (a), (c), (d) and (e) hold. To see the invariance under composition, let $w_{1}$ be the number of upper white points of $q$ , and $b_{1}$ be the number of upper black points. Let $w_{2}$ be the number of lower white points of $q$ and likewise $b_{2}$ for the black points. Since $p$ and $q$ are composable, the numbers $w_{2}$ and $b_{2}$ also count the number of upper white and upper black points of $p$ , respectively. Finally, let $w_{3}$ and $b_{3}$ be the number of lower white and black points of $p$ respectively. We thus have:

The global parameter $k(\mathcal{C})$ gives rise to a complete description of all possible numbers $c(p)$ of a category $\mathcal{C}$ .

$\ldots$ $\ldots$ or $p=\quad\ldots\quad\circ\;p_{1}\circ\quad\ldots<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>…</mo></mrow><annotation encoding="application/x-tex">\ldots</annotation></semantics></math>…\ldots$ By rotation, we can reduce it to the following situation.

Let $p\in NC^{\circ\bullet}(0,l)$ be a partition with no upper points. Assume that $p$ can be decomposed as $p=p_{1}\otimes p_{2}$ where $p_{1}\neq\emptyset$ , the partition $p_{2}$ has at least two points and the first and the last point of $p_{2}$ belong to the same block. Then we say that $p=p_{1}\otimes p_{2}$ is in nest decomposed form.

The next lemma is of quite technical nature, but it will be needed in this subsection as well as in the remainder of this article several times.

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions.

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ and $d=d(\mathcal{C})$ .

↑⊗dm↑⊗dm⊗r-1⊗r-1 $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\bullet$ $\bullet$ ↑↑ $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\in\mathcal{C}$ Furthermore, the following partition is in $\mathcal{C}$ since it is a rotated version of ↑⊗r+1↑⊗r-1 $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\bullet$ :

In the globally colorized case, the local parameters are almost trivial as can be seen in the next lemma.

The second assertion follows from Lemma 2.14(b). ∎

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ and put $d=d(\mathcal{C})$ , $k=k(\mathcal{C})$ .

(b) We consider $p_{1}\otimes p_{2}\in\mathcal{C}$ with $c(p_{1})=d$ as in (a), but by Lemma 1.3(c) we may assume that $p_{1}$ consists only of one block. The rest of the proof is similar to (a).

5. Summary of the strategy for the classification

We now have all tools at hand for the classification of categories $\mathcal{C}\subseteq NC^{\circ\bullet}$ of noncrossing partitions. The general strategy is as follows.

We study the cases $\mathcal{O},\mathcal{H},\mathcal{S}$ and $\mathcal{B}$ (see Definition 2.2) step by step subdividing them again into the local and the global colorization (see Definition 2.3) respectively.

We then find characteristic sample partitions which somehow represent these parameters.

Next, we isolate sets of partitions $M$ depending on the possible values of the parameters and we prove $M\subseteq\langle p_{1},\ldots,p_{n}\rangle$ , where $p_{1},\ldots,p_{n}$ are the sample partitions.

Case 𝒪𝒪\mathcal{O}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{O}$ .

If $\mathcal{C}$ is locally colorized, then $d(\mathcal{C})=k(\mathcal{C})=0$ and we have:

(b) By Lemma 2.13(d), we have $d(\mathcal{C})=k(\mathcal{C})=0$ . Lemma 2.14(d) completes the proof. ∎

2. Finding partitions realizing the parameters

3. Description of natural categories in case 𝒪𝒪\mathcal{O}

We have the following natural categories of partitions in case $\mathcal{O}$ .

The category ${\mathcal{O}}_{\textnormal{loc}}:=\langle\emptyset\rangle$ consists of all noncrossing pair partitions such that each block connects a white point with a black point, when the partition is rotated such that it has no upper points.

In particular, all these categories are pairwise different.

(a) We may construct all partitions $p$ from the assertion using $\bullet$ $\circ$ , $\circ$ $\bullet$ and the category operations due to a simple inductive argument: Assume that $p$ has $m+1$ blocks. Since $p$ is noncrossing, it contains at least one block $\bullet$ $\circ$ or $\circ$ $\bullet$ on two consecutive points. Removing it yields a partition which is in $\langle\emptyset\rangle$ by induction hypothesis. Putting it back (Lemma 1.1(d)), we infer $p\in\langle\emptyset\rangle$ . Conversely, the set of all noncrossing pair partitions with the block rule of the assertion forms a category of partitions, hence containing $\langle\emptyset\rangle$ .

4. Classification in the case 𝒪𝒪\mathcal{O}

We are now ready to prove our first classification theorem.

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{O}$ . Then $\mathcal{C}$ coincides with one of the following categories.

If $\mathcal{C}$ is locally colorized, then $\mathcal{C}={\mathcal{O}}_{\textnormal{loc}}=\langle\emptyset\rangle$ .

Case ℋℋ\mathcal{H}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{H}$ .

If $\mathcal{C}$ is locally colorized, then

either $k(\mathcal{C})=d(\mathcal{C})=0$ and we have:

2. Finding partitions realizing the parameters

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{H}$ .

If $k=k(\mathcal{C})\neq 0$ , then $b_{k}\in\mathcal{C}$ .

3. Description of natural categories

We have the following natural categories in case $\mathcal{H}$ .

4. Classification in the case ℋℋ\mathcal{H}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{H}$ . Then $\mathcal{C}$ coincides with one of the following categories.

(ii) Let $\mathcal{C}$ be locally colorized and let $k:=k(\mathcal{C})$ and $d:=d(\mathcal{C})$ .

Case 𝒮𝒮\mathcal{S}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{S}$ .

(a) By Lemma 1.3, we may disconnect the white points from $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ$ $\bullet$ .

2. Finding partitions realizing the parameters

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category in case $\mathcal{S}$ .

3. Description of natural categories

if $p_{1}\otimes p_{2}$ is any rotated version of $p$ in nest decomposed form such that the first and the last point of $p_{2}$

Case 2. Let $m(p)=1$ . Using rotation, $p$ is of the following form:

Case 3. Let $m(p)>1$ . By rotation, $p$ can be brought in nest decomposed form $p=p_{1}\otimes p_{2}$ such that $m(p_{2})=1$ . Such a decomposition exists since $p$ is noncrossing.

4. Classification in the case 𝒮𝒮\mathcal{S}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{S}$ . Then $\mathcal{C}$ coincides with one of the following categories.

Case ℬℬ\mathcal{B}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{B}$ .

If $\mathcal{C}$ is globally colorized, then the cases $d(\mathcal{C})=1$ and $d(\mathcal{C})=2$ can occur.

If $\mathcal{C}$ is locally colorized, then

(a) This follows directly from Lemma 2.15.

Finally, let $r\neq 0$ . We now prove $r=\frac{d}{2}$ . The following two partitions are in $\mathcal{C}$ .

↑⊗r+1↑⊗r-1 $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\in\mathcal{C}$ and↑⊗r+1↑⊗r-1 $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\in\mathcal{C}$ Forming the tensor product of these two partitions and composing it with $\circ$ $\bullet$ (Remark 1.2) we infer:

2. Finding partitions realizing the parameters

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category in case $\mathcal{B}$ .

3. Description of natural categories

We have the following natural categories in case $\mathcal{B}$ .

the blocks of size two connect a black point and a white point,

the number of black singletons and the number of white singletons between two legs of every pair coincide, and on the global level, too.

if $p_{1}\otimes p_{2}$ is any rotated version of $p$ in nest decomposed form such that the first and the last point of $p_{2}$

Case 2. Let $m=1$ . Up to rotation, $p$ is of the form $p=p_{1}\otimes a^{\varepsilon_{1}}p_{2}^{0}a^{\varepsilon_{2}}$ where $a^{\varepsilon_{1}}$ and $a^{\varepsilon_{2}}$ form a pair block, and $p_{1}$ and $p_{2}^{0}$ consist only of singletons respectively.

4. Classification in the case ℬℬ\mathcal{B}

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a category of noncrossing partitions in case $\mathcal{B}$ . Then $\mathcal{C}$ coincides with one of the following categories.

If $\mathcal{C}$ is globally colorized and

If $\mathcal{C}$ is locally colorized and

Main result: Summary of the noncrossing case

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a globally colorized category of noncrossing partitions. Then it coincides with one of the following categories.

Let $\mathcal{C}\subseteq NC^{\circ\bullet}$ be a locally colorized category of noncrossing partitions.Then it coincides with one of the following categories.

${\mathcal{O}}_{\textnormal{loc}}=\langle\emptyset\rangle$

Here is a graphical overview of all categories of two-colored noncrossing partitions. The single framed categories are the locally colorized ones whose inclusions are indicated by single dashed lines (inclusions from top to bottom and from right to left, for fixed parameters $k$ and $d$ ). Constraints for inclusions are marked in brackets. The double framed categories are the globally colorized ones with inclusion pattern according to the double dahed lines. The locally colorized categories are contained in the globally colorized ones according to the diagonal chain lines. In our graphic, we also included a cross marking the areas of the cases $\mathcal{B}$ , $\mathcal{O}$ , $\mathcal{S}$ and $\mathcal{H}$ .

${\mathcal{H}}_{\textnormal{glob}}(k)={\mathcal{H}}_{\textnormal{loc}}(k,2)$ and ${\mathcal{H}}_{\textnormal{glob}}(2m+1)={\mathcal{S}}_{\textnormal{glob}}(2m+1)$

${\mathcal{S}}_{\textnormal{glob}}(k)={\mathcal{S}}_{\textnormal{loc}}(k,1)={\mathcal{H}}_{\textnormal{loc}}(k,1)$

${\mathcal{B}}_{\textnormal{glob}}(k)={\mathcal{B}^{\prime}}_{\textnormal{loc}}(k,2,1)$ and ${\mathcal{B}}_{\textnormal{glob}}(2m+1)={\mathcal{B}^{\prime}}_{\textnormal{glob}}(2m+1)$

${\mathcal{B}^{\prime}}_{\textnormal{glob}}(k)={\mathcal{B}^{\prime}}_{\textnormal{loc}}(k,1,0)={\mathcal{B}^{\prime}}_{\textnormal{loc}}(k,1,1)$

In an unpublished draft, Banica, Curran and Speicher [BCS12] already found several of the above categories. We thank them for sending the draft to us.

The group case

For categories $\mathcal{C}\subseteq P^{\circ\bullet}$ of two-colored partitions, there are two natural extreme cases. The first is the one of noncrossing partitions, completely classified in the preceding sections. The second is the one containing the crossing partitions $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ$ $\circ$ , $\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\bullet$ , $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\circ$ and $\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ$ $\bullet$ , which allow us to permute the points of a partition in an arbitrary way (without changing their colors). It is easy to see that one of these four partitions is in a category if and only if all are (by verticolor reflection and rotation).

A category of two colored partitions $\mathcal{C}$ is in the group case if one (and hence all) of the partitions $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ$ $\circ$ , $\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\bullet$ , $\bullet<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∘</mo></mrow><annotation encoding="application/x-tex">\circ</annotation></semantics></math>∘\circ$ $\bullet$ and $\circ<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>∙</mo></mrow><annotation encoding="application/x-tex">\bullet</annotation></semantics></math>∙\bullet$ $\circ$ is in $\mathcal{C}$ .

The name “group case” refers to the situation when a quantum group is associated to a category of partitions (see [TW15]). If $\mathcal{C}$ is in the group case, the associated quantum group is in fact a group.

The classification of all categories in the group case follows directly from the classification of all categories of noncrossing partitions and the following lemma.

Let $\mathcal{C}$ and $\mathcal{D}$ be categories of two-colored partitions.

Then $\mathcal{C}\cap\mathcal{D}$ is again a category of partitions.

(a) This follows directly from the definition of a category.

The categories in the group case are the following.

Concluding remarks

In [TW15], we define unitary easy quantum groups using categories of two-colored partitions. The first step is to associate a universal $C^{*}$ -algebra to a category of partitions by assigning certain algebraic relations to any partition. This $C^{*}$ -algebra can then be endowed with a comultiplication turning it into a compact matrix quantum group in the sense of Woronowicz [Wor87]. Another way of obtaining this quantum group is to turn the category of partitions into a concrete monoidal $W^{*}$ -category in the sense of Woronowicz [Wor88]. Using his Tannaka-Krein result [Wor88], we thus obtain the quantum group via its intertwiner spaces. Quantum groups obtained this way are called unitary easy quantum groups, extending the definition of Banica and Speicher’s orthogonal easy quantum groups [BS09]. If a category consists only of noncrossing partitions, we call the associated quantum group a free easy quantum group. See [TW15] for remarks on the use of easy quantum groups for the theory of compact matrix quantum groups, for free probability and for other links.

2. Open problems in the classification of categories of partitions

3. Using more colors

Once the step from non-colored partitions to colored partitions is done, the question is: why only two colors? From the combinatorial point of view, it is straightforward to define categories of partitions having $n$ colors and $n$ inverse colors (thus, our two-colored partitions would be the case $n=1$ ). Such partitions appear for instance in Freslon’s work on partition quantum groups [Fre14b]. It would be nice to see if we again obtain a much wider variety of noncrossing categories, when passing from $n=1$ to $n>1$ .

Introduction

Acknowledgements

Categories of two-colored partitions

2. Operations on partitions

3. Categories of partitions

4. Special operations on partitions

5. The non- (or one-) colored case

Dividing the categories into cases

2. Global and local colorization

3. The global parameter k​(𝒞)𝑘𝒞k(\mathcal{C})

5. Summary of the strategy for the classification

Case 𝒪𝒪\mathcal{O}

2. Finding partitions realizing the parameters

3. Description of natural categories in case 𝒪𝒪\mathcal{O}

4. Classification in the case 𝒪𝒪\mathcal{O}

Case ℋℋ\mathcal{H}

2. Finding partitions realizing the parameters

3. Description of natural categories

4. Classification in the case ℋℋ\mathcal{H}

Case 𝒮𝒮\mathcal{S}

2. Finding partitions realizing the parameters

3. Description of natural categories

4. Classification in the case 𝒮𝒮\mathcal{S}

Case ℬℬ\mathcal{B}

2. Finding partitions realizing the parameters

3. Description of natural categories

4. Classification in the case ℬℬ\mathcal{B}

Main result: Summary of the noncrossing case

The group case

Concluding remarks

2. Open problems in the classification of categories of partitions

3. Using more colors

References

3. The global parameter k(𝒞)𝑘𝒞k(\mathcal{C})