The University of Michigan Combinatorics Seminar
|
|---|
|
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.
|