We show that any finite partially ordered set P (not a total order) 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 information, then it is possible to sort X using no more than C log2e (X) comparisons where C is approximately 2.17.
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Geometry and Topology
- Computational Theory and Mathematics
- AMS (MOS) subject classifications (1980): 06A10, 68E05
- information theoretic bound
- linear extension