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.
Previous Page Next Page