Balanced pairs in partial orders (Q1301727)

If \(P=(X,<)\) is a partial order, denote by \(P(x\prec y)\) the proportion of linear extensions of \(P\) in which \(x\) is below \(y\). For \(0<\alpha\leq 1/2\), an \(\alpha\)-balanced pair is a pair \((x,y)\) of elements of \(X\) with \(\alpha\leq P(x\prec y)\leq 1-\alpha\). The paper is a survey on the \(1/3-2/3\) Conjecture, which can be formulated as follows: In every finite partial order that is not a chain, there is some 1/3-balanced pair. This conjecture is important for example in the problem how many comparisions are necessary to reconstruct a linear order from a given partial order on the same set. The number of comparisons is minimal if one can find a pair \((x,y)\) with \(P(x\prec y)=1/2\). The author shows some special types of partial orders for which the \(1/3-2/3\) Conjecture has been proved (i.e., the balanced constant of every such class is at least 1/3) and observes the various weaker bounds of the balanced constant for the class of all partial orders that are not chains. Variations on the problem and algorithmic aspects are also dicussed.