Extensions of the Kahn--Saks inequality for posets of width two

Abstract

The Kahn--Saks inequality is a classical result on the number of linear extensions of finite posets. We give a new proof of this inequality for posets of width two using explicit injections of lattice paths. As a consequence we obtain a $q$-analogue, a multivariate generalization and an equality condition in this case. We also discuss the equality conditions of the Kahn--Saks inequality for general posets and prove several implications between conditions conjectured to be equivalent.

25 pages; v3: added conditions to Theorem 1.4 and 1.6, revised Conjecture in Section 8, added example 1.5

References in corpus (4)

• The cross-product conjecture for width two posets
• Log-concave poset inequalities
• Log-concavity in planar random walks
• The extremals of Stanley's inequalities for partially ordered sets

Cited by in corpus (7)

• The cross-product conjecture for width two posets
• Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
• Multivariate correlation inequalities for $P$-partitions
• Log-concave poset inequalities
• On the cross-product conjecture for the number of linear extensions
• Log-concavity in planar random walks
• Correlation inequalities for linear extensions