An insertion algorithm on multiset partitions with applications to diagram algebras

DOI10.1016/J.JALGEBRA.2020.04.010MaRDI QIDQ2178556zbMATH OpenOpenAlexFDO

Authors Laura Colmenarejo, Anne Schilling, Rosa Orellana, Franco Saliola, Mike Zabrocki

Publication date 11 May 2020

Published in Journal of Algebra (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.02071

zbMATH Keywords

representation theoryRSK algorithmpartition algebrasmultiset tableaux

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Partitions of sets (05A18) Combinatorial aspects of representation theory (05E10) Representations of finite symmetric groups (20C30)

Abstract: We generalize the Robinson-Schensted-Knuth algorithm to the insertion of two row arrays of multisets. This generalization leads to new enumerative results that have representation theoretic interpretations as decompositions of centralizer algebras and the spaces they act on. In addition, restrictions on the multisets lead to further identities and representation theory analogues. For instance, we obtain a bijection between words of length $k$ with entries in $[n]$ and pairs of tableaux of the same shape with one being a standard Young tableau of size $n$ and the other being a standard multiset tableau of content $[k]$. We also obtain an algorithm from partition diagrams to pairs of a standard tableau and a standard multiset tableau of the same shape, which has the remarkable property that it is well-behaved with respect to restricting a representation to a subalgebra. This insertion algorithm matches recent representation-theoretic results of Halverson and Jacobson.

Recommendations

• An insertion algorithm for diagram algebras
• RSK insertion for set partitions and diagram algebras
• Set-partition tableaux and representations of diagram algebras
• The multiset partition algebra
• scientific article; zbMATH DE number 2242531
• Embedding dualities for set partitions and for relational structures
• Publication:4886037
• Set-partition tableaux, symmetric group multiplicities, and partition algebra modules
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Algorithms for constructing the shortest allowable partitions of finite sets

Cites work

• scientific article; zbMATH DE number 1296970 (Why is no real title available?)
• scientific article; zbMATH DE number 1160038 (Why is no real title available?)
• scientific article; zbMATH DE number 1160560 (Why is no real title available?)
• scientific article; zbMATH DE number 1950436 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 796484 (Why is no real title available?)
• Characters of the partition algebras.
• Combinatory analysis. Vols. I, II (bound in one volume)
• Dimensions of irreducible modules for partition algebras and tensor power multiplicities for symmetric and alternating groups
• Enumerative applications of a decomposition for graphs and digraphs
• Ideals, Varieties, and Algorithms
• Index for subfactors
• Longest Increasing and Decreasing Subsequences
• Motzkin algebras
• On algebras which are connected with the semisimple continuous groups
• On an algebraic approach to higher dimensional statistical mechanics
• On the representation theory of partial Brauer algebras
• On the structure of Brauer's centralizer algebras
• Partition algebras and the invariant theory of the symmetric group
• Partition algebras.
• Permutations, matrices, and generalized Young tableaux
• Products of symmetric group characters
• RSK insertion for set partitions and diagram algebras
• Relations between the ‘percolation’ and ‘colouring’ problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the ‘percolation’ problem
• Representation theory of the symmetric groups. The Okounkov-Vershik approach, character formulas, and partition algebras.
• Representations of graph Temperley-Lieb algebras
• Representations of the \(q\)-rook monoid.
• Representations of the rook monoid.
• Representations of the rook-Brauer algebra
• Set-partition tableaux and representations of diagram algebras
• Set-partition tableaux, symmetric group multiplicities, and partition algebra modules
• The multiset partition algebra
• The planar rook algebra and Pascal's triangle.
• The representation theory of the Temperley-Lieb algebras

Cited in

(18)

• Super multiset RSK and a mixed multiset partition algebra
• Set-partition tableaux, symmetric group multiplicities, and partition algebra modules
• Cellular subalgebras of the partition algebra
• Young-type matrix units for non-propagating partition algebra submodules
• The multiset partition algebra
• Representations of the quasi-partition algebras
• Howe duality of the symmetric group and a multiset partition algebra
• Robinson-Schensted correspondence for party algebras
• RSK insertion for set partitions and diagram algebras
• Insertion algorithms for Gelfand \(S_n\)-graphs
• Traces on diagram algebras. II: Centralizer algebras of easy groups and new variations of the Young graph
• Plethysm and the algebra of uniform block permutations
• An insertion algorithm for diagram algebras
• Multiparameter colored partition category and the product of the reduced Kronecker coefficients
• On the limiting vacillating tableaux for integer sequences
• A diagram-like basis for the multiset partition algebra
• Robinson-Schensted correspondence for the signed Brauer algebras
• Alternating submodules for partition algebras, rook algebras, and rook-Brauer algebras

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: An insertion algorithm on multiset partitions with applications to diagram algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2178556)