Skip to main content
Open Access Publications from the University of California

Combinatorial Theory

Combinatorial Theory banner

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

Published Web Location Commons 'BY' version 4.0 license

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

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View