RSK insertion for set partitions and diagram algebras

Tom Halverson ; Tim Lewandowski

The electronic journal of combinatorics, The Stanley Festschrift volume, Tome 11 (2004) no. 2

Résumé

We give combinatorial proofs of two identities from the representation theory of the partition algebra ${\Bbb 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, \ldots, 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.

Détail

DOI : 10.37236/1881

Classification : 05A19, 05E10, 05A17
Mots-clés : symmetric group, partition algebra, diagram algebra, Young tableau, vacillating tableau