Counterexamples for the Poset Conjectures

John Stembridge
University of Michigan
November 2004

I: Overview

If P is a partial ordering of 1,2,...,n, then the W-polynomial of P is the generating function

   W(P,t) := Sum t^(1+d(w))

where w ranges over the linear extensions of P and d(w) denotes the number of descents in w. Similarly, the W-bar-polynomial of P is the generating function

   W'(P,t) := Sum t^(1+p(w))

where p(w) denotes the number of peaks in w.

In 1978, Joseph Neggers conjectured that if P is naturally labeled (i.e., if i is below j in the poset, then i < j in the usual ordering of the integers), then all zeros of W(P,t) should be real. In particular, this would imply that the coefficients of W(P,t) must be log-concave.

In 1986, Richard Stanley conjectured that the same thing should be true without the hypothesis that P is naturally labeled.

In 1997, I conjectured that the same thing should be true for W'(P,t)   (see this paper).

Recently, Petter Brändén showed that Stanley's conjecture is false (see his preprint).

This motivated me to conduct systematic searches that have yielded counterexamples to all three conjectures. More specifically, we have discovered that there exist NRZ-posets on 10 vertices (i.e., posets whose W-polynomials have non-real zeros), NRZ-bar-posets on 11 vertices (i.e., posets whose W-bar-polynomials have non-real zeros), naturally labeled NRZ-posets on 17 vertices, and naturally labeled NRZ-bar-posets on 18 vertices. The purpose of this document is to provide access to these posets and the software that produced them.

For more information, including an explanation of the algorithms and theory that guided the search, see the accompanying preprint [PDF].

The Maple programs used to find the examples, as well as the output files and log files are available in this gzipped tar archive: poc.tar.gz.

II: NRZ posets on 10 points

Up to a natural "equivalence" (see the paper for the definition), there are 48 NRZ-posets on 10 points that are "narrow" in the sense that they may be partitioned into two chains. (There are no NRZ-posets with fewer vertices, but there could also be non-narrow NRZ posets on 10 vertices.) These 48 may be further grouped into 8 "shift-equivalence" classes, and these 8 shift-classes involve only four distinct isomorphism classes of posets.

We list 44 of the 48 equivalence classes of posets below, together with their W-polynomials. The four that are missing may be obtained by taking the duals of the four in Family #3. In each case, we first list a set P of covering pairs for a poset from the isomorphism class of this family (this poset is not NRZ), followed by a line-by-line listing of the form 

W-polynomial    edge subset of P
where the edge subset E indicates that to obtain a representative from this equivalence class, you have to renumber the vertices so that each member of E has the form [i,j] where i > j, and each member of P-E has the form [i,j] where i < j. If E includes more than half of the covering edges of P, we display the complement of E, prepended with P-.

Some nice NRZ-posets from this collection are displayed in Figure 4 of the paper.

Family #1:

P = {[8, 9], [7, 8], [4, 5], [3, 4], [1, 2], [2, 3], [9, 10],
     [2, 9], [8, 5], [4, 10], [6, 3], [6, 7], [1, 7], [7, 4]}

shift-equivalence class #1: 
11*t^7+41*t^6+46*t^5+14*t^4+t^3   {[2,3],[4,5],[4,10],[7,4],[7,8],[8,9]}
11*t^7+41*t^6+46*t^5+14*t^4+t^3   {[1,7],[2,3],[4,5],[4,10],[6,7],[8,9]}
11*t^7+41*t^6+46*t^5+14*t^4+t^3   {[1,7],[2,3],[3,4],[6,7],[7,4],[8,9]}
11*t^8+41*t^7+46*t^6+14*t^5+t^4   P-{[1,2],[2,9],[6,3],[8,5],[8,9]}
11*t^8+41*t^7+46*t^6+14*t^5+t^4   P-{[2,3],[2,9],[6,3],[8,5],[9,10]}
11*t^8+41*t^7+46*t^6+14*t^5+t^4   P-{[1,2],[2,9],[6,3],[7,8]}
11*t^8+41*t^7+46*t^6+14*t^5+t^4   P-{[2,9],[3,4],[8,5],[9,10]}
11*t^8+41*t^7+46*t^6+14*t^5+t^4   P-{[1,2],[6,3],[8,5],[9,10]}

shift-equivalence class #2: 
t^7+14*t^6+46*t^5+41*t^4+11*t^3   {[1,2],[2,9],[6,3],[7,8]}
t^7+14*t^6+46*t^5+41*t^4+11*t^3   {[2,9],[3,4],[8,5],[9,10]}
t^7+14*t^6+46*t^5+41*t^4+11*t^3   {[1,2],[6,3],[8,5],[9,10]}
t^7+14*t^6+46*t^5+41*t^4+11*t^3   {[1,2],[2,9],[6,3],[8,5],[8,9]}
t^7+14*t^6+46*t^5+41*t^4+11*t^3   {[2,3],[2,9],[6,3],[8,5],[9,10]}
t^8+14*t^7+46*t^6+41*t^5+11*t^4   P-{[2,3],[4,5],[4,10],[7,4],[7,8],[8,9]}
t^8+14*t^7+46*t^6+41*t^5+11*t^4   P-{[1,7],[2,3],[4,5],[4,10],[6,7],[8,9]}
t^8+14*t^7+46*t^6+41*t^5+11*t^4   P-{[1,7],[2,3],[3,4],[6,7],[7,4],[8,9]}

Family #2:

P = {[8, 9], [7, 8], [4, 5], [3, 4], [1, 2], [2, 3], [9, 10],
     [2, 9], [8, 5], [4, 10], [6, 3], [6, 7], [1, 7]}

shift-equivalence class #1: 
11*t^7+42*t^6+50*t^5+18*t^4+t^3   {[2,3],[3,4],[7,8],[8,9]}
11*t^7+42*t^6+50*t^5+18*t^4+t^3   {[2,3],[4,5],[4,10],[7,8],[8,9]}
11*t^7+42*t^6+50*t^5+18*t^4+t^3   {[1,7],[2,3],[3,4],[6,7],[8,9]}
11*t^7+42*t^6+50*t^5+18*t^4+t^3   {[1,7],[2,3],[4,5],[4,10],[6,7],[8,9]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[1,2],[1,7],[2,9],[6,3],[6,7]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[2,9],[4,5],[4,10],[8,5],[9,10]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[1,2],[2,9],[6,3],[8,5],[8,9]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[2,3],[2,9],[6,3],[8,5],[9,10]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[1,2],[2,9],[6,3],[7,8]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[2,9],[3,4],[8,5],[9,10]}
11*t^8+42*t^7+50*t^6+18*t^5+t^4   P-{[1,2],[6,3],[8,5],[9,10]}
11*t^9+42*t^8+50*t^7+18*t^6+t^5   P-{[2,9]}

shift-equivalence class #2: 
t^6+18*t^5+50*t^4+42*t^3+11*t^2   {[2,9]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[1,2],[2,9],[6,3],[7,8]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[2,9],[3,4],[8,5],[9,10]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[1,2],[6,3],[8,5],[9,10]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[1,2],[1,7],[2,9],[6,3],[6,7]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[2,9],[4,5],[4,10],[8,5],[9,10]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[1,2],[2,9],[6,3],[8,5],[8,9]}
t^7+18*t^6+50*t^5+42*t^4+11*t^3   {[2,3],[2,9],[6,3],[8,5],[9,10]}
t^8+18*t^7+50*t^6+42*t^5+11*t^4   P-{[1,7],[2,3],[4,5],[4,10],[6,7],[8,9]}
t^8+18*t^7+50*t^6+42*t^5+11*t^4   P-{[2,3],[4,5],[4,10],[7,8],[8,9]}
t^8+18*t^7+50*t^6+42*t^5+11*t^4   P-{[1,7],[2,3],[3,4],[6,7],[8,9]}
t^8+18*t^7+50*t^6+42*t^5+11*t^4   P-{[2,3],[3,4],[7,8],[8,9]}

Family #3

P = {[8, 9], [1, 8], [7, 8], [4, 5], [3, 4], [1, 2], [7, 3],
     [2, 3], [9, 5], [2, 10], [9, 10], [8, 4], [5, 6]}

shift-equivalence class #1:
12*t^8+39*t^7+35*t^6+5*t^5   P-{[1,2],[2,10],[7,3],[9,5],[9,10]}
12*t^8+39*t^7+35*t^6+5*t^5   P-{[1,2],[2,10],[7,3],[8,9]}

shift-equivalence class #2:
5*t^6+35*t^5+39*t^4+12*t^3   {[1,2],[2,10],[7,3],[8,9]}
5*t^6+35*t^5+39*t^4+12*t^3   {[1,2],[2,10],[7,3],[9,5],[9,10]}

III: NRZ-bar posets on 11 points

Up to equivalence, there are 10 NRZ-bar posets on 11 points that are narrow. There might also be non-narrow NRZ-bar posets on 9, 10 or 11 points, but we have not tested for this possibility.

We have listed five of the 10 equivalence classes below, following the same format as in the previous section. The remaining five are the duals of these.

Some nice NRZ-bar posets from this collection are displayed in Figure 5 of the paper.

Family #1:

P = {[1, 2], [1, 7], [4, 5], [3, 10], [7, 4], [10, 11], [5, 11], [7, 8],
     [2, 8], [3, 4], [9, 6], [2, 3], [8, 9], [5, 6], [9, 10]}

t^6+18*t^5+50*t^4+42*t^3+11*t^2   {[3,10]}
t^6+18*t^5+50*t^4+42*t^3+11*t^2   {[1,7],[3,10]}
t^6+18*t^5+50*t^4+42*t^3+11*t^2   {[1,2],[3,10]}

Family #2:

P = {[1, 2], [4, 5], [10, 11], [7, 8], [3, 4], [2, 3], [8, 9], [5, 6],
     [9, 10], [1, 8], [7, 3], [9, 5], [2, 10], [4, 11]}

t^6+27*t^5+89*t^4+82*t^3+23*t^2   P-{[2,10],[5,6]}
t^6+27*t^5+89*t^4+82*t^3+23*t^2   P-{[2,10]}

IV: Naturally labeled NRZ posets on 17 points

There are 58 isomorphism classes of narrow posets on 17 points whose natural labelings are NRZ. We can break these 58 into a dual pair of families, and representatives from the 29 isomorphism classes in one of the families are listed below.

The posets turn out to be very similar to each other: all 29 representatives may be chosen so as to include the following covering relations: 

P = {[16, 17], [4, 13], [6, 15], [4, 6], [2, 4], [14, 16], [12, 14],
     [1, 4], [1, 3], [13, 17], [3, 5], [5, 7], [7, 9], [9, 11],
     [13, 15], [11, 13], [10, 12], [6, 8], [8, 10], [2, 11]}
and the remaining covering relations are always subsets of 
  {[5, 6], [7, 8], [3, 6], [11, 16], [9, 14], [9, 10], [3, 8],
   [7, 12], [7, 10], [9, 12], [11, 14], [5, 8], [5, 10]}
See Figure 6 of the paper for a nice illustration.

Here, we list the 29 posets and their W-polynomials, sorted in order of increasing numbers of linear extensions. The format is 

index [coeffs of the W-polynomial]  Extra covering edges
The "Extra covering edges" are the those that need to be added to P to generate the poset. Note that the lowest term of the W-polynomial of a naturally labeled poset is t, so the first coefficient listed is always 1.

The naturally labeled NRZ-bar posets we found are obtained by adjoining minimum elements to these NRZ posets. 

 1  [1 29 283 1122 1846 1239 336 27]    {[5,6],[7,8],[9,10],[11,14]}        

 2  [1 30 298 1189 1968 1332 365 30]    {[5,6],[7,8],[9,10],[11,16]}        

 3  [1 30 299 1202 1998 1350 363 27]    {[5,6],[9,10],[11,14]}              

 4  [1 31 315 1277 2139 1457 395 30]    {[5,6],[9,10],[11,16]}              

 5  [1 31 316 1301 2234 1601 477 45]    {[5,6],[7,10],[9,12],[11,14]}       

 6  [1 31 318 1309 2251 1615 480 45]    {[3,6],[5,8],[9,10],[11,14]}        

 7  [1 32 329 1355 2316 1649 486 45]    {[5,6],[9,12],[11,14]}              

 8  [1 32 332 1365 2337 1664 489 45]    {[3,6],[9,10],[11,14]}              

 9  [1 32 330 1365 2347 1679 495 45]    {[5,6],[7,10],[11,14]}              

10  [1 32 333 1388 2419 1771 543 54]    {[5,6],[7,10],[9,12],[11,16]}       

11  [1 33 344 1429 2460 1757 513 45]    {[5,6],[7,12],[11,14]}              

12  [1 34 354 1460 2490 1766 513 45]    {[5,6],[11,14]}                     

13  [1 33 348 1464 2576 1912 595 60]    {[5,6],[7,10],[9,14],[11,16]}       

14  [1 32 336 1420 2534 1946 658 86 3]  {[3,6],[5,8],[7,10],[9,12],[11,14]} 

15  [1 34 360 1508 2639 1946 601 60]    {[5,6],[7,10],[11,16]}              

16  [1 33 351 1487 2656 2039 687 89 3]  {[3,6],[7,10],[9,12],[11,14]}       

17  [1 34 363 1537 2716 2023 630 63]    {[5,6],[7,12],[9,14],[11,16]}       

18  [1 33 351 1493 2674 2057 693 89 3]  {[3,6],[5,8],[7,10],[11,14]}        

19  [1 33 354 1504 2683 2060 693 89 3]  {[5,8],[7,10],[9,12],[11,14]}       

20  [1 35 376 1589 2798 2071 639 63]    {[5,6],[7,12],[11,16]}              

21  [1 34 370 1584 2837 2182 731 92 3]  {[5,8],[7,10],[11,14]}              

22  [1 34 366 1569 2831 2198 745 95 3]  {[3,6],[5,8],[7,12],[11,14]}        

23  [1 34 370 1584 2847 2203 745 95 3]  {[3,8],[7,10],[9,12],[11,14]}       

24  [1 35 377 1608 2880 2221 748 95 3]  {[3,6],[5,8],[11,14]}               

25  [1 35 383 1626 2897 2226 748 95 3]  {[7,10],[9,12],[11,14]}             

26  [1 35 387 1673 3026 2347 789 98 3]  {[3,8],[7,10],[11,14]}              

27  [1 36 401 1721 3084 2373 792 98 3]  {[7,10],[11,14]}                    

28  [1 36 404 1772 3262 2598 903 116 3] {[3,8],[5,10],[7,12],[11,14]}       

29  [1 37 417 1826 3350 2654 915 116 3] {[3,8],[7,12],[11,14]}
This page last modified Mon Nov 29 15:30:17 EST 2004
Links updated Mon Aug 5 14:41:13 EDT 2024