ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 10, Pages 155–158 (December 24, 2004) S 1079-6762(04)00140-4

COUNTEREXAMPLES TO THE NEGGERS-STANLEY CONJECTURE

PETTER BRÄNDÉN

(Communicated by Sergey Fomin)

Abstract. The Neggers-Stanley conjecture asserts that the polynomial counting the linear extensions of a labeled finite partially ordered set by the number of descents has real zeros only. We provide counterexamples to this conjecture.

A finite partially ordered set (poset) P of cardinality p is said to be labeled if its elements are identified with the integers 1, 2, …, p. We will use the symbol ≺ to denote the partial order on P and < to denote the usual order on the integers. The Jordan-Hölder set L(P) is the set of permutations π = (π_{1}, …, π_{p}) of [p] =^{def} {1, 2, …, p} which encode the linear extensions of P. More precisely, π ∈ L(P) if π_{i} ≺ π_{j} implies i < j.

A descent in a permutation π is an index i such that π_{i} > π_{i+1}. Let des(π) denote the number of descents in π. The W -polynomial of a labeled poset P is defined by

W (P, t) = ∑_{π∈L(P)} t^{des(π)}.

W -polynomials appear naturally in many combinatorial contexts [2, 7, 8], and are connected to Hilbert series of the Stanley-Reisner rings of simplicial complexes [10, Section III.7] and algebras with straightening laws [9, Theorem 5.2.].

Example 1. Let P_{2,2} be the labeled poset shown in Figure 1. Then

L(P_{2,2}) = {(1, 3, 2, 4), (1, 3, 4, 2), (3, 1, 2, 4), (3, 1, 4, 2), (3, 4, 1, 2)},

so W (P_{2,2}, t) = 4t + t^{2}.

P_{2,2} = [figure: 2; 4; 1; 3]

Figure 1. The poset P_{2,2}.

\begin{matrix}c \\ ◯ \end{matrix}2004 American Mathematical Society

Reverts to public domain 28 years from publication

Received by the editors August 31, 2004.

2000 Mathematics Subject Classification. Primary 06A07, 26C10.

Key words and phrases. Neggers-Stanley conjecture, partially ordered set, linear extension, real roots.

When P is a p-element antichain, then L(P) consists of all permutations of [p], and W (P, t) is the pth Eulerian polynomial. The Eulerian polynomials are known [3] to have only real zeros. In this instance, the Neggers-Stanley conjecture holds:

Conjecture 1 (Neggers-Stanley). For any finite labeled poset P, all zeros of the polynomial W (P, t) are real.

A poset P is naturally labeled if i ≺ j implies i < j. Conjecture 1 was made by J. Neggers [4] in 1978 for naturally labeled posets, and extended by R. P. Stanley in 1986 to arbitrary labelings. It has been proved in some special cases (see [2, 11]). A weaker unimodality property of W -polynomials was recently proved [6] (see also [1]) for graded naturally labeled posets.

In this note, we construct counterexamples to Conjecture 1 utilizing the following construction. Let m ⊔ n denote the disjoint union of the chains 1 ≺ 2 ≺ ⋯ ≺ m and m + 1 ≺ m + 2 ≺ ⋯ ≺ m + n. Let P_{m,n} be the labeled poset obtained by adding the relation m + 1 ≺ m to the relations in m ⊔ n; see Figure 2.

P_{3,4} = [figure: 7; 3; 6; 2; 5; 1; 4]

Figure 2. The poset P_{3,4}.

Theorem 1. Let M be a positive integer. The polynomial W (P_{m,n}, t) has more than M non-real zeros provided min(m, n) is sufficiently large.

The posets P_{m,n} are not naturally labeled, so the original conjecture of Neggers remains open.

The rest of the paper is devoted to the proof of Theorem 1. At the end, we discuss specific (minimal) counterexamples obtained from Theorem 1.

Lemma 1. W (P_{m,n}, t) = ∑_{k=1}^{min(n,m)} \binom{m}{k}\binom{n}{k}t^{k}.

Proof. Let π = (π_{1}, π_{2}, …) be a permutation. If i is a descent in π, we say that π_{i} is a descent top and π_{i+1} is a descent bottom. Any π ∈ L(m⊔n) is uniquely determined by its descent tops (which are necessarily elements of [m + n] \ [m]) and descent bottoms (which are elements of [m]). It follows that the number of permutations in L(m ⊔ n) with exactly k descents is \binom{m}{k}\binom{n}{k}, implying that W (m ⊔ n, t) = ∑_{k=0}^{min(n,m)} \binom{m}{k}\binom{n}{k}t^{k}. Since the only element of L(m⊔n)\L(P_{m,n}) is (1, 2, …, m+n), we have W (m ⊔ n, t) = 1 + W (P_{m,n}, t), and Lemma 1 follows. □

We note that all zeros of W (m ⊔ n, t) are real and simple (R. Simion [7]).

Proof of Theorem 1. Recall that the Bessel function of order 0 is given by

(2)  J_{0}(z) = \frac{2}{π} ∫_{0}^{1} \frac{cos(zt)}{\sqrt{1 − t^{2}}} dt = ∑_{k=0}^{∞} \frac{1}{k!k!} (\frac{−z^{2}}{2} )^{k} .

It is known that J_{0}(z) has infinitely many zeros, all of which are real and simple. It follows from (2) that |J_{0}(θ)| ≤ 1 for all real θ, with equality only if θ = 0. Hence the function

F (z) = ∑_{k=0}^{∞} \frac{1}{k!k!}z^{k}

has infinitely many zeros, all of them negative and simple. Also, |F (θ)| < 1 for θ < 0.

Let f_{m,n}(z) = W (P_{m,n}, z/mn). Then

f_{m,n}(z) = ∑_{k=1}^{min(m,n)} \frac{(1 − \frac{1}{n})(1 − \frac{2}{n}) ⋯ (1 − \frac{k−1}{n})}{k!} \frac{(1 − \frac{1}{m})(1 − \frac{2}{m}) ⋯ (1 − \frac{k−1}{m})}{k!} z^{k}.

Let m_{1}, n_{1}, m_{2}, n_{2}, … be positive integers such that lim_{j→∞} min(m_{j}, n_{j}) = ∞. Then

lim_{j→∞} f_{m_{j},n_{j}}(z) + 1 = F (z),

where the convergence is uniform on any compact subset of ℂ. Let (−a, 0) be an interval containing more than M zeros of F (z). It follows from Hurwitz’s theorem [5, Theorem 1.3.8] that the polynomial f_{m_{j},n_{j}}(z) + 1 has more than M zeros in (−a, 0) for sufficiently large j. By continuity we also have |f_{m_{j},n_{j}}(z) + 1| < 1 for z ∈ (−a, 0) and j large. Thus by subtracting 1 from f_{m_{j},n_{j}}(z) + 1, we will lose at least M real zeros. □

By applying Sturm’s Theorem [5, Section 10.5], one can find specific counterexamples. The polynomial W (P_{11,11}, t) has two non-real zeros which are approximately

z = −0.10902 ± 0.01308i.

A counterexample with a polynomial of lower degree is

W (P_{36,6}, t) = 216t + 9450t^{2} + 142800t^{3} + 883575t^{4} + 2261952t^{5} + 1947792t^{6}.

This polynomial has two non-real zeros.

References

[1] P. Brändén, Sign-graded posets, unimodality of W -polynomials and the Charney-Davis conjecture, Electr. J. Combin. 11(2), #9.

[2] F. Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 413, Amer. Math. Soc., Providence, 1989. MR0963833 (90d:05014)

[3] L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 (1967), 410–414. MR0211432 (35:2312)

[4] J. Neggers, Representations of finite partially ordered sets, J. Comb. Inf. Syst. Sci. 3 (1978), 113–133. MR0551484 (58:27668)

[5] Q. I. Rahman and G. Schmeisser, Analytic theory of polynomials, The Clarendon Press, Oxford University Press, Oxford, 2002. MR1954841 (2004b:30015)

[6] V. Reiner and V. Welker, On the Charney-Davis and Neggers-Stanley conjectures, preprint;

   available at www.math.umn.edu/~reiner/.

[7] R. Simion, A multiindexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences. J. Comb. Theory, Ser. A 36 (1984), 15–22. MR0728500 (85e:05015)

[8] R. P. Stanley, Ordered structures and partitions, Mem. Amer. Math. Soc. 119, Amer. Math. Soc., Providence, 1972. MR0332509 (48:10836)

[9] R. P. Stanley, Hilbert functions of graded algebras, Adv. Math. 28 (1978), 57–83. MR0485835 (58:5637)

[10] R. P. Stanley, Combinatorics and commutative algebra, Birkhäuser Boston Inc., Boston, MA, 2nd edition, 1996. MR1453579 (98h:05001)

[11] D. Wagner, Enumeration of functions from posets to chains, Eur. J. Comb. 13 (1992), 313– 324. MR1179527 (94c:05008)

Department of Mathematics, Chalmers University of Technology and Göteborg University, S-412 96 Göteborg, Sweden

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