PF SEQUENCES IN COMBINATORICS 3

numbers) is called log-concave if of at_ia;+i for i = 1,.. . ,d — 1, is said to be unimodal

if there exists an index 0 j d such that a,- a

t+ 1

for i = 0 , . . . , j — 1 and at ai+1

for i = j,...,d — 1, and is said to have no internal zeros if there are not three indices

0ijkd such that a{,ak =^ 0 and aj = 0. We say that a polynomial Y^i=oai X% 1S

log-concave (respectively, unimodal, with no internal zeros) if the sequence {a

0

,ai,.. . ,0^}

has the corresponding property.

Theorem 1.2.1 Let Y^=oaix% be a polynomial with nonnegative coefficients and with only

real zeros. Then the sequence {ao?ai? • • • iad) is log-concave with no internal zeros; in par-

ticular it is unimodal.

This result allows us immediately to derive from Conjectures 1 and 2 some weaker (eas-

ier?) but almost just as interesting conjectures:

Conjecture 1.1 The polynomial W(P, u; z) is log- concave with no internal zeros.

Conjecture 1.2 The polynomial W{P,LO\Z) is unimodal.

Conjecture 2.1 The polynomial E(P,UJ'1Z) is log-concave with no internal zeros.

Conjecture 2.2 The polynomial E(P,OJ;Z) is unimodal.

It should be noted that while equation (4) immediately implies that Conjectures 1 and

2 are equivalent it does not imply the equivalence of Conjectures 1.1 and 2.1 or that of 1.2

and 2.2. As a matter of fact, we will show in section 2.5 that Conjecture 1.1 actually implies

Conjecture 2.1, (see Theorem 2.5.8).

All the conjectures above stated can be specialized also in another direction, namely

to the case of u; being a natural labeling. In this case the combinatorial interpretation of

the polynomials E{P\z) and W(P]z) (we will usually write just E(P;z), W(P\z), etc.,

instead of E(P,uj]z), W(P,w1z), etc., if u; is a natural labeling) becomes particularly nice

and simple. In fact, it is easy to see that, for s £ N , es(P) is the number of surjective order

reversing (or, equivalently, order preserving) maps P —• s, (where s denotes a chain with

5 elements) while the coefficient of z8 in W(P; z) equals the number of linear extensions of

P with exactly s descents. Now, it is very easy to see that if a : P —• s is a surjective

order preserving map then cr~1([l]) C cr""1([2]) C .. . C cr~x([s — 1]) is a chain of 5 — 1 order

ideals in J(P) (the distributive lattice of order ideals of P) and that this correspondence

is a bijection. Therefore, we may also think of ea(P) as the number of chains of length s

from 0 to P in J(P). Since, by a well known classical result (see, e. g. , [5] or [63], Thm

3.4.1), every finite distributive lattice is of the form J(P) for some poset P , we may restate

Conjecture 2, in the case of a natural labeling, as follows:

Conjecture 3 (The distributive lattice conjecture) Let D be a (finite) distributive

lattice and let, for s € N

;

cs(D) be the number of chains of length s from 0 to 1 in D. Then

the polynomial C(D, z) = Y}s=ocs{D)zs has only real zeros.

In Chapter 7 we will see how the point of view of Conjecture 3 is probably the most

useful one in trying to solve the Poset Conjecture for natural labelings.