Every Poset Has a Good Comparison

We show that any finite partially ordered set P contains a pair of elements x and y such that the proportion of linear extensions of P in which x lies below y is between 3/11 and 8/11. A consequence is that the information-theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: if X is a totally ordered set about which we are given some partial information, and if e(X) is the number of total orderings of X compatible with this partial information, then it is possible to sort X using no more than c log 2 e(X) comparisons (c@@@@2.17).

Authors

• Jeff Kahn 0001
• Michael E. Saks

Keywords

No keywords are indexed for this paper.