Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets (Q2036599): Difference between revisions

The \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture states that for any poset (partially ordered set) \((P,\prec)\) which is not totally ordered, there are two incomparable elements \(x,y\in P\) such that, considering the probability space of all linear extensions of \(P\) (i.e. total orderings compatible with the partial order \(\prec\)) with the uniform distribution, we have \(\mathbb{P}(x\prec y)\in [1/3,2/3]\). Equivalently, defining \(\delta (P)=\max_{\{x,y\} \subseteq P} \min (\mathbb{P}(x\prec y). \mathbb{P}(y\prec x))\), we have \(\delta(P)\geq 1/3\) for any poset \(P\) which is not totally ordered. It is known that we cannot improve on the interval \([1/3,2/3]\) in the first form of the conjecture (respectively on the constant \(1/3\)) in the formulation involving \(\delta(P)\); for example consider the poset \(\mathcal{E}\) comprising three vertices \(\{x,y,z\}\) with exactly one relation \(x\prec y\). Various special cases are known: they include width 2 posets, see \textit{N. Linial} [SIAM J. Comput. 13, 795--801 (1984; Zbl 0548.68065)], but the general problem seems to be very difficult. \par Attention in this paper focusses on the case of width 2 posets. \textit{M. Aigner} [Order 2, 257--264 (1985; Zbl 0582.06003)] showed that width 2 posets which achieve \(\delta(P)=1/3\) are very limited (they are direct sums of copies of \(\mathcal{E}\) above and the one-element poset). The first main contribution of the paper under review is to show that when a width 2 poset does not have \(\delta(P)=1/3\) then there is a new lower bound for \(\delta(P)\), namely \((5\sqrt{17}-3)/52\simeq 0.33876\). Numerical work in \textit{M. Peczarski} [Exp. Math. 28, No. 2, 181--184 (2019; Zbl 1490.06002)] suggests that an improvement to about 0.348842 may be possible. \par In the other direction, the author can improve on an infinite sequence \((P_{n})\) of width 2 posets constructed in \textit{E. Chen} [Electron. J. Comb. 25, No. 4, Research Paper P4.43, 13 p. (2018; Zbl 06989244)] where the limiting value of \(\delta(P_{n})\) is about 0.3488999, by giving a sequence \((Q_{n})\) for which the limit of \(\delta(Q_{n})\) is 0.348833. (All these limits are quadratic surds). This time, Peczarski's numerical work [loc. cit,] suggests that this sequence of examples may be best possible. \par Both results make use of a path-counting interpretation of identification of linear extensions of width 2 posets with a certain path-counting problem. The author also notes some open problems.