The 1/3–2/3 Conjecture for 5-Thin Posets (Q4030185)

For a poset \((X,<)\) a linear extension of \((X,<)\) is a total order \((X,\ll)\) on \(X\) such that \(x\ll y\) whenever \(x<y\). If \(x\) and \(y\) are elements of \((X,<)\), the probability \(P(x\ll y)\) that \(x\) is below \(y\) is defined to be the proportion of linear extensions \(\ll\) of \((X,<)\) in which \(x\ll y\). If \(x<y\) in \((X,<)\), then \(P(x\ll y)=1\). The behavior of this probability has been extensively studied (survey articles by \textit{R. L. Graham} [Mathematical programming, 11th Int. Symp., Bonn 1982, 115-131 (1983; Zbl 0561.06006)], \textit{I. Rival} [Ann. Discrete Math. 23, 355-370 (1984; Zbl 0551.06003)] and \textit{P. M. Winkler} [Contemp. Math. 57, 151- 174 (1986; Zbl 0598.06001)]), but the 1/3-2/3 conjecture has not yet been resolved. The 1/3-2/3 conjecture states the following: Let \((X,<)\) be a finite partial order that is not a total order. Then there exist distinct elements \(x\), \(y\) of \(X\) such that \(1/3\leq P(x\ll y)\leq 2/3\). The authors verify this conjecture for 5-thin partial orders, where for a positive integer \(k\) the poset \((X,<)\) is \(k\)-thin if every element of \(X\) is incomparable with at most \(k\) other elements of \(X\). Theorem: Let \((X,<)\) be a 5-thin partial order that is not a total order. Then there exist distinct elements \(x\), \(y\) of \(X\) such that \(1/3\leq P(x\ll y)\leq 2/3\). The strategy for proving the theorem is roughly as follows: The authors define a poset \((X,<)\) to satisfy the 1/3-2/3 condition, if there is no pair of elements \(x\), \(y\), such that \(1/3\leq P(x\ll y)\leq 2/3\). The conjecture then states that the only finite posets that satisfy the 1/3- 2/3 condition are the total orders. Given a 5-thin poset with at least two minimal elements, the authors show that it does not satisfy the 1/3- 2/3 condition and that it does not have a down-set isomorphic to \((X,<)\) that satisfies the condition. A configuration is discardable if there is no continuation of it satisfying the 1/3-2/3 condition, and it is shown that every configuration that is not 2-separated is discardable. The authors produce a finite list of discardable configurations such that every 5-thin poset with at least 2 minimals and a 2-separated pair of elements is a continuation of some configuration in the list. The existence of the list implies that the only 5-thin posets satisfying the 1/3-2/3 condition are total orders. The list was found with the aid of a computer. It consists of 38,372 configurations. A brief description of the programming methods used to find the list is included in the paper. For a full account including a listing of the programs that were used, the authors refer to the second author's thesis [``Combinatorial algorithms'', Ph. D. thesis, Cambridge Univ. Cambridge, UK (1990)].