Every poset has a good comparison
Jeff Kahn, Michael Saks · 1984
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 log2e(X) comparisons ([email protected]@@@2.17).