×

Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets. (English) Zbl 1474.06006

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 N. Linial [SIAM J. Comput. 13, 795–801 (1984; Zbl 0548.68065)], but the general problem seems to be very difficult.
Attention in this paper focusses on the case of width 2 posets. 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 M. Peczarski [Exp. Math. 28, No. 2, 181–184 (2019; Zbl 1490.06002)] suggests that an improvement to about 0.348842 may be possible.
In the other direction, the author can improve on an infinite sequence \((P_{n})\) of width 2 posets constructed in E. Chen [Electron. J. Comb. 25, No. 4, Research Paper P4.43, 13 p. (2018; Zbl 1507.06002)] 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.
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.

MSC:

06A07 Combinatorics of partially ordered sets
05A20 Combinatorial inequalities
05D99 Extremal combinatorics
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, M., A note on merging, Order, 2, 257-264 (1985) · Zbl 0582.06003
[2] Brightwell, G. R.; Felsner, S.; Trotter, W. T., Balancing pairs and the cross product conjecture, Order, 12, 327-349 (1995) · Zbl 0839.06002 · doi:10.1007/BF01110378
[3] Brightwell, G., Balanced pairs in partial orders, Discrete Mathematics, 201, 25-52 (1999) · Zbl 0940.06002 · doi:10.1016/S0012-365X(98)00311-2
[4] Brightwell, G. R., Semiorders and the 1/3-2/3 conjecture, Order, 5, 369-380 (1989) · Zbl 0681.06001 · doi:10.1007/BF00353656
[5] Cardinal, J.; Fiorini, S.; Joret, G.; Jungers, R. M.; Munro, J. I., Sorting under partial information (without the ellipsoid algorithm), Combinatorica, 33, 655-697 (2013) · Zbl 1315.06002 · doi:10.1007/s00493-013-2821-5
[6] E. Chen: A family of partially ordered sets with small balance constant, Electron. J. Combin.25 Paper 4.43, 13, 2018. · Zbl 1507.06002
[7] Fiorini, S.; Rexhep, S., Poset entropy versus number of linear extensions: the width-2 case, Order, 33, 1-21 (2016) · Zbl 1343.06002 · doi:10.1007/s11083-015-9346-z
[8] Fishburn, P. C., On linear extension majority graphs of partial orders, Journal of Combinatorial Theory, Series B, 21, 65-70 (1976) · Zbl 0294.06001 · doi:10.1016/0095-8956(76)90028-9
[9] Fredman, M. L., How good is the information theory bound in sorting?, Theoretical Computer Science, 1, 355-361 (1976) · Zbl 0327.68056 · doi:10.1016/0304-3975(76)90078-5
[10] Hoggar, S. G., Chromatic polynomials and logarithmic concavity, Journal of Combinatorial Theory, Series B, 16, 248-254 (1974) · Zbl 0268.05104 · doi:10.1016/0095-8956(74)90071-9
[11] Kahn, J.; Kim, J. H., Entropy and sorting, volume 51, 390-399. 1995 (1992) · Zbl 1294.68069
[12] Kahn, J.; Saks, M., Balancing poset extensions, Order, 1, 113-126 (1984) · Zbl 0561.06004 · doi:10.1007/BF00565647
[13] Kislitsyn, S. S., Finite partially ordered sets and their corresponding permutation sets, Math. Notes, 4, 798-801 (1968) · Zbl 0229.05016 · doi:10.1007/BF01111312
[14] Linial, N., The information-theoretic bound is good for merging, SIAM Journal on Computing, 13, 795-801 (1984) · Zbl 0548.68065 · doi:10.1137/0213049
[15] Olson, E. J.; Sagan, B. E., On the 1/3-2/3 conjecture, Order, 35, 581-596 (2018) · Zbl 1528.06007 · doi:10.1007/s11083-017-9450-3
[16] Peczarski, M., The Gold Partition Conjecture for 6-thin Posets, Order, 25, 91-103 (2008) · Zbl 1155.06004 · doi:10.1007/s11083-008-9081-9
[17] Peczarski, M., The Worst Balanced Partially Ordered Sets—Ladders with Broken Rungs, Experimental Mathematics, 28, 181-184 (2019) · Zbl 1490.06002 · doi:10.1080/10586458.2017.1368050
[18] Trotter, W. T.; Gehrlein, W. G.; Fishburn, P. C., Balance theorems for height-2 posets, Order, 9, 43-53 (1992) · Zbl 0769.06004 · doi:10.1007/BF00419038
[19] I. Zaguia: The 1/3-2/3 conjecture for N-free ordered sets, Electron. J. Combin.19 Paper 29, 5, 2012. · Zbl 1288.06005
[20] Zaguia, I., The 1/3-2/3 conjecture for ordered sets whose cover graph is a forest, Order, 36, 335-347 (2019) · Zbl 1443.06004 · doi:10.1007/s11083-018-9469-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.