The cross–product conjecture for width two posets

Chan, Swee Hong; Pak, Igor; Panova, Greta

doi:10.1090/tran/8679

The cross–product conjecture for width two posets
HTML articles powered by AMS MathViewer

by Swee Hong Chan, Igor Pak and Greta Panova PDF

Trans. Amer. Math. Soc. 375 (2022), 5923-5961

Abstract:

The cross–product conjecture (CPC) of Brightwell, Felsner and Trotter [Order 12 (1995), pp. 327-349] is a two-parameter quadratic inequality for the number of linear extensions of a poset $P= (X, \prec )$ with given value differences on three distinct elements in $X$. We give two different proofs of this inequality for posets of width two. The first proof is algebraic and generalizes CPC to a four-parameter family. The second proof is combinatorial and extends CPC to a $q$-analogue. Further applications include relationships between CPC and other poset inequalities, and the equality part of the CPC for posets of width two.

References

Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. MR 3524748
Csaba Biró and William T. Trotter, A combinatorial approach to height sequences in finite partially ordered sets, Discrete Math. 311 (2011), no. 7, 563–569. MR 2765624, DOI 10.1016/j.disc.2010.12.020
Julius Borcea, Petter Brändén, and Thomas M. Liggett, Negative dependence and the geometry of polynomials, J. Amer. Math. Soc. 22 (2009), no. 2, 521–567. MR 2476782, DOI 10.1090/S0894-0347-08-00618-8
Petter Brändén and June Huh, Lorentzian polynomials, Ann. of Math. (2) 192 (2020), no. 3, 821–891. MR 4172622, DOI 10.4007/annals.2020.192.3.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
Francesco Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Jerusalem combinatorics ’93, Contemp. Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 71–89. MR 1310575, DOI 10.1090/conm/178/01893
G. R. Brightwell, S. Felsner, and W. T. Trotter, Balancing pairs and the cross product conjecture, Order 12 (1995), no. 4, 327–349. MR 1368815, DOI 10.1007/BF01110378
Graham Brightwell and Peter Winkler, Counting linear extensions, Order 8 (1991), no. 3, 225–242. MR 1154926, DOI 10.1007/BF00383444
S. H. Chan and I. Pak, Log-concave poset inequalities, preprint (2021), 71 pp., arXiv:2110.10740.
Swee Hong Chan, Igor Pak, and Greta Panova, Sorting probability for large Young diagrams, Discrete Anal. , posted on (2021), Paper No. 24, 57. MR 4349569, DOI 10.19086/da
S. H. Chan, I. Pak, and G. Panova, Extensions of the Kahn–Saks inequality for posets of width two, preprint (2021), 24 pp., arXiv:2106.07133.
S. H. Chan, I. Pak, and G. Panova, Effective combinatorics of poset inequalities, in preparation (2022).
Evan Chen, A family of partially ordered sets with small balance constant, Electron. J. Combin. 25 (2018), no. 4, Paper No. 4.43, 13. MR 3891110
Samuel Dittmer and Igor Pak, Counting linear extensions of restricted posets, Electron. J. Combin. 27 (2020), no. 4, Paper No. 4.48, 13. MR 4245223, DOI 10.37236/8552
Peter C. Fishburn, A correlational inequality for linear extensions of a poset, Order 1 (1984), no. 2, 127–137. MR 764320, DOI 10.1007/BF00565648
Michael L. Fredman, How good is the information theory bound in sorting?, Theoret. Comput. Sci. 1 (1975/76), no. 4, 355–361. MR 416100, DOI 10.1016/0304-3975(76)90078-5
I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint (1989), 36 pp., available at https://tinyurl.com/85z9v3m7
I. P. Goulden and D. M. Jackson, Combinatorial enumeration, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. With a foreword by Gian-Carlo Rota. MR 702512
R. L. Graham, A. C. Yao, and F. F. Yao, Some monotonicity properties of partial orders, SIAM J. Algebraic Discrete Methods 1 (1980), no. 3, 251–258. MR 586151, DOI 10.1137/0601028
June Huh, Combinatorial applications of the Hodge-Riemann relations, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3093–3111. MR 3966524
Jeff Kahn and Michael Saks, Balancing poset extensions, Order 1 (1984), no. 2, 113–126. MR 764319, DOI 10.1007/BF00565647
Jang Soo Kim and Dennis Stanton, On $q$-integrals over order polytopes, Adv. Math. 308 (2017), 1269–1317. MR 3600087, DOI 10.1016/j.aim.2017.01.001
S. S. Kislicyn, Finite partially ordered sets and their corresponding permutation sets, Mat. Zametki 4 (1968), 511–518 (Russian). MR 244113
Nathan Linial, The information-theoretic bound is good for merging, SIAM J. Comput. 13 (1984), no. 4, 795–801. MR 764179, DOI 10.1137/0213049
I. Pak, Combinatorial inequalities, Notices AMS 66 (2019), 1109–1112; an expanded version of the paper is available at https://tinyurl.com/py8sv5v6
Ashwin Sah, Improving the $\frac {1}{3}$-$\frac {2}{3}$ conjecture for width two posets, Combinatorica 41 (2021), no. 1, 99–126. MR 4235316, DOI 10.1007/s00493-020-4091-3
Y. Shenfeld and R. van Handel, The extremals of the Alexandrov–Fenchel inequality for convex polytopes, Acta Math., to appear, 82 pp., arXiv:2011.04059.
L. A. Shepp, The FKG inequality and some monotonicity properties of partial orders, SIAM J. Algebraic Discrete Methods 1 (1980), no. 3, 295–299. MR 586157, DOI 10.1137/0601034
L. A. Shepp, The $XYZ$ conjecture and the FKG inequality, Ann. Probab. 10 (1982), no. 3, 824–827. MR 659563
Richard P. Stanley, Two combinatorial applications of the Aleksandrov-Fenchel inequalities, J. Combin. Theory Ser. A 31 (1981), no. 1, 56–65. MR 626441, DOI 10.1016/0097-3165(81)90053-4
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
P. M. Winkler, Correlation among partial orders, SIAM J. Algebraic Discrete Methods 4 (1983), no. 1, 1–7. MR 689859, DOI 10.1137/0604001
Peter M. Winkler, Correlation and order, Combinatorics and ordered sets (Arcata, Calif., 1985) Contemp. Math., vol. 57, Amer. Math. Soc., Providence, RI, 1986, pp. 151–174. MR 856236, DOI 10.1090/conm/057/856236