zbMATH — the first resource for mathematics

Balancing poset extensions. (English) Zbl 0561.06004
From the author’s abstract: Theorem: Any finite partially ordered set P, which is not totally ordered, 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 log\({}_ 2e(X)\) comparisons where C is approximately 2.17.
Reviewer: T.Ohkuma

06A06 Partial orders, general
68P10 Searching and sorting
06A05 Total orders
05A20 Combinatorial inequalities
Full Text: DOI
[1] H. Buseman (1958)Convex Surfaces, Interscience, New York.
[2] T. Bonneson and W. Fenchel (1934)Theorie der konvexen Körper, Springer, Berlin, 1934; Chelsea, New York, 1948 and 1971.
[3] M. Fredman (1976) How good is the information theory bound in sorting?,Theoretical Computer Science 1, 355-361. · Zbl 0327.68056 · doi:10.1016/0304-3975(76)90078-5
[4] N. Linial, The information theoretic bound is good for merging,SIAM J. Comp., to appear. · Zbl 0548.68065
[5] R. P. Stanley (1987) Two combinatorial applications of the Aleksandrov-Fenchel inequalities,J. Comb. Theory (A) 31, 56-65. · Zbl 0484.05012 · doi:10.1016/0097-3165(81)90053-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.