On the cross-product conjecture for the number of linear extensions

Abstract

We prove a weak version of the cross--product conjecture: $F(k+1,\ell )F(k,\ell +1)\ge (\frac{1}{2}+\epsilon )F(k,\ell )F(k+1,\ell +1)$, where $F(k,\ell )$ is the number of linear extensions for which the values at fixed elements $x,y,z$ are $k$ and $\ell$ apart, respectively, and where $\epsilon >0$ depends on the poset. We also prove the converse inequality and disprove the {generalized cross--product conjecture}. The proofs use geometric inequalities for mixed volumes and combinatorics of words.

24 pages

References in corpus (4)

• Introduction to the combinatorial atlas
• Extensions of the Kahn--Saks inequality for posets of width two
• Effective poset inequalities
• Multivariate correlation inequalities for $P$-partitions

Cited by in corpus (2)

• Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
• Correlation inequalities for linear extensions