Characterizing posets with more linear extensions than ideals

Abstract

Two of the most important invariants associated with a poset P are the number of linear extensions, e(P), and the number of order ideals, i(P). Many important techniques to generate random linear extensions assume that e(P) ≥ i(P) and consequently choose to deal with ideals instead of linear extensions. However, this condition does not hold for every poset. In this paper we characterize when this condition holds for chain-irreducible posets, providing a complete list of posets where this fails. The proof is divided into three parts: for non-connected posets, for connected posets whose width exceeds 2, and for connected posets with width 2. We also give some applications of this result.