Partition algebra

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 formula_1 elements labelled formula_2 is represented as a diagram, with lines connecting elements in the same subset. In the following example, the subset formula_3 gives rise to the lines formula_4, and could equivalently be represented by the lines formula_5 (for instance).
For formula_6 and formula_7, the partition algebra formula_8 is defined by a formula_9-basis made of partitions, and a multiplication given by diagram concatenation. The concatenated diagram comes with a factor formula_10, where formula_11 is the number of connected components that are disconnected from the top and bottom elements.
Generators and relations.
The partition algebra formula_8 is generated by formula_13 elements of the type
These generators obey relations that include
Other elements that are useful for generating subalgebras include
In terms of the original generators, these elements are 
Properties.
The partition algebra formula_8 is an associative algebra. It has a multiplicative identity
The partition algebra formula_8 is semisimple for formula_18. For any two formula_19 in this set, the algebras formula_8 and formula_21 are isomorphic.
The partition algebra is finite-dimensional, with formula_22 (a Bell number).
Subalgebras.
Eight subalgebras.
Subalgebras of the partition algebra can be defined by the following properties:
Combining these properties gives rise to 8 nontrivial subalgebras, in addition to the partition algebra itself:
The symmetric group algebra formula_28 is the group ring of the symmetric group formula_29 over formula_9. The Motzkin algebra is sometimes called the dilute Temperley–Lieb algebra in the physics literature.
Properties.
The listed subalgebras are semisimple for formula_18.
Inclusions of planar into non-planar algebras:
Inclusions from constraints on subset size:
Inclusions from allowing top-top and bottom-bottom lines:
We have the isomorphism:
More subalgebras.
In addition to the eight subalgebras described above, other subalgebras have been defined:
An algebra with a half-integer index formula_43 is defined from partitions of formula_44 elements by requiring that formula_45 and formula_46 are in the same subset. For example, formula_47 is generated by formula_48 so that formula_49, and formula_50.
Periodic subalgebras are generated by diagrams that can be drawn on an annulus without line crossings. Such subalgebras include a translation element formula_51 such that formula_52. The translation element and its powers are the only combinations of formula_53 that belong to periodic subalgebras.
Representations.
Structure.
For an integer formula_54, let formula_55 be the set of partitions of formula_56 elements formula_57 (bottom) and formula_58 (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 formula_59:
Partition diagrams act on formula_55 from the bottom, while the symmetric group formula_61 acts from the top. For any Specht module formula_62 of formula_61 (with therefore formula_64), we define the representation of formula_8
The dimension of this representation is
where formula_68 is a Stirling number of the second kind, formula_69 is a binomial coefficient, and formula_70 is given by the hook length formula.
A basis of formula_71 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 formula_8 is semisimple, the representation formula_71 is irreducible, and the 
set of irreducible finite-dimensional representations of the partition algebra is 
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 formula_75 with formula_76, 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.
^k \left\{ {k\atop \ell} \right\} \binom{\ell}&lt;/math&gt;
The irreducible representations of formula_36 are indexed by partitions such that formula_110 and their dimensions are formula_111. The irreducible representations of formula_112 are indexed by partitions such that formula_113. The irreducible representations of formula_41 are indexed by sequences of partitions.
Schur-Weyl duality.
Assume formula_115.
For formula_116 a formula_26-dimensional vector space with basis formula_118, there is a natural action of the partition algebra formula_8 on the vector space formula_120. This action is defined by the matrix elements of a partition formula_121 in the basis formula_122:
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 
Duality between the partition algebra and the symmetric group.
Let formula_125 be integer.
Let us take formula_116 to be the natural permutation representation of the symmetric group formula_127. This formula_26-dimensional representation is a sum of two irreducible representations: the standard and trivial representations, formula_129.
Then the partition algebra formula_8 is the centralizer of the action of formula_127 on the tensor product space formula_120, 
Moreover, as a bimodule over formula_134, the tensor product space decomposes into irreducible representations as 
where formula_136 is a Young diagram of size formula_26 built by adding a first row to formula_82, and formula_139 is the corresponding Specht module of formula_127.
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 formula_141 for an irreducible formula_26-dimensional representation of the first group or algebra: