The University of Michigan Combinatorics Seminar
Winter 2003
March 28, 4:10-5:00, 4088 East Hall
(pre-talk 2:15-2:45, 3866 East Hall)





Sign-balanced and maj-balanced posets

Richard Stanley

MIT




Abstract

Let P be a poset with elements 1,2,...,n. We say that P is sign-balanced if exactly half the linear extensions of P (regarded as permutations of 1,2,...,n) are even permutations, i.e., have an even number of inversions. This concept first arose in the work of Frank Ruskey, who was interested in the efficient generation of all linear extensions of P. We survey a number of techniques for showing that posets are sign-balanced, and more generally, computing their "imbalance." There are close connections with domino tilings and, for certain posets, a "domino generalization" of Schur functions due to Carré and Leclerc. These posets are also connected with work of Eremenko and Gabrielov on the degree of real Wronski maps. We also say that P is maj-balanced if exactly half the linear extensions of P have even major index (a statistic on permutations with many similarities to the number of inversions). We discuss some similarities and some differences between sign-balanced and maj-balanced posets.