An insertion algorithm on multiset partitions with applications to diagram algebras (Q2178556): Difference between revisions

This paper gives a generalization of the Robinson-Schensted-Knuth (RSK) algorithm to the case of multiset arrays. In classical RSK, \textit{D. E. Knuth} [Pac. J. Math. 34, 709--727 (1970; Zbl 0199.31901)] gave a bijection between two-row integer arrays and pairs of semistandard Young tableaux of the same shape. By restricting the possible integer arrays, one obtains several other bijections as special cases. As the authors explain in more detail, RSK-like bijections often have representation theoretic content in the form of a direct sum decomposition \(V\cong \bigoplus_{\lambda} U^\lambda \otimes W^\lambda\), where the \(U^\lambda\) and \(W^\lambda\) are modules over algebras that are mutual centralizers, and thus \(U^\lambda\) and \(W^\lambda\) are in duality with each other. This leads to enumerative formulas of the form \(\dim V = \sum_\lambda (\dim U^\lambda)(\dim W^\lambda)\). The authors' first generalization of RSK is as follows: the top row of their array consists of multisets (sets with multiplicity), while the bottom row consists of integers without repetition. They show that these arrays are in correspondence with pairs of tableaux where one is a standard (integer) tableau, and the other is a semistandard multiset tableau (under a graded lexicographic order). Specializing to arrays with disjoint multisets, they obtain bijective and enumerative results (Corollary 5.4, (5.1)) which on the representation theory side correspond to the duality between the symmetric group and the partition algebra [\textit{T. Halverson} and \textit{A. Ram}, Eur. J. Comb. 26, No. 6, 869--921 (2005; Zbl 1112.20010)]. The authors go on to construct a bijection between the set partitions that generate the partition algebra and pairs of standard multiset tableaux. The nicest feature of this bijection is that it restricts nicely to a large class of subalgebras: the symmetric group algebra, the rook algebra, and the Temperley-Lieb algebra, among several others. This property allows the authors to prove uniform dimension formulas for all of these algebras in terms of multiset tableaux with certain restrictions. They then construct the branching diagram for each of these subalgebras in terms of the combinatorics of multiset tableaux (Theorem 6.13). Bases of irreducible representations are given as sets of multiset tableaux, and restrictions are realized by a certain projection-like operator on multiset tableaux. Finally, the connection between multiset tableaux and vacillating tableaux is also explored, and a new bijection is given.