invariant of the labeled poset (P,^).
Since 0(P,u;;:r) is a polynomial of degree \P\ there follows from a well known result
about rational generating functions (see e. g. [63], Cor.4.3.1) that there exists a polynomial
W(P,u; z) e R[z] of degree |P | such that
^ (1)
as formal power series in z. We are now already in a position to state the Poset Conjecture:
Conjecture 1 (Th e Poset Conjecture) For all labeled posets (P, tt) the polynomial
W(P, w, z) defined by (2) has only real zeros.
In the case that u is a natural labeling of P Conjecture 1 was first stated in 1978 in [42]
(in the form of Conjecture 2, see below) and later also in [65]. The Poset Conjecture in the
present form has been first conjectured by Stanley in [64].
The polynomial W(P, u;; z) has an important and well known combinatorial interpreta-
tion. However, before we can state this interpretation we need some additional definitions.
Let P be a poset of cardinality p, a linear extension of P is an order preserving bijection
T : P —• [p] (i. e. a natural labeling of P). If (P,o;) is a labeled poset and r is a linear
extension of P then we let d(r,u) = \{i \p 1] : a?(r"1(z)) o;(r~1(z + 1))}|. Using the
theory of (P,u)-partitions it is possible to show (see e. g. [57]) that
W(P,^z)^J2zd{TfU,Hl (2)
where the sum is over all linear extensions r of P . This non trivial result implies in particular
that W(P,u) z) 6 N(^) and we will use this fact often in the sequel.
Now, if we substitute the expression for ft(P, w; n) given in (1) into (2) we obtain
W(P,u;z) = ( l - * ) | F | + 1 £ £ e
( P , u ; ) Q ^
= V-'^X^Wjrhyz
where E(P,w,z) d= E ! = I e.(P,«)za. Therefore, we may equivalently state the Poset Con-
jecture in the following form:
Conjecture 2 (The Poset Conjecture) For any labeled poset (P,u?) the polynomial
E(P,LU; z) defined above has only real zeros.
Now the reader is probably wondering: "Why should we be interested in knowing whether
or not those polynomials have only real zeros?". The answer lies in the following classic re-
sult whose proof can be found e. g. in [29]. Recall that a sequence {a0, a i , . . . , a^} (of real
Previous Page Next Page