Promotion and Evacuation

Richard P. Stanley


Promotion and evacuation are bijections on the set of linear extensions of a finite poset first defined by Schützenberger. This paper surveys the basic properties of these two operations and discusses some generalizations. Linear extensions of a finite poset $P$ may be regarded as maximal chains in the lattice $J(P)$ of order ideals of $P$. The generalizations concern permutations of the maximal chains of a wider class of posets, or more generally bijective linear transformations on the vector space with basis consisting of the maximal chains of any poset. When the poset is the lattice of subspaces of ${\Bbb F}_q^n$, then the results can be stated in terms of the expansion of certain Hecke algebra products.

Full Text: PDF