The University of Michigan Combinatorics Seminar


Abstract 

Let P be a poset with elements 1,2,...,n.
We say that P is signbalanced 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 signbalanced, 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 majbalanced 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 signbalanced and
majbalanced posets.
