## 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

## Additional Information

**Swee Hong Chan**- Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
- MR Author ID: 1058757
- ORCID: 0000-0003-0599-9901
- Email: sweehong@math.ucla.edu
**Igor Pak**- Affiliation: Department of Mathematics, UCLA, Los Angeles, California 90095
- MR Author ID: 293184
- ORCID: 0000-0001-8579-7239
- Email: pak@math.ucla.edu
**Greta Panova**- Affiliation: Department of Mathematics, USC, Los Angeles, California 90089
- MR Author ID: 964307
- ORCID: 0000-0003-0785-1580
- Email: gpanova@usc.edu
- Received by editor(s): May 6, 2021
- Received by editor(s) in revised form: February 7, 2022, and February 22, 2022
- Published electronically: June 10, 2022
- Additional Notes: The first author was supported in part by the AMS-Simons Travel Grant.

The second author was supported in part by NSF Grant #2007891.

The third author was supported in part by NSF Grant #2007652. - © Copyright 2022 by the authors
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 5923-5961 - MSC (2020): Primary 05A20; Secondary 05A30, 06A07, 06A11
- DOI: https://doi.org/10.1090/tran/8679
- MathSciNet review: 4469242