RSK insertion for set partitions and diagram algebras (Q2583631)

Two fundamental identities in the representation theory of the symmetric group \(S_k\) are (a) \(n^k=\sum_{\lambda\vdash k, \ell(\lambda)\leq n}f^\lambda d_\lambda\) and (b) \(k!=\sum_{\lambda\vdash k}(f^\lambda)^2\), where \(\lambda\) varies over partitions of the integer \(k\) of length \(\ell(\lambda)\leq n\), \(f^\lambda\) is the number of standard Young tableaux of shape \(\lambda\), and \(d_\lambda\) is the number of column strict tableaux of shape \(\lambda\) with entries from \(\{1,\dots,n\}\). A combinatorial proof of (b) was provided by Robinson and Schensted, and of (a) by Knuth, using the so-called RSK insertion algorithm. The authors extend the two identities to the partition algebras \({\mathbb C}A_k(n)\) and \({\mathbb C}A_{k+\frac{1}{2}}(n)\), which may be defined, for \(n\geq 2k\), as the centralizers of \(S_n\) and \(S_{n-1}\), respectively, in \(\text{GL}_n(\mathbb C)\). The analogues are (A) \(n^k=\sum_{\lambda\in\Lambda_n^k}f^\lambda m_k^\lambda\) and (B) \(B(2k)=\sum_{\lambda\in\Gamma_k}(m_k^\lambda)^2\), where \(m_k^\lambda\) is the number of vacillating tableaux of shape \(\lambda\) and length \(2k\) and \(B(2k)\) is the number of set partitions of \(\{1,\dots,2k\}\). (\(\Lambda_n^k\) is a set of partitions which indexes the irreducible representations of \({\mathbb C}A_k(n)\); for \(n\geq 2k\) it is equivalent to \(\Gamma_k\), which is better suited to stating and proving (B).) The authors use iterations of Schützenberger's jeu de taquin and RSK column insertion to obtain algorithms (equations (3.4) and (4.4)) which give combinatorial proofs of identities (A) (Theorem 3.1) and (B) (Theorem 4.4). The insertion algorithm restricts to several diagram algebras which appear as subalgebras of \({\mathbb C}A_k(n)\), and this gives combinatorial proofs of analogues of (B) for each of these algebras (equations (5.1) to (5.4)). They also show that the algorithm has the symmetry property of the usual RSK algorithm for the symmetric group (Cor. 5.6).