The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest (Q2314426)

A balanced pair in an ordered set \(P = (V, \leq)\) is a pair \((x, y)\) of elements of \(V\) such that the proportion of linear extensions of \(P\) that put \(x\) before \(y\) is in the real interval \([1/3, 2/3]\). The author defines the notion of a good pair. \textbf{The 1/3--2/3 Conjecture} states that every finite ordered set which is not totally ordered has a balanced pair. It first appeared in a paper of \textit{S. S. Kislitsyn} [Math. Notes 4, 798--801 (1969; Zbl 0229.05016); translation from Mat. Zametki 4, 511--518 (1968)]. It was also formulated independently by Fredman in about 1975 and again by \textit{N. Linial} [SIAM J. Comput. 13, 795--801 (1984; Zbl 0548.68065)]. The following results related to the existence of a balanced pair are proved and thus the author shows that the conjecture holds in certain class of posets. Theorem. A finite ordered set that has a good pair has a balanced pair. Theorem. Let \(P = (V, \leq)\) be an ordered set and let \((x, y) \in \mathrm{inc}(P)\). Suppose that one of the following propositions holds for \(P\) or for its dual. (i) There exists \(z \in V\) such that \(x < z\), \(x \nsim y \nsim z\) and \(\{x, y\}\) is autonomous in \(P \ \{z\}\). (ii) There are \(z, t \in V\) such that \(x < z,y < t\), \(y \nsim z\), \(x \nsim t\) and \(\{x, y\}\) is autonomous for \(P \ \{z, t\}\). (iii) There are \(z, t \in V\) such that \(t < x <z\), \(y\) is incomparable to both \(t\) and \(z\), and \(\{x, y\}\) is autonomous for \(P \ \{z, t\}\). Then \(\{x, y\}\) is balanced in \(P\). Theorem. Let \(P\) be an ordered set not totally ordered whose cover graph is a forest. Then \(P\) has a very good pair, and hence has a balanced pair.