Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge

Stembridge, John

doi:10.1090/S0002-9947-06-04271-1

Counterexamples to the poset conjectures of Neggers, Stanley, and Stembridge
HTML articles powered by AMS MathViewer

by John R. Stembridge PDF

Trans. Amer. Math. Soc. 359 (2007), 1115-1128 Request permission

Abstract:

We provide the first counterexamples to Neggers’ 1978 conjecture and Stembridge’s 1997 conjecture that the generating functions for descents and peaks in the linear extensions of naturally labeled posets should have all real zeros. We also provide minimum-sized counterexamples to a generalization of the Neggers conjecture due to Stanley that was recently disproved by Brändén.

References

Anders Björner and Jonathan David Farley, Chain polynomials of distributive lattices are $75%$ unimodal, Electron. J. Combin. 12 (2005), Note 4, 7. MR 2134190
Petter Brändén, On operators on polynomials preserving real-rootedness and the Neggers-Stanley conjecture, J. Algebraic Combin. 20 (2004), no. 2, 119–130. MR 2104673, DOI 10.1023/B:JACO.0000047295.93525.df
Petter Brändén, Sign-graded posets, unimodality of $W$-polynomials and the Charney-Davis conjecture, Electron. J. Combin. 11 (2004/06), no. 2, Research Paper 9, 15. MR 2120105
Petter Brändén, Counterexamples to the Neggers-Stanley conjecture, Electron. Res. Announc. Amer. Math. Soc. 10 (2004), 155–158. MR 2119757, DOI 10.1090/S1079-6762-04-00140-4
Francesco Brenti, Unimodal, log-concave and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. 81 (1989), no. 413, viii+106. MR 963833, DOI 10.1090/memo/0413
Gunnar Brinkmann and Brendan D. McKay, Posets on up to 16 points, Order 19 (2002), no. 2, 147–179. MR 1922916, DOI 10.1023/A:1016543307592
Vesselin Gasharov, On the Neggers-Stanley conjecture and the Eulerian polynomials, J. Combin. Theory Ser. A 82 (1998), no. 2, 134–146. MR 1620853, DOI 10.1006/jcta.1997.2839
Samuel K. Hsiao, A signed analog of the Birkhoff transform, J. Combin. Theory Ser. A 113 (2006), no. 2, 251–272. MR 2199274, DOI 10.1016/j.jcta.2005.03.003
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Joseph Neggers, Representations of finite partially ordered sets, J. Combin. Inform. System Sci. 3 (1978), no. 3, 113–133. MR 551484
Victor Reiner and Volkmar Welker, On the Charney-Davis and Neggers-Stanley conjectures, J. Combin. Theory Ser. A 109 (2005), no. 2, 247–280. MR 2121026, DOI 10.1016/j.jcta.2004.09.003
Rodica Simion, A multi-indexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences, J. Combin. Theory Ser. A 36 (1984), no. 1, 15–22. MR 728500, DOI 10.1016/0097-3165(84)90075-X
Richard P. Stanley, Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, Providence, R.I., 1972. MR 0332509
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
John R. Stembridge, Enriched $P$-partitions, Trans. Amer. Math. Soc. 349 (1997), no. 2, 763–788. MR 1389788, DOI 10.1090/S0002-9947-97-01804-7
David G. Wagner, Enumeration of functions from posets to chains, European J. Combin. 13 (1992), no. 4, 313–324. MR 1179527, DOI 10.1016/S0195-6698(05)80036-8