A MONOID FOR THE UNIVERSAL k-BRUHAT ORDER

NANTEL BERGERON AND FRANK SOTTILE

Abstract. Structure constants for the multiplication of Schubert polynomials by Schur symmetric polynomials are known to be related to the enumeration of chains in a new partial order on Sym_{∞}, the universal k-Bruhat order. Here we present a monoid M for this order. We show that M is analogous to the nil-Coxeter monoid for the weak order on Sym_{∞}. For this, we develop the theory of reduced sequences for M. We use these sequences to give a combinatorial description of the structure constants above. We also give a combinatorial proof of some of the symmetry relations satisfied by these constants.