Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 113-126 |
| Number of pages | 14 |
| Journal | Order |
| Volume | 1 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jun 1984 |
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- AMS (MOS) subject classifications (1980): 06A10, 68E05
- Sorting
- comparison
- information theoretic bound
- linear extension