Relating Edelman-Greene insertion to the Little map

Abstract

The Little map and the Edelman-Greene insertion algorithm, a generalization of the Robinson-Schensted correspondence, are both used for enumerating the reduced decompositions of an element of the symmetric group. We show the Little map factors through Edelman-Greene insertion and establish new results about each map as a consequence. In particular, we resolve some conjectures of Lam and Little.

Keywords

• young tableaux
• reduced decompositions in the symmetric group
• edelman-greene insertion
• lascoux-schützenberger tree
• knuth moves
• stanley symmetric functions
• [info.info-dm]computer science [cs]/discrete mathematics [cs.dm]