partition algebra

{{Short description|Algebraic structure}}

The partition algebra is an associative algebra with a basis of set-partition diagrams and multiplication given by diagram concatenation. Its subalgebras include diagram algebras such as the Brauer algebra, the Temperley–Lieb algebra, or the group algebra of the symmetric group. Representations of the partition algebra are built from sets of diagrams and from representations of the symmetric group.

Definition

= Diagrams =

A partition of 2k elements labelled 1,\bar 1, 2,\bar 2,\dots, k,\bar k is represented as a diagram, with lines connecting elements in the same subset. In the following example, the subset \{\bar 1, \bar 4,\bar 5, 6\} gives rise to the lines \bar 1 - \bar 4, \bar 4 -\bar 5, \bar 5 - 6, and could equivalently be represented by the lines \bar 1- 6, \bar 4 - 6, \bar 5 - 6, \bar 1 - \bar 5 (for instance).

Diagram representation of a partition of 14 elements

For n\in \mathbb{C} and k\in \mathbb{N}^*, the partition algebra P_k(n) is defined by a \mathbb{C}-basis made of partitions, and a multiplication given by diagram concatenation. The concatenated diagram comes with a factor n^D, where D is the number of connected components that are disconnected from the top and bottom elements.

File:Partition concatenation.svg

= Generators and relations =

The partition algebra P_k(n) is generated by 3k-2 elements of the type

File:Partition generators.svg

These generators obey relations that include

:

s_i^2 = 1 \quad , \quad s_is_{i+1}s_i = s_{i+1}s_is_{i+1} \quad, \quad p_i^2 = np_i \quad , \quad b_i^2= b_i \quad , \quad p_i b_i p_i = p_i

Other elements that are useful for generating subalgebras include

File:Partition subgenerators.svg

In terms of the original generators, these elements are

: e_i = b_ip_ip_{i+1}b_i \quad , \quad l_i = s_ip_i \quad , \quad r_i=p_is_i

= Properties =

The partition algebra P_k(n) is an associative algebra. It has a multiplicative identity

File:Partition identity.svg

The partition algebra P_k(n) is semisimple for n\in\mathbb{C} - \{0,1,\dots, 2k-2\}. For any two n,n' in this set, the algebras P_k(n) and P_k(n') are isomorphic.

The partition algebra is finite-dimensional, with \dim P_k(n) = B_{2k} (a Bell number).

Subalgebras

= Eight subalgebras =

Subalgebras of the partition algebra can be defined by the following properties:

  • Whether they are planar i.e. whether lines may cross in diagrams.
  • Whether subsets are allowed to have any size 1,2,\dots,2k, or size 1,2, or only size 2.
  • Whether we allow top-top and bottom-bottom lines, or only top-bottom lines. In the latter case, the parameter n is absent, or can be eliminated by p_i\to \frac{1}{n}p_i.

Combining these properties gives rise to 8 nontrivial subalgebras, in addition to the partition algebra itself:

class="wikitable" ; text-align:center;"
Notation

! Name

! Generators

! Dimension

! Example

P_k(n)

| Partition

| s_i,p_i,b_i

| B_{2k}

| File:Partition ex P.svg

PP_k(n)

| Planar partition

| p_i, b_i

| \frac{1}{2k+1}\binom{4k}{2k}

| File:Partition ex PP.svg

RB_k(n)

| Rook Brauer

| s_i, e_i, p_i

| \sum_{\ell=0}^k \binom{2k}{2\ell} (2\ell-1)!!

| File:Partition ex RB.svg

M_k(n)

| Motzkin

| e_i, l_i, r_i

| \sum_{\ell=0}^k \frac{1}{\ell+1} \binom{2\ell}{\ell} \binom{2k}{2\ell}

| File:Partition ex M.svg

B_k(n)

| Brauer

| s_i, e_i

| (2k-1)!!

| File:Partition ex B.svg

TL_k(n)

| Temperley–Lieb

| e_i

| \frac{1}{k+1} \binom{2k}{k}

| File:Partition ex TL.svg

R_k

| Rook

| s_i, p_i

| \sum_{\ell=0}^k \binom{k}{\ell}^2 \ell!

| File:Partition ex R.svg

PR_k

| Planar rook

| l_i, r_i

| \binom{2k}{k}

| File:Partition ex PR.svg

\mathbb{C} S_k

| Symmetric group

| s_i

| k!

| File:Partition ex S.svg

The symmetric group algebra \mathbb{C} S_k is the group ring of the symmetric group S_k over \mathbb{C}. The Motzkin algebra is sometimes called the dilute Temperley–Lieb algebra in the physics literature.

= Properties =

The listed subalgebras are semisimple for n\in\mathbb{C} - \{0,1,\dots, 2k-2\}.

Inclusions of planar into non-planar algebras:

:

PP_k(n) \subset P_k(n) \quad , \quad M_k(n) \subset RB_k(n) \quad ,\quad TL_k(n)\subset B_k(n) \quad, \quad PR_k \subset R_k

Inclusions from constraints on subset size:

:

B_k(n) \subset RB_k(n) \subset P_k(n) \quad ,\quad TL_k(n) \subset M_k(n) \subset PP_k(n) \quad , \quad

\mathbb{C}S_k \subset R_k

Inclusions from allowing top-top and bottom-bottom lines:

:

R_k \subset RB_k(n) \quad , \quad PR_k\subset M_k(n) \quad ,\quad \mathbb{C}S_k \subset B_k(n)

We have the isomorphism:

:

PP_k(n^2) \cong TL_{2k}(n) \quad , \quad \left\{\begin{array}{l} p_i \mapsto n e_{2i-1} \\ b_i \mapsto \frac{1}{n} e_{2i} \end{array}\right.

= More subalgebras =

In addition to the eight subalgebras described above, other subalgebras have been defined:

  • The totally propagating partition subalgebra \text{prop}P_k is generated by diagrams whose blocks all propagate, i.e. partitions whose subsets all contain top and bottom elements. These diagrams from the dual symmetric inverse monoid, which is generated by s_i, b_ip_{i+1}b_{i+1}.
  • The quasi-partition algebra QP_k(n) is generated by subsets of size at least two. Its generators are s_i,b_i,e_i and its dimension is 1+\sum_{j=1}^{2k} (-1)^{j-1} B_{2k-j}.
  • The uniform block permutation algebra U_k is generated by subsets with as many top elements as bottom elements. It is generated by s_i, b_i.

An algebra with a half-integer index k+\frac12 is defined from partitions of 2k+2 elements by requiring that k+1 and \overline{k+1} are in the same subset. For example, P_{k+\frac12} is generated by s_{i\leq k-1},b_{i\leq k},p_{i\leq k} so that P_k\subset P_{k+\frac12}\subset P_{k+1}, and \dim P_{k+\frac12} =B_{2k+1}.

Periodic subalgebras are generated by diagrams that can be drawn on an annulus without line crossings. Such subalgebras include a translation element u=File:Partition translation.svg such that u^k=1. The translation element and its powers are the only combinations of s_i that belong to periodic subalgebras.

Representations

= Structure =

For an integer 0\leq \ell \leq k, let D_\ell be the set of partitions of k+\ell elements 1,2,\dots, k (bottom) and \bar 1,\bar 2,\dots,\bar \ell (top), such that no two top elements are in the same subset, and no top element is alone. Such partitions are represented by diagrams with no top-top lines, with at least one line for each top element. For example, in the case k=12, \ell = 5:

Example of a state in a representation of the partition algebra

Partition diagrams act on D_\ell from the bottom, while the symmetric group S_\ell acts from the top. For any Specht module V_\lambda of S_\ell (with therefore |\lambda|=\ell), we define the representation of P_k(n)

:

\mathcal{P}_\lambda = \mathbb{C} D_

\lambda
\otimes_{\mathbb{C} S_
\lambda
} V_\lambda\ .

The dimension of this representation is

:

\dim\mathcal{P}_\lambda = f_\lambda \sum_{\ell = |\lambda|}^k \left\{ {k\atop \ell} \right\} \binom{\ell}

\lambda
\ ,

where \left\{ {k\atop \ell} \right\} is a Stirling number of the second kind, \binom{\ell}

\lambda
is a binomial coefficient, and f_\lambda = \dim V_\lambda is given by the hook length formula.

A basis of \mathcal{P}_\lambda can be described combinatorially in terms of set-partition tableaux: Young tableaux whose boxes are filled with the blocks of a set partition.

Assuming that P_k(n) is semisimple, the representation \mathcal{P}_\lambda is irreducible, and the

set of irreducible finite-dimensional representations of the partition algebra is

:

\text{Irrep}\left(P_k(n)\right) = \left\{ \mathcal{P}_\lambda \right\}_{0\leq |\lambda|\leq k}\ .

= Representations of subalgebras =

Representations of non-planar subalgebras have similar structures as representations of the partition algebra. For example, the Brauer-Specht modules of the Brauer algebra are built from Specht modules, and certain sets of partitions.

In the case of the planar subalgebras, planarity prevents nontrivial permutations, and Specht modules do not appear. For example, a standard module of the Temperley–Lieb algebra is parametrized by an integer 0\leq \ell\leq k with \ell\equiv k\bmod 2, and a basis is simply given by a set of partitions.

The following table lists the irreducible representations of the partition algebra and eight subalgebras.

class="wikitable" ; text-align:center;"
Algebra

! Parameter

! Conditions

! Dimension

P_k(n)

| \lambda

| 0\leq |\lambda|\leq k

| f_\lambda \sum_{\ell = |\lambda

^k \left\{ {k\atop \ell} \right\} \binom{\ell}
\lambda

|-

| PP_k(n)

| \ell

| 0\leq \ell\leq k

| \binom{2k}{k+\ell}-\binom{2k}{k+\ell+1}

|-

| RB_k(n)

| \lambda

| 0\leq |\lambda|\leq k

| f_\lambda \binom{k}

\lambda
\sum_{m=0}^{\left\lfloor\frac{k-|\lambda|}{2}\right\rfloor} \binom{k-|\lambda|}{2m} (2m-1)!!

|-

| M_k(n)

| \ell

| 0\leq \ell\leq k

| \sum_{m=0}^{\left\lfloor\frac{k-\ell}{2}\right\rfloor} \binom{k}{\ell+2m} \left\{\binom{\ell+2m}{m}-\binom{\ell+2m}{m-1}\right\}

|-

| B_k(n)

| \lambda

| \begin{array}{c} 0\leq |\lambda|\leq k \\ |\lambda|\equiv k\bmod 2\end{array}

| f_\lambda \binom{k}

\lambda
(k-|\lambda|-1)!!

|-

| TL_k(n)

| \ell

| \begin{array}{c} 0\leq \ell\leq k \\ \ell\equiv k\bmod 2\end{array}

| \binom{k}{\frac{k+\ell}{2}} -\binom{k}{\frac{k+\ell+2}{2}}

|-

| R_k

| \lambda

| 0\leq |\lambda|\leq k

| f_\lambda \binom{k}

\lambda

|-

| PR_k

| \ell

| 0\leq \ell\leq k

| \binom{k}{\ell}

|-

| \mathbb{C} S_k

| \lambda

| |\lambda|=k

| f_\lambda

|}

The irreducible representations of \text{prop}P_k are indexed by partitions such that 0<|\lambda|\leq k and their dimensions are f_\lambda \left\{ {k\atop |\lambda|} \right\}. The irreducible representations of QP_k are indexed by partitions such that 0\leq|\lambda|\leq k. The irreducible representations of U_k are indexed by sequences of partitions.

Schur-Weyl duality

Assume n\in \mathbb{N}^*.

For V a n-dimensional vector space with basis v_1,\dots, v_n, there is a natural action of the partition algebra P_k(n) on the vector space V^{\otimes k}. This action is defined by the matrix elements of a partition \{1,\bar 1, 2,\bar 2,\dots, k,\bar k\}=\sqcup_h E_h in the basis (v_{j_1}\otimes \cdots \otimes v_{j_k}):

:

\left(\sqcup_h E_h\right)_{j_1,j_2,\dots ,j_k}^{j_{\bar 1}, j_{\bar 2},\dots ,j_{\bar k}} = \mathbf{1}_{r,s\in E_h\implies j_r=j_s} \ .

This matrix element is one if all indices corresponding to any given partition subset coincide, and zero otherwise. For example, the action of a Temperley–Lieb generator is

:

e_i \left(v_{j_1}\otimes \cdots \otimes v_{j_i}\otimes v_{j_{i+1}}\otimes \cdots \otimes v_{j_k}\right)

= \delta_{j_i,j_{i+1}}\sum_{j=1}^n v_{j_1}\otimes \cdots \otimes v_{j}\otimes v_{j}\otimes \cdots \otimes v_{j_k}\ .

= Duality between the partition algebra and the symmetric group =

Let n\geq 2k be integer.

Let us take V to be the natural permutation representation of the symmetric group S_n. This n-dimensional representation is a sum of two irreducible representations: the standard and trivial representations, V=[n-1,1]\oplus [n].

Then the partition algebra P_k(n) is the centralizer of the action of S_n on the tensor product space V^{\otimes k},

:

P_k(n) \cong \text{End}_{S_n}\left(V^{\otimes k}\right)\ .

Moreover, as a bimodule over P_k(n)\times S_n, the tensor product space decomposes into irreducible representations as

:

V^{\otimes k} = \bigoplus_{0\leq |\lambda|\leq k} \mathcal{P}_\lambda \otimes V_{[n-|\lambda|,\lambda]}\ ,

where [n-|\lambda|,\lambda] is a Young diagram of size n built by adding a first row to \lambda, and V_{[n-|\lambda|,\lambda]} is the corresponding Specht module of S_n.

= Dualities involving subalgebras =

The duality between the symmetric group and the partition algebra generalizes the original Schur-Weyl duality between the general linear group and the symmetric group. There are other generalizations. In the relevant tensor product spaces, we write V_n for an irreducible n-dimensional representation of the first group or algebra:

class="wikitable" ; text-align:center;"
Tensor product space

! Group or algebra

! Dual algebra or group

! Comments

\left(V_{n-1}\oplus V_1\right)^{\otimes k}

| S_n

| P_k(n)

| The duality for the full partition algebra

\left(V_{n-2}\oplus V_1\oplus V_1\right)^{\otimes k}

| S_{n-1}

| P_{k+\frac12}(n)

| Case of a partition algebra with a half-integer index

V_n^{\otimes k}

| GL_n(\mathbb{C})

| S_k

| The original Schur-Weyl duality

V_n^{\otimes k}

| O(n)

| B_k(n)

| Duality between the orthogonal group and the Brauer algebra

\left(V_n\oplus V_1\right)^{\otimes k}

| O(n)

| RB_k(n+1)

| Duality between the orthogonal group and the rook Brauer algebra

V_n^{\otimes k}

| R_n

| \text{prop}P_k

| Duality between the rook algebra and the totally propagating partition algebra

V_2^{\otimes k}

| gl(1|1)

| PR_{k-1}

| Duality between a Lie superalgebra and the planar rook algebra

V_{n-1}^{\otimes k}

| S_n

| QP_k(n)

| Duality between the symmetric group and the quasi-partition algebra

V_n^{\otimes r} \otimes \left(V_n^*\right)^{\otimes s}

| GL_n(\mathbb{C})

| B_{r,s}(n)

| Duality involving the walled Brauer algebra.

References

{{Reflist|refs=

{{cite journal | last1=Jacobsen | first1=Jesper Lykke | last2=Ribault | first2=Sylvain | last3=Saleur | first3=Hubert | title=Spaces of states of the two-dimensional O(n) and Potts models | year=2022 | arxiv=2208.14298 | page=}}

{{Cite arXiv| last1=Cox | first1=Anton | last2=Visscher | first2=De | last3=Doty | first3=Stephen | last4=Martin | first4=Paul | title=On the blocks of the walled Brauer algebra | date=2007-09-06 | class=math.RT | eprint=0709.0851v1 }}

{{cite arXiv | last=Maltcev | first=Victor | title=On a new approach to the dual symmetric inverse monoid I*X | date=2007-03-16 | eprint=math/0703478v1 }}

{{cite arXiv | last1=Orellana | first1=Rosa | last2=Saliola | first2=Franco | last3=Schilling | first3=Anne | last4=Zabrocki | first4=Mike | title=Plethysm and the algebra of uniform block permutations | date=2021-12-27 | class=math.CO | eprint=2112.13909v1 }}

{{Cite journal |last1=Daugherty |first1=Zajj |last2=Orellana |first2=Rosa |date=2014 |title=The quasi-partition algebra |url=https://linkinghub.elsevier.com/retrieve/pii/S0021869314000477 |journal=Journal of Algebra |language=en |volume=404 |pages=124–151 |doi=10.1016/j.jalgebra.2013.11.028|arxiv=1212.2596v1|s2cid=117848394 }}

{{Cite journal |last1=Benkart |first1=Georgia |last2=Moon |first2=Dongho |date=2013-05-28 |title=Planar Rook Algebras and Tensor Representations of 𝔤𝔩(1 {{!}} 1) |url=http://www.tandfonline.com/doi/abs/10.1080/00927872.2012.658533 |journal=Communications in Algebra |language=en |volume=41 |issue=7 |pages=2405–2416 |doi=10.1080/00927872.2012.658533 |issn=0092-7872|arxiv=1201.2482v1|s2cid=119125305 }}

{{Cite journal |last1=Kudryavtseva |first1=Ganna |last2=Mazorchuk |first2=Volodymyr |date=2008 |title=Schur–Weyl dualities for symmetric inverse semigroups |url=https://linkinghub.elsevier.com/retrieve/pii/S0022404908000169 |journal=Journal of Pure and Applied Algebra |language=en |volume=212 |issue=8 |pages=1987–1995 |doi=10.1016/j.jpaa.2007.12.004|arxiv=math/0702864|s2cid=13564450 }}

{{Cite journal |last1=Halverson |first1=Tom |last2=delMas |first2=Elise |date=2014-01-02 |title=Representations of the Rook-Brauer Algebra |url=http://www.tandfonline.com/doi/abs/10.1080/00927872.2012.716120 |journal=Communications in Algebra |language=en |volume=42 |issue=1 |pages=423–443 |doi=10.1080/00927872.2012.716120 |issn=0092-7872|arxiv=1206.4576v2|s2cid=38469372 }}

{{Cite journal |last1=Mishra |first1=Ashish |last2=Srivastava |first2=Shraddha |date=2021 |title=Jucys–Murphy elements of partition algebras for the rook monoid |url=https://www.worldscientific.com/doi/abs/10.1142/S0218196721500399 |journal=International Journal of Algebra and Computation |language=en |volume=31 |issue=5 |pages=831–864 |doi=10.1142/S0218196721500399 |issn=0218-1967|arxiv=1912.10737v3|s2cid=209444954 }}

{{Cite journal |last1=Colmenarejo |first1=Laura |last2=Orellana |first2=Rosa |last3=Saliola |first3=Franco |last4=Schilling |first4=Anne |last5=Zabrocki |first5=Mike |date=2020 |title=An insertion algorithm on multiset partitions with applications to diagram algebras |url=https://linkinghub.elsevier.com/retrieve/pii/S0021869320301873 |journal=Journal of Algebra |language=en |volume=557 |pages=97–128 |doi=10.1016/j.jalgebra.2020.04.010|arxiv=1905.02071v2|s2cid=146121089 }}

{{Cite journal |last1=Halverson |first1=Tom |last2=Jacobson |first2=Theodore N. |date=2020 |title=Set-partition tableaux and representations of diagram algebras |url=https://alco.centre-mersenne.org/item/ALCO_2020__3_2_509_0 |journal=Algebraic Combinatorics |language=en |volume=3 |issue=2 |pages=509–538 |doi=10.5802/alco.102 |issn=2589-5486|arxiv=1808.08118v2|s2cid=119167251 }}

{{Cite journal |last1=Halverson |first1=Tom |last2=Ram |first2=Arun |date=2005 |title=Partition algebras |url=https://linkinghub.elsevier.com/retrieve/pii/S0195669804000976 |journal=European Journal of Combinatorics |language=en |volume=26 |issue=6 |pages=869–921 |doi=10.1016/j.ejc.2004.06.005|arxiv=math/0401314v2|s2cid=1168919 }}

}}

Further reading

  • {{Cite book |last=Kauffman |first=Louis H. |url=https://books.google.com/books?id=av05vRwIKIwC |title=Knots and Physics |date=1991 |publisher=World Scientific |isbn=978-981-02-0343-6 |language=en}}
  • {{Cite journal |last=Kauffman |first=Louis H. |date=1990 |title=An invariant of regular isotopy |url=https://www.ams.org/tran/1990-318-02/S0002-9947-1990-0958895-7/ |journal=Transactions of the American Mathematical Society |language=en |volume=318 |issue=2 |pages=417–471 |doi=10.1090/S0002-9947-1990-0958895-7 |issn=0002-9947|doi-access=free }}

Category:Representation theory

Category:Diagram algebras