Sign-balanced posets (Q5940301): Difference between revisions

Let \(P\) be a poset with \(n\) elements and fixed labeling of the elements of \(P\) (i.e. a bijection \(f\) from \(P\) to \(\{1,2,\dots,n\}\)). One may consider the linear extensions (of the partial ordering) of \(P\) as permutations of the labeling. An important characteristic of this set of permutations is its statistic generating function for inversions \(\text{INV}_{P,f}(q)=\sum q^{\text{inv}(\pi)}\), where \(\text{inv}(\pi)\) is the number of inversions of the permutation \(\pi\) and the sum is on all permutations corresponding to linear extensions of \(P\). \textit{A. Björner} and \textit{M. L. Wachs} [J. Comb. Theory, Ser. A 58, No. 1, 85-114 (1991; Zbl 0742.05084)] found an interesting presentation of \(\text{INV}_{P,f}(q)\) for some special kinds of posets. A substantial weakening of the problem to study \(\text{INV}_{P,f}(q)\) is simply to evaluate \(\text{INV}_{P,f}(-1)\) which, up to a sign, is independent of the choice of the labeling. It is natural to descibe the sign-balanced posets defined with the property \(\text{INV}_{P,f}(-1)=0\). In the paper under review the author studies posets with Hasse diagrams which are Ferrers diagrams. If the poset \(P\) is a product of an \(m\)-chain with an \(n\)-chain and both \(m\) and \(n\) are even, then \textit{G. Pruesse} and \textit{F. Ruskey} [SIAM J. Discrete Math. 4, No. 3, 413-422 (1991; Zbl 0757.05075)] established that \(P\) is sign-balanced. The main result of the paper under review is to confirm the conjecture of \textit{F. Ruskey} [J. Comb. Theory, Ser. B 54, No. 1, 77-101 (1992; Zbl 0772.06004, preview in Zbl 0697.06001)] that if \(m\) or \(n\) is odd, then \(P\) is not sign-balanced. The linear extensions of a poset with Hasse diagram which is a Ferrers diagram, are in one-to-one correspondence with the standard tableaux associated with the Ferrers diagram, and the author involves various techniques for tableaux. In particular, the main idea is to relate sign-balanced posets with domino tableaux and this allows to give a larger class of sign-balanced posets. Finally the author gives a direct combinatorial proof for products of two chains using a sign-reversing involution.