Combinatorial Theory

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 and both elements in the same chain 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.

Mathematics Subject Classifications: 05A15, 05A19, 05A20, 05A30, 06A07

Keywords: Poset inequality, Stanley's inequality, Kahn-Saks inequality, log-concavity, q-analogues, equality conditions, lattice paths