Balancing poset extensions

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

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 languageEnglish (US)
Pages (from-to)113-126
Number of pages14
JournalOrder
Volume1
Issue number2
DOIs
StatePublished - Jun 1984

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics

Keywords

  • AMS (MOS) subject classifications (1980): 06A10, 68E05
  • Sorting
  • comparison
  • information theoretic bound
  • linear extension

Fingerprint

Dive into the research topics of 'Balancing poset extensions'. Together they form a unique fingerprint.

Cite this