ON OPERATORS ON POLYNOMIALS PRESERVING REAL-ROOTEDNESS AND THE NEGGERS-STANLEY CONJECTURE

PETTER BRÄNDÉN

Abstract. We refine a technique used in a paper by Schur on realrooted polynomials. This amounts to an extension of a theorem of Wagner on Hadamard products of Toeplitz matrices. We also apply our results to polynomials for which the Neggers-Stanley Conjecture is known to hold. More precisely, we settle interlacing properties for Epolynomials of series-parallel posets and column-strict labelled Ferrers posets.

1. Introduction

Several polynomials associated to combinatorial structures are known to have real zeros. In most cases one can say more about the location of the zeros, than just that they are on the real axis. The matching polynomial of a graph is not only real-rooted, but it is known that the matching polynomial of the graph obtained by deleting a vertex of G interlaces that of G [4]. The same is true for the characteristic polynomial of graph (see e.g., [3]). If A is a nonnegative matrix and A′ is the matrix obtained by either deleting a row or a column, then Nijenhuis [7] showed that the rook polynomial of A′ interlaces that of A.

The Neggers-Stanley Conjecture asserts that certain polynomials associated to posets, see Section 3, have real zeros; see [1, 9, 13] for the state of the art. For classes of posets for which the conjecture is known to hold we will exhibit explicit interlacing relationships.

The first part of this paper is concerned with operators on polynomials which preserve real-rootedness. The following classical theorem is due to Schur [10]: Theorem 1 (Schur). Let f = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} and g = b_{0} + b_{1}x + ⋯ + b_{m}x^{m} be polynomials in ℝ[x]. Suppose that f and g have only real zeros and that the zeros of g are all of the same sign. Then the polynomial

f ⊙ g := ∑_{k} k!a_{k}b_{k}x^{k},

has only real zeros. If a_{0}b_{0} ≠ 0 then all the zeros of f ⊙ g are distinct.

In this paper we will refine the technique used in Schur’s proof of the theorem to extend a theorem of Wagner [14, Theorem 0.3]. The diamond product of two polynomials f and g is the polynomial

Date: 12th March 2003.

f◇g = ∑_{n≥0} \frac{f^{(n)}(x)}{n!} \frac{g^{(n)}(x)}{n!}x^{n}(x + 1)^{n}.

Brenti [1] conjectured an equivalent form of Theorem 2 and Wagner proved it in [14]. Theorem 2 (Wagner). If f, g ∈ ℝ[x] have all their zeros in the interval [−1, 0] then so does f◇g.

This theorem has important consequences in combinatorics [13], and it also has implications to the theory of total positivity [14].

In the second part of the paper we settle interlacing properties for Epolynomials of series-parallel posets and column-strict labelled Ferrers posets.

We will implicitly use the fact that the zeros of a polynomial are continuous functions of the coefficients of the polynomial. In particular, the limit of real-rooted polynomials will again be real-rooted. For a treatment of these matters we refer the reader to [6].

2. Sturm sequences and linear operators preserving real-rootedness

Let f and g be real polynomials. We say that f and g alternate if f and g are real-rooted and either of the following conditions hold:

(A) deg(g) = deg(f) = d and

α_{1} ≤ β_{1} ≤ α_{2} ≤ ⋯ ≤ β_{d−1} ≤ α_{d} ≤ β_{d},

where α_{1} ≤ ⋯ ≤ α_{d} and β_{1} ≤ ⋯ ≤ β_{d} are the zeros of f and g respectively

(B) deg(f) = deg(g) + 1 = d and

α_{1} ≤ β_{1} ≤ α_{2} ≤ ⋯ ≤ β_{d−1} ≤ α_{d}

where α_{1} ≤ ⋯ ≤ α_{d} and β_{1} ≤ ⋯ ≤ β_{d−1} are the zeros of f and g respectively.

If all the inequalities above are strict then f and g are said to strictly alternate. Moreover, if f and g are as in (B) then we say that g interlaces f, denoted g ⪯ f. In the strict case we write g ≺ f. If the leading coefficient of f is positive we say that f is standard.

For z ∈ ℝ let T_{z} : ℝ[x] → ℝ[x] be the translation operator defined by T_{z}(f(x)) = f(x + z). For any linear operator ϕ : ℝ[x] → ℝ[x] we define a linear transform L_{ϕ} : ℝ[x] → ℝ[x, z] by

L_{ϕ}(f) := ϕ(T_{z}(f))
= ∑_{n} ϕ(f^{(n)})(x)\frac{z^{n}}{n!}  (1)

= ∑_{n} \frac{ϕ(x^{n})}{n!}f^{(n)}(z).

Definition 3. Let ϕ : ℝ[x] → ℝ[x] be a linear operator and let f ∈ ℝ[x]. If ϕ(f^{(n)}) = 0 for all n ∈ ℕ, we let d_{ϕ}(f) = −∞. Otherwise let d_{ϕ}(f) be the smallest integer d such that ϕ(f^{(n)}) = 0 for all n > d.

The set 𝒜^{+}(ϕ) is defined as follows: If d_{ϕ}(f) = −∞, or d_{ϕ}(f) = 0 and ϕ(f) is standard real- and simple-rooted, then f ∈ 𝒜^{+}(ϕ). Moreover, f ∈ 𝒜^{+}(ϕ) if d = d_{ϕ}(f) ≥ 1 and all of the following conditions are satisfied:

(i) ϕ(f^{(i)}) is standard for all i and deg(ϕ(f^{(i−1)})) = deg(ϕ(f^{(i)})) + 1 for 1 ≤ i ≤ d,

(ii) ϕ(f) and ϕ(f′) have no common real zero, (iii) ϕ(f^{(d)}) ≺ ϕ(f^{(d−1)}), (iv) for all ξ ∈ ℝ the polynomial L_{ϕ}(f)(ξ, z) is real-rooted.

Let 𝒜^{−}(ϕ) := {−f : f ∈ 𝒜^{+}(ϕ)} and 𝒜 (ϕ) := 𝒜^{−}(ϕ) ∪ 𝒜^{+}(ϕ).

The following theorem is the basis for our analysis: Theorem 4. Let ϕ : ℝ[x] → ℝ[x] be a linear operator. If f ∈ 𝒜 (ϕ) then ϕ(f) is real- and simple-rooted and if d_{ϕ}(f) ≥ 1 we have

ϕ(f^{(d)}) ≺ ϕ(f^{(d−1)}) ≺ ⋯ ≺ ϕ(f′) ≺ ϕ(f).

Before we give a proof of Theorem 4 we will need a couple of lemmas. Note that \frac{∂}{∂z} L_{ϕ}(f) = L_{ϕ}(f′) so by Rolle’s Theorem we know that L_{ϕ}(f′) is realrooted (in z) if L_{ϕ}(f) is. By Theorem 4 it follows that 𝒜 (ϕ) is closed under differentiation. A (generalised) Sturm sequence is a sequence f_{0}, f_{1}, …, f_{n} of standard polynomials such that deg(f_{i}) = i for 0 ≤ i ≤ n and

f_{i−1}(θ)f_{i+1}(θ) < 0,  (2)

whenever f_{i}(θ) = 0 and 1 ≤ i ≤ n − 1. If f is a standard polynomial with real simple zeros, we know from Rolle’s Theorem that the sequence {f^{(i)}}_{i} is a Sturm sequence. The following lemma is folklore. Lemma 5. Let f_{0}, f_{1}, …, f_{n} be a sequence of standard polynomials with deg(f_{i}) = i for 0 ≤ i ≤ n. Then the following statements are equivalent:

(i) f_{0}, f_{1}, …, f_{n} is a Sturm sequence,

(ii) f_{0} ≺ f_{1} ≺ ⋯ ≺ f_{n}.

The next lemma is of interest for real-rooted polynomials encountered in combinatorics. Lemma 6. Let a_{m}x^{m} + a_{m+1}x^{m+1} + ⋯ + a_{n}x^{n} ∈ ℝ[x] be real-rooted with a_{m}a_{n} ≠ 0. Then the sequence a_{i} is strictly log-concave, i.e.,

a_{i}^{2} > a_{i−1}a_{i+1}, (m + 1 ≤ i ≤ n − 1).

Proof. See Lemma 3 on page 337 of [5]. □

Proof of Theorem 4. Let f ∈ 𝒜^{+}(ϕ). Clearly we may assume that d = d_{ϕ}(f) > 1. We claim that for 1 ≤ n ≤ d − 1:

ϕ(f^{(n)})(θ) = 0 ⟹ ϕ(f^{(n−1)})(θ)ϕ(f^{(n+1)})(θ) < 0.  (3)

If 1 ≤ n ≤ d − 1 and ϕ(f^{(n)})(θ) = 0, then by condition (ii) and (iii) of Definition 3 we have that there are integers 0 ≤ ℓ < n < k ≤ d with ϕ(f^{(ℓ)})(θ)ϕ(f^{(k)})(θ) ≠ 0. By Lemma 6 and the real-rootedness of L_{ϕ}(f)(θ, z) this verifies (3).

If ϕ(f^{(d)}) is a constant then {ϕ(f^{(n)})}_{n} is a Sturm sequence. Otherwise let g = ϕ(f^{(d)}). Then, since g′ ≺ g ≺ ϕ(f^{(d−1)}), we have that (2) is satisfied everywhere in the sequence {g^{(n)}}_{n} ∪ {ϕ(f^{(n)})}_{n}. This proves the theorem by Lemma 5. □

In order to make use of Theorem 4 we will need further results on realrootedness and interlacings of polynomials. There is a characterisation of alternating polynomials due to Obreschkoff and Dedieu. Obreschkoff proved the case of strictly alternating polynomials, see [8, Satz 5.2], and Dedieu [2] generalised it in the case deg(f) = deg(g). But his proof also covers this slightly more general theorem: Theorem 7. Let f and g be real polynomials. Then f and g alternate (strictly alternate) if and only if all polynomials in the space

{αf + βg : α, β ∈ ℝ}

are real-rooted (real- and simple-rooted).

A direct consequence of Theorem 7 is the following theorem, which the author has not seen previously in the literature. Theorem 8. If ϕ : ℝ[x] → ℝ[x] is a linear operator preserving real-rootedness, then ϕ(f) and ϕ(g) alternate if f and g alternate. Moreover, if ϕ preserves real- and simple-rootedness then ϕ(f) and ϕ(g) strictly alternate if f and g strictly alternate.

Proof. The theorem is an immediate consequence of Theorem 7 since the concept of alternating zeros is translated into a linear condition. □

Lemma 9. Let 0 ≠ h, f, g ∈ ℝ[x] be standard and real-rooted. If h ≺ f and h ≺ g, then h ≺ αf + βg for all α, β ≥ 0 not both equal to zero.

Note that Lemma 9 also holds (by continuity arguments) when all instances of ≺ are replaced by ⪯ in Lemma 9.

Proof. If θ is a zero of h then clearly αf+βg has the same sign as f and g at θ. Since {h^{(i)}}_{i}∪{f} is a Sturm sequence by Lemma 5, so is {h^{(i)}}_{i}∪{αf +βg}. By Lemma 5 again the proof follows. □

We will need two classical theorems on real-rootedness. The first theorem is essentially due to Hermite and Poulain and the second is due to Laguerre. Theorem 10 (Hermite, Poulain). Let f(x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} and g be real-rooted. Then the polynomial

f(\frac{d}{dx})g := a_{0}g(x) + a_{1}g′(x) + ⋯ + a_{n}g^{(n)}(x)

is real-rooted. Moreover, if x^{N} ∤ f and deg(g) ≥ N − 1 then any multiple zero of f(\frac{d}{dx})g is a multiple zero of g.

Proof. The case N = 1 is the Hermite-Poulain theorem. A proof can be found in any of the references [5, 8, 10]. For the general result it will suffice to prove that if deg(g) ≠ 0 then any multiple zero of g′ is a multiple zero of g. Let

g = c_{0} + c_{1}(x − θ) + ⋯ + c_{M}(x − θ)^{M},

where c_{M} ≠ 0, M > 0 and (x − θ)^{2}|g′. Then c_{1} = c_{2} = 0 and M > 2. If c_{0} = 0 we are done and if c_{0} ≠ 0 we have by Lemma 6 that 0 = c_{1}^{2} > c_{0}c_{2} = 0, which is a contradiction. □

Theorem 11 (Laguerre). If a_{0} + a_{1}x + a_{2}x^{2} + ⋯ + a_{n}x^{n} is real-rooted then so is

a_{0} + a_{1}x + \frac{a_{2}}{2!} x^{2} + ⋯ + \frac{a_{n}}{n!} x^{n}.

Proof. Claim (ii) can be derived from (i) when applied to x^{n}, (see [1]), or from Theorem 1 as in [5, 10]. □

We are now in a position to extend Theorem 2. Theorem 12. Let h be [−1, 0]-rooted and let f be real-rooted.

(a) Then f◇h is real-rooted, and if g ⪯ f then

g◇h ⪯ f◇h.

(b) If h is (−1, 0)- and simple-rooted and f is simple-rooted then f◇h is

simple-rooted and

g◇h ≺ f◇h,

for all g ≺ f.

Proof. First we assume that deg(h) > 0 and that h is standard, (−1, 0)- rooted and has simple zeros. Let ϕ : ℝ[x] → ℝ[x] be the linear operator defined by ϕ(f) = f◇h.

We will show that f ∈ 𝒜^{+}(ϕ) if f is standard real- and simple-rooted. Clearly we may assume that deg(f) = d ≥ 1. Condition (i) of Definition 3 follows immediately from the definition of the diamond product. Now, f^{(d−1)} = ax + b, where a, b ∈ ℝ and a > 0 so

ϕ(f^{(d)}) = ah and
ϕ(f^{(d−1)}) = (ax + b)h + ax(x + 1)h′,

and since h ⪯ (ax + b)h and h ⪯ x(x + 1)h′ we have by the discussion following Lemma 9 that h ⪯ ϕ(f^{(d−1)}). If θ is a common zero of h and ϕ(f^{(d−1)}), then θ(θ + 1)h′(θ) = 0, which is impossible since θ ∈ (−1, 0) and h′(θ) ≠ 0. Thus ϕ(f^{(d)}) ≺ ϕ(f^{(d−1)}), which verifies condition (iii) of Definition 3. Given ξ ∈ ℝ we have

L_{ϕ}(f)(ξ, z) = ∑_{n} \frac{h^{(n)}(ξ)}{n!n!}ξ^{n}(ξ + 1)^{n} \frac{d^{n}f(ξ + z)}{dz^{n}}

= H_{ξ}(\frac{d}{dz})f(ξ + z),

where

H_{ξ}(x) = ∑_{n} \frac{h^{(n)}(ξ)}{n!n!}\{ξ(ξ + 1)x\}^{n}.

By Theorem 11 H_{ξ} is real-rooted, which by Theorem 10 verifies condition (iv).

Suppose that ξ is a common zero of ϕ(f′) and ϕ(f). From the definition of the diamond product it follows that ξ ∉ {0, −1}, so x^{2} ∤ H_{ξ}(x). Since ξ is supposed to be a common zero of ϕ(f′) and ϕ(f) we have, by (1), that 0 is a multiple zero of L_{ϕ}(f)(ξ, z). It follows from Theorem 10 that 0 is a multiple zero of f(z + ξ), that is, ξ is a multiple zero of f, contrary to assumption that f is simple-rooted. This verifies condition (ii), and we can conclude that f ∈ 𝒜^{+}(ϕ). Part (b) of the theorem now follows from Theorem 8.

If h is merely [−1, 0]-rooted and f is real-rooted then we can find polynomials h_{n} and f_{n} whose limits are h and f respectively, such that h_{n} and f_{n} are real- and simple-rooted and h_{n} is (−1, 0)-rooted. Now, f_{n}◇h_{n} is realrooted by the above and, by continuity, so is f◇g. The proof now follows from Theorem 8. □

There are many products on polynomials for which a similar proof applies. With minor changes in the above proof, Theorem 12 also holds for the product

(f, g) → ∑_{n≥0} \frac{f^{(n)}(x)g^{(n)}(x)}{n!}x^{n}(x + 1)^{n}.

3. Interlacing zeros and the Neggers-Stanley Conjecture

Let P be any finite poset of cardinality p. An injective function ω : P → ℕ is called a labelling of P and (P, ω) is a called a labelled poset. A (P, ω)- partition with largest part ≤ n is a map σ : P → [n] such that

• σ is order reversing, that is, if x ≤ y then σ(x) ≥ σ(y),

• if x < y and ω(x) > ω(y) then σ(x) > σ(y). The number of (P, ω)-partitions with largest part ≤ n is denoted Ω(P, ω, n) and is easily seen to be a polynomial in n. Indeed, if we let e_{k}(P, ω) be the number of surjective (P, ω)-partitions σ : P → [k], then by a simple counting argument we have:

Ω(P, ω, x) = ∑_{k=1}^{|P |} e_{k}(P, ω)\binom{x}{k}.  (4)

The polynomial Ω(P, ω, x) is called the order polynomial of (P, ω). The Epolynomial of (P, ω) is the polynomial

E(P, ω) = ∑_{k=1}^{p} e_{k}(P, ω)x^{k},

so E(P, ω) is the image of Ω(P, ω, x) under the invertible linear operator E : ℝ[x] → ℝ[x] which takes \binom{x}{k} to x^{k}. The Neggers-Stanley Conjecture asserts that the polynomial E(P, ω) is real-rooted for all choices of P and ω. The conjecture has been verified for series-parallel posets [13], column-strict labelled Ferrers posets [1] and for all labelled posets having at most seven elements.

There are two operations on labelled posets under which E-polynomials behave well. The first operation is the ordinal sum:

Let (P, ω) and (Q, ν) be two labelled posets. The ordinal sum, P ⊕ Q, of P and Q is the poset with the disjoint union of P and Q as underlying set and with partial order defined by x ≤ y if either x ≤_{P} y, x ≤_{Q} y, or x ∈ P, y ∈ Q. For i = 0, 1 let ω ⊕_{i} ν be any labellings of P ⊕ Q such that

• (ω⊕_{0}ν)(x) < (ω⊕_{0}ν)(y) if ω(x) < ω(y), ν(x) < ν(y) or x ∈ P, y ∈ Q.

• (ω⊕_{1}ν)(x) < (ω⊕_{1}ν)(y) if ω(x) < ω(y), ν(x) < ν(y) or x ∈ Q, y ∈ P. The following result follows easily by combinatorial reasoning: Proposition 13. Let (P, ω) and (Q, ν) be as above. Then

E(P ⊕ Q, ω ⊕_{1} ν) = E(P, ω)E(Q, ν)

and

xE(P ⊕ Q, ω ⊕_{0} ν) = (x + 1)E(P, ω)E(Q, ν),

if P and Q are nonempty.

Proof. See [1, 13]. □

The disjoint union, P ⊔ Q, of P and Q is the poset on the disjoint union with x < y in P ⊔ Q if and only if x <_{P} y or x <_{Q} y. Let ω ⊔ ν be any labelling of P ⊔ Q such that

(ω ⊔ ν)(x) < (ω ⊔ ν)(y),

if ω(x) < ω(y) or ν(x) < ν(y). It is immediate by construction that

Ω(P ⊔ Q, ω ⊔ ν) = Ω(P, ω)Ω(Q, ν)

Here is where the diamond product comes in. Wagner [13] showed that the diamond product satisfies

f◇g = E(E^{−1}(f)E^{−1}(g)),  (5)

which implies:

E(P ⊔ Q, ω ⊔ ν) = E(P, ω)◇E(Q, ν),  (6)

for all pairs of labelled posets (P, ω) and (Q, ν).

If P is nonempty and x ∈ P we let P \ x be the poset on P \ {x} with the order inherited by P. If (P, ω) is labelled then P \ x is labelled with the restriction of ω to P \ x. By a slight abuse of notation we will write (P \ x, ω) for this labelled poset. A series-parallel labelled poset (S, μ) is either the empty poset, a one element poset or

(a) (S, μ) = (P ⊕ Q, ω ⊕_{0} ν),

(b) (S, μ) = (P ⊕ Q, ω ⊕_{1} ν) or

(c) (S, μ) = (P ⊔ Q, ω ⊔ ν) where (P, ω) and (Q, ν) are series-parallel. Note that if (S, μ) is series-parallel then so is (S \ x, μ) for all x ∈ S. Let ℐ denote the class of all finite labelled posets (S, μ) such that E(S, μ) is real-rooted and

E(S \ x, μ) ⪯ E(S, μ),

for all x ∈ S. Note that the empty poset and the singleton posets are members of ℐ which by the following theorem gives that series-parallel posets are in ℐ. Theorem 14. The class ℐ is closed under ordinal sum and disjoint union.

Figure 1. From left to right: A column-strict labelling ω of P_{λ} with λ = (3, 2, 2, 1), a (P_{λ}, ω)-partition and the corresponding reverse SSYT.

8 7 6 5 4 3 2 1  9 10 9 7 10 8 7 2  10 10 9 8 9 7 7 2

Proof. Suppose that (P, ω), (Q, ν) ∈ ℐ. (a): Let (S, μ) = (P ⊕ Q, ω ⊕_{0} ν). Now, if y ∈ P we have

(S \ y, μ) = (P \ y ⊕ Q, ω ⊕_{0} ν).

If |P | = 1 then by Proposition 13 we have E(S \ y, μ) = E(Q, ν) and E(S, μ) = (x + 1)E(Q, ν) so E(S \ y, μ) ⪯ E(S, μ). If |P | > 1 then

xE(S \ y, μ) = (x + 1)E(P \ y, ω)E(Q, ν)
⪯ (x + 1)E(P, ω)E(Q, ν)
= xE(S, μ),

which gives E(S \ y, μ) ⪯ E(S, μ). A similar argument applies to the case y ∈ Q. (b): The case (S, μ) = (P ⊕ Q, ω ⊕_{0} ν) follows as in (a). (c): (S, μ) = (P ⊔ Q, ω ⊔ ν). If y ∈ P we have by (6) and Theorem 12:

E(S \ y, μ) = E(P \ y ⊔ Q, ω ⊔ ν)
= E(P \ y, ω)◇E(Q, ν)
⪯ E(P, ω)◇E(Q, ν)
= E(S, μ).

This proves the theorem. □

In [11] Simion proved a special case of the following corollary. Namely the case when S is a disjoint union of chains and μ is order-preserving. Corollary 15. If (S, μ) is series-parallel and x ∈ S then

E(S \ x, μ) ⪯ E(S, μ).

Next we will analyse interlacings of E-polynomials of Ferrers posets. For undefined terminology in what follows we refer the reader to [12, Chapter 7]. Let λ = (λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{ℓ} > 0) be a partition. The Ferrers poset P_{λ} is the poset

P_{λ} = {(i, j) ∈ ℙ × ℙ : 1 ≤ i ≤ ℓ, 1 ≤ j ≤ λ_{i}},

ordered by the standard product ordering. A labelling ω of P_{λ} is column strict if ω(i, j) > ω(i + 1, j) and ω(i, j) < ω(i, j + 1) for all (i, j) ∈ P_{λ}. If ω is a column strict labelling then any (P_{λ}, ω)-partition must necessarily be strictly decreasing in the x-direction and weakly decreasing in the y-direction. It follows that the (P_{λ}, ω)-partitions are in a one-to-one correspondence with with the reverse SSYT’s of shape λ (see Figure 1). The number of reverse SSYT’s of shape λ with largest part ≤ n is by the combinatorial definition of the Schur function equal to s_{λ}(1^{n}) which by the hook-content formula [12, Corollary 7.21.4] gives us.

Ω(P_{λ}, ω, z) = ∏_{u∈P_{λ}} \frac{z + c_{λ}(u)}{h_{λ}(u)},  (7)

where for u = (x, y) ∈ P_{λ}

h_{λ}(u) := |{(x, j) ∈ λ : j ≥ y}| + |{(i, y) ∈ λ : i ≥ x}| − 1

and c_{λ}(u) := y −x are the hook length respectively content at u. In [1] Brenti showed that the E-polynomials of column strict labelled Ferrers posets are real-rooted. In the next theorem we refine this result. If x < y in a poset P and x < z < y for no z ∈ P we say that y covers x. If we remove an element from P_{λ} the resulting poset will not necessarily be a Ferrers poset. But if we remove a maximal element m from P_{λ} we will have P_{λ} \ m = P_{μ} for a partition μ covered by λ in the Young’s lattice. Theorem 16. Let (P_{λ}, ω) be labelled column strict. Then E(P_{λ}, ω) is realrooted. Moreover, if λ covers μ in the Young’s lattice, then

E(P_{μ}, ω) ⪯ E(P_{λ}, ω).

Proof. The proof is by induction over n, where λ ⊢ n. It is trivially true for n = 1. If λ ⊢ n + 1 and λ covers μ we have that P_{λ} = P_{μ} ∪ {m} for some maximal element m ∈ P_{λ}. By definition c_{μ}(u) = c_{λ}(u) for all u ∈ P_{μ}, so by (7) we have that for some C > 0:

Ω(P_{λ}, ω, x) = C(x + c_{λ}(m))Ω(P_{μ}, ω, x),

and by (5):

E(P_{λ}, ω) = C(x + c_{λ}(m))◇E(P_{μ}, ω).

Wagner [13] showed that all real zeros of E-polynomials are necessarily in [−1, 0], so by induction we have that E(P_{μ}, ω) is [−1, 0]-rooted. By Theorem 12 this suffices to prove the theorem. □

References

[1] F. Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413):viii+106, 1989.

[2] J. Dedieu. Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials? J. Pure Appl. Algebra, 81(3):269–278, 1992.

[3] C. D. Godsil. Algebraic combinatorics. Chapman and Hall Mathematics Series. Chapman & Hall, New York, 1993.

[4] O. J. Heilmann and E. H. Lieb. Theory of monomer-dimer systems. Comm. Math. Phys., 25:190–232, 1972.

[5] B. Ja. Levin. Distribution of zeros of entire functions. American Mathematical Society, Providence, R.I., 1964.

[6] M. Marden. Geometry of polynomials. Second edition. Mathematical Surveys, No. 3. American Mathematical Society, Providence, R.I., 1966.

[7] A. Nijenhuis. On permanents and the zeros of rook polynomials. J. Combinatorial Theory Ser. A, 21(2):240–244, 1976.

[8] N. Obreschkoff. Verteilung und Berechnung der Nullstellen reeller Polynome. VEB Deutscher Verlag der Wissenschaften, Berlin, 1963.

[9] V. Reiner and V. Welker. On the Charney-Davis and the Neggers-Stanley conjectures. http://www.math.umn.edu/ reiner/Papers/papers.html, 2002.

[10] J. Schur. Zwei sätze über algebraische gleichungen mit lauter reellen wurzeln. J. Reine Angew. Math., 144(2):75–88, 1914.

[11] R. Simion. A multi-indexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences. J. Combin. Theory Ser. A, 36(1):15–22, 1984.

[12] R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

[13] D. G. Wagner. Enumeration of functions from posets to chains. European J. Combin., 13(4):313–324, 1992.

[14] D. G. Wagner. Total positivity of Hadamard products. J. Math. Anal. Appl., 163(2):459–483, 1992.

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

E-mail address: branden@math.chalmers.se