Properties of the nonsymmetric Robinson-Schensted-Knuth algorithm

Haglund, James ; Mason, Sarah ; Remmel, Jeffrey

Journal of Algebraic Combinatorics, Tome 38 (2013) no. 2, pp. 285-327.

Résumé

Summary: We introduce a generalization of the Robinson-Schensted-Knuth insertion algorithm for semi-standard augmented fillings whose basement is an arbitrary permutation $\sigma \in S _{ n }$. If $\sigma $ is the identity, then our insertion algorithm reduces to the insertion algorithm introduced by the second author (Sémin. Lothar. Comb. 57:B57e, 2006) for semi-standard augmented fillings and if $\sigma $ is the reverse of the identity, then our insertion algorithm reduces to the original Robinson-Schensted-Knuth row insertion algorithm. We use our generalized insertion algorithm to obtain new decompositions of the Schur functions into nonsymmetric elements called generalized Demazure atoms (which become Demazure atoms when $\sigma $ is the identity). Other applications include Pieri rules for multiplying a generalized Demazure atom by a complete homogeneous symmetric function or an elementary symmetric function, a generalization of Knuth's correspondence between matrices of non-negative integers and pairs of tableaux, and a version of evacuation for composition tableaux whose basement is an arbitrary permutation $\sigma $.

Détail

Keywords: symmetric functions, permutations, nonsymmetric macdonald polynomials, Demazure atoms, permuted basement fillings