The skeleton of a reduced word and a correspondence of Edelman and Green

Stefan Felsner

The electronic journal of combinatorics, Tome 8 (2001) no. 1

Résumé

Stanley conjectured that the number of maximal chains in the weak Bruhat order of $S_n$, or equivalently the number of reduced decompositions of the reverse of the identity permutation $ w_0 = n,n-1,n-2,\ldots,2,1$, equals the number of standard Young tableaux of staircase shape $s=\{n-1,n-2,\ldots,1\}$. Originating from this conjecture remarkable connections between standard Young tableaux and reduced words have been discovered. Stanley proved his conjecture algebraically, later Edelman and Greene found a bijective proof. We provide an extension of the Edelman and Greene bijection to a larger class of words. This extension is similar to the extension of the Robinson-Schensted correspondence to two line arrays. Our proof is inspired by Viennot's planarized proof of the Robinson-Schensted correspondence. As it is the case with the classical correspondence the planarized proofs have their own beauty and simplicity.

Détail

DOI : 10.37236/1554

Classification : 05E10, 20F55
Mots-clés : chains in the weak Bruhat order, reduced decompositions, Young tableaux, bijective proof, planarization