RSK Insertion for Set Partitions and Diagram Algebras

Abstract

We give combinatorial proofs of two identities from the representation theory of the partition algebra $C{A}_k(n),n\ge 2k$. The first is $n^k={\sum }_{\lambda }{f}^{\lambda }{m}_k^{\lambda }$, where the sum is over partitions $\lambda$ of $n$, $f^{\lambda }$ is the number of standard tableaux of shape $\lambda$, and $m_k^{\lambda }$ is the number of "vacillating tableaux" of shape $\lambda$ and length $2k$. Our proof uses a combination of Robinson-Schensted-Knuth insertion and jeu de taquin. The second identity is $B(2k)={\sum }_{\lambda }(m_k^{\lambda }{)}^2$, where $B(2k)$ is the number of set partitions of $\{1,>...,2k\}$. We show that this insertion restricts to work for the diagram algebras which appear as subalgebras of the partition algebra: the Brauer, Temperley-Lieb, planar partition, rook monoid, planar rook monoid, and symmetric group algebras.

24 pages