2 FRANCESCO BRENTI

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

E^U;«K

=

^ (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)

T

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

a

( P , u ; ) Q ^

nOa=l

= V-'^X^Wjrhyz

(3)

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