Shuffle invariance of the super-RSK algorithm

DOI10.1006/AAMA.2001.0767MaRDI QIDQ696799zbMATH OpenOpenAlexFDO

Authors Amitai Regev, Tamar Seeman

Publication date 12 September 2002

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

super-Robinson-Schensted-Knuth correspondence

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10)

Abstract: As in the $(k,l)$-RSK (Robinson-Schensted-Knuth) of [1], other super-RSK algorithms can be applied to sequences of variables from the set $t_1,\mathrm{...},t_k,u_1,\mathrm{...},u_l$, where $t_1<\mathrm{...}<t_k$, and $u_1<\mathrm{...}<u_l$. While the $(k,l)$-RSK of [1] is the case where $t_i<u_j$ for all $i$ and $j$, these other super-RSK's correspond to all the $$ shuffles of the $t$'s and $u$'s satisfying the above restrictions that $t_1<\mathrm{...}<t_k$ and $u_1<\mathrm{...}<u_l$. We show that the shape of the tableaux produced by any such super-RSK is independent of the particular shuffle of the $t$'s and $u$'s.

Review text

The paper is concerned with a further generalisation of A. Berele and A. Regev's generalisation of the Robinson-Schensted-Knuth (RSK) correspondence: While Berele and Regev's \((k,l)\)-RSK maps permutations of the alphabet \(t_1<\dots <t_k<u_1<\dots<u_l\) to pairs of tableaux by applying the usual RSK insertion to the letters \(t_i\) and the conjugate correspondence to the letters \(u_j\), here all \({k+l}\choose{l}\) shuffles of the letters (i.e., reorderings, where only the conditions \(t_1<\dots <t_k\) and \(u_1<\dots<u_l\) apply) are considered. It is shown that the shape of the resulting tableaux is independent of the particular shuffle.

Recommendations

• scientific article; zbMATH DE number 1842502
• Public Key Cryptography – PKC 2004
• Sub-linear Zero-Knowledge Argument for Correctness of a Shuffle
• VERIFICATION OF A PAILLIER BASED SHUFFLE USING REPRESENTATIONS OF THE SYMMETRIC GROUP
• Efficient Zero-Knowledge Argument for Correctness of a Shuffle
• Verifiable Shuffle of Large Size Ciphertexts
• A verifiable secret shuffle of homomorphic encryptions
• A Verifiable Secret Shuffe of Homomorphic Encryptions
• Leakage-resilient riffle shuffle

Cites work

• A bijective proof of a factorization theorem for (k,l)-hook schur functions
• Hook flag characters and their combinatorics
• Hook Young diagrams with applications to combinatorics and to representations of Lie superalgebras
• scientific article; zbMATH DE number 3889534 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2012467 (Why is no real title available?)
• Permutation statistics and (k,)-hook Schur functions

Cited in

(6)

• Super RSK correspondence with symmetry
• A central limit theorem for extremal characters of the infinite symmetric group.
• SUPER RSK-ALGORITHMS AND SUPER PLACTIC MONOID
• Matrix tableau-pairs with key and shuffling conditions
• Bounds on colength and maximal multiplicity sequences.
• The mathematics of Amitai Regev

This page was built for publication: Shuffle invariance of the super-RSK algorithm

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