Colmenarejo, Laura; Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike An insertion algorithm on multiset partitions with applications to diagram algebras. (English) Zbl 1460.05195 J. Algebra 557, 97-128 (2020). This paper gives a generalization of the Robinson-Schensted-Knuth (RSK) algorithm to the case of multiset arrays. In classical RSK, 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 [T. Halverson and 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. Reviewer: Andrew Hardt (Minneapolis) Cited in 7 Documents MSC: 05E10 Combinatorial aspects of representation theory 20C30 Representations of finite symmetric groups 05C85 Graph algorithms (graph-theoretic aspects) 05A18 Partitions of sets Keywords:partition algebras; RSK algorithm; multiset tableaux; representation theory Citations:Zbl 0199.31901; Zbl 1112.20010 Software:OEIS PDFBibTeX XMLCite \textit{L. Colmenarejo} et al., J. Algebra 557, 97--128 (2020; Zbl 1460.05195) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Bell or exponential numbers: number of ways to partition a set of n labeled elements. Number of oriented multigraphs on n labeled arcs (with loops). References: [1] Benkart, Georgia; Halverson, Tom, Motzkin algebras, Eur. J. Comb., 36, 473-502 (2014), MR 3131911 · Zbl 1284.05333 [2] Benkart, Georgia; Halverson, Tom, Partition algebras and the invariant theory of the symmetric group, (Recent Trends in Algebraic Combinatorics. Recent Trends in Algebraic Combinatorics, Assoc. Women Math. Ser., vol. 16 (2019), Springer: Springer Cham), 1-41, MR 3969570 · Zbl 1421.05094 [3] Benkart, Georgia; Halverson, Tom; Harman, Nate, Dimensions of irreducible modules for partition algebras and tensor power multiplicities for symmetric and alternating groups, J. Algebraic Comb., 46, 1, 77-108 (2017), MR 3666413 · Zbl 1368.05156 [4] Brauer, Richard, On algebras which are connected with the semisimple continuous groups, Ann. Math. (2), 38, 4, 857-872 (1937), MR 1503378 · Zbl 0017.39105 [5] Cox, David A.; Little, John; O’Shea, Donal, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics (2015), Springer: Springer Cham, MR 3330490 · Zbl 1335.13001 [6] Comtet, Louis, Advanced Combinatorics: The Art of Finite and Infinite Expansions (1974), D. Reidel Publishing Co.: D. Reidel Publishing Co. Dordrecht, MR 0460128 · Zbl 0283.05001 [7] Ceccherini-Silberstein, Tullio; Scarabotti, Fabio; Tolli, Filippo, Representation Theory of the Symmetric Groups: The Okounkov-Vershik Approach, Character Formulas, and Partition Algebras, Cambridge Studies in Advanced Mathematics, vol. 121 (2010), Cambridge University Press: Cambridge University Press Cambridge, MR 2643487 · Zbl 1230.20002 [8] Flath, Daniel; Halverson, Tom; Herbig, Kathryn, The planar rook algebra and Pascal’s triangle, Enseign. Math. (2), 55, 1-2, 77-92 (2009), MR 2541502 · Zbl 1209.20004 [9] Gessel, Ira M., Enumerative applications of a decomposition for graphs and digraphs, Formal Power Series and Algebraic Combinatorics. Formal Power Series and Algebraic Combinatorics, Montreal, PQ, 1992. Formal Power Series and Algebraic Combinatorics. Formal Power Series and Algebraic Combinatorics, Montreal, PQ, 1992, Discrete Math., 139, 1-3, 257-271 (1995), MR 1336842 · Zbl 0827.05045 [10] Goodman, Roe; Wallach, Nolan R., Representations and Invariants of the Classical Groups, Encyclopedia of Mathematics and Its Applications, vol. 68 (1998), Cambridge University Press: Cambridge University Press Cambridge, MR 1606831 · Zbl 0901.22001 [11] Halverson, Tom, Characters of the partition algebras, J. Algebra, 238, 2, 502-533 (2001), MR 1823772 · Zbl 1083.20010 [12] Halverson, T., Representations of the q-rook monoid, J. Algebra, 273, 227-251 (2004) · Zbl 1072.20006 [13] Halverson, Tom, Set-partition tableaux, symmetric group multiplicities, and partition algebra modules, Sémin. Lothar. Comb., 82B, Article 58 pp. (2019) · Zbl 1435.05220 [14] Halverson, Tom; delMas, Elise, Representations of the rook-Brauer algebra, Commun. Algebra, 42, 1, 423-443 (2014), MR 3169580 · Zbl 1291.05215 [15] Halverson, Tom; Jacobson, Theodore N., Set-partition tableaux and representations of diagram algebras (2018), arXiv e-prints · Zbl 1436.05124 [16] Halverson, Tom; Lewandowski, Tim, RSK insertion for set partitions and diagram algebras, Electron. J. Comb., 11, 2, Article R24 pp. (2004/2006), MR 2195430 · Zbl 1086.05014 [17] Howe, Roger, Perspectives on invariant theory: Schur duality, multiplicity-free actions and beyond, (The Schur Lectures. The Schur Lectures, Tel Aviv, 1992. The Schur Lectures. The Schur Lectures, Tel Aviv, 1992, Israel Math. Conf. Proc., vol. 8 (1995), Bar-Ilan Univ.: Bar-Ilan Univ. Ramat Gan), 1-182, MR 1321638 · Zbl 0844.20027 [18] Halverson, Tom; Ram, Arun, Partition algebras, Eur. J. Comb., 26, 6, 869-921 (2005), MR 2143201 · Zbl 1112.20010 [19] OEIS Foundation Inc., The on-line encyclopedia of integer sequences, 2019 (online). · Zbl 1044.11108 [20] Jones, V. F.R., Index for subfactors, Invent. Math., 72, 1, 1-25 (1983), MR 696688 · Zbl 0508.46040 [21] Jones, V. F.R., The Potts model and the symmetric group, (Subfactors. Subfactors, Kyuzeso, 1993 (1994), World Sci. Publ.: World Sci. Publ. River Edge, NJ), 259-267, MR 1317365 · Zbl 0938.20505 [22] Knuth, Donald E., Permutations, matrices, and generalized Young tableaux, Pac. J. Math., 34, 709-727 (1970), MR 0272654 · Zbl 0199.31901 [23] MacMahon, Percy A., Combinatory Analysis, vols. I, II, Dover Phoenix Editions (2004), Dover Publications, Inc.: Dover Publications, Inc. Mineola, NY, Reprint of An Introduction to Combinatory Analysis (1920) and Combinatory Analysis, vols. I, II (1915, 1916), MR 2417935 · Zbl 1144.05300 [24] Martin, Paul P., Representations of graph Temperley-Lieb algebras, Publ. Res. Inst. Math. Sci., 26, 3, 485-503 (1990), MR 1068862 · Zbl 0718.17025 [25] Martin, Paul; Mazorchuk, Volodymyr, On the representation theory of partial Brauer algebras, Q. J. Math., 65, 1, 225-247 (2014), MR 3179659 · Zbl 1354.16016 [26] Martin, P. P.; Rollet, G., The Potts model representation and a Robinson-Schensted correspondence for the partition algebra, Compos. Math., 112, 2, 237-254 (1998), MR 1626017 · Zbl 0899.05070 [27] Martin, Paul; Saleur, Hubert, On an algebraic approach to higher-dimensional statistical mechanics, Commun. Math. Phys., 158, 1, 155-190 (1993), MR 1243720 · Zbl 0784.05056 [28] Narayanan, Sridhar; Paul, Digjoy; Srivastava, Shraddha, The multiset partition algebra (2019), arXiv e-prints · Zbl 1527.05176 [29] Orellana, Rosa; Zabrocki, Mike, Symmetric group characters as symmetric functions (2016), arXiv e-prints · Zbl 1414.05298 [30] Orellana, Rosa; Zabrocki, Mike, A combinatorial model for the decomposition of multivariate polynomials rings as an \(S_n\)-module (2019), arXiv e-prints · Zbl 1414.05298 [31] de B. Robinson, G., On the representations of the symmetric group, Am. J. Math., 60, 3, 745-760 (1938), MR 1507943 · JFM 64.0070.01 [32] Rosas, Mercedes Helena, A Combinatorial Overview of the Theory of MacMahon Symmetric Functions and a Study of the Kronecker Product of Schur Functions (2000), ProQuest LLC: ProQuest LLC Ann Arbor, MI, Thesis (Ph.D.), Brandeis University, MR 2700302 [33] Schur, I., Über eine Klasse von Matrizen, die sich einer gegebenen Matrix zuordnen lassen (1901), JMF 32.0165.04 · JFM 32.0165.04 [34] Schur, I., Über die rationalen Darstellungen der allgemeinen linearen Gruppe, Sitz.ber. Akad. Berlin, 58-75 (1927), JMF 53.0108.05 · JFM 53.0108.05 [35] Schensted, C., Longest increasing and decreasing subsequences, Can. J. Math., 13, 179-191 (1961), MR 0121305 · Zbl 0097.25202 [36] Solomon, Louis, Representations of the rook monoid, J. Algebra, 256, 2, 309-342 (2002), MR 1939108 · Zbl 1034.20056 [37] Temperley, H. N.V.; Lieb, E. H., Relations between the “percolation” and “colouring” problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the “percolation” problem, Proc. R. Soc. Lond. Ser. A, 322, 1549, 251-280 (1971), MR 0498284 · Zbl 0211.56703 [38] Wenzl, Hans, On the structure of Brauer’s centralizer algebras, Ann. Math. (2), 128, 1, 173-193 (1988), MR 951511 · Zbl 0656.20040 [39] Westbury, B. W., The representation theory of the Temperley-Lieb algebras, Math. Z., 219, 4, 539-565 (1995), MR 1343661 · Zbl 0840.16008 [40] Weyl, Hermann, The Classical Groups: Their Invariants and Representations, Princeton Landmarks in Mathematics (1997), Princeton University Press: Princeton University Press Princeton, NJ, Princeton Paperbacks, MR 1488158 · Zbl 1024.20501 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.