# 1/3–2/3 conjecture

In order theory, a branch of mathematics, the **1/3–2/3 conjecture** states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. Equivalently, in every finite partially ordered set that is not totally ordered, there exists a pair of elements *x* and *y* with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place *x* earlier than *y*.

## Contents

## Example[edit]

The partial order formed by three elements *a*, *b*, and *c* with a single comparability relationship, *a* ≤ *b*, has three linear extensions, *a* ≤ *b* ≤ *c*, *a* ≤ *c* ≤ *b*, and *c* ≤ *a* ≤ *b*. In all three of these extensions, *a* is earlier than *b*. However, *a* is earlier than *c* in only two of them, and later than *c* in the third. Therefore, the pair of *a* and *c* have the desired property, showing that this partial order obeys the 1/3–2/3 conjecture.

This example shows that the constants 1/3 and 2/3 in the conjecture are tight; if *q* is any fraction strictly between 1/3 and 2/3, then there would not exist a pair *x*, *y* in which *x* is earlier than *y* in a number of partial orderings that is between *q* and 1 − *q* times the total number of partial orderings.^{[1]}

More generally, let *P* be any series composition of three-element partial orders and of one-element partial orders, such as the one in the figure. Then *P* forms an extreme case for the 1/3–2/3 conjecture in the sense that, for each pair *x*, *y* of elements, one of the two elements occurs earlier than the other in at most 1/3 of the linear extensions of *P*. Partial orders with this structure are necessarily series-parallel semiorders; they are the only known extreme cases for the conjecture and can be proven to be the only extreme cases with width two.^{[2]}

## Definitions[edit]

A partially ordered set is a set *X* together with a binary relation ≤ that is reflexive, antisymmetric, and transitive. A total order is a partial order in which every pair of elements is comparable. A linear extension of a finite partial order is a sequential ordering of the elements of *X*, with the property that if *x* ≤ *y* in the partial order, then *x* must come before *y* in the linear extension. In other words, it is a total order compatible with the partial order. If a finite partially ordered set is totally ordered, then it has only one linear extension, but otherwise it will have more than one, the 1/3–2/3 conjecture states that one can choose two elements *x* and *y* such that, among this set of possible linear extensions, between 1/3 and 2/3 of them place *x* earlier than *y*, and symmetrically between 1/3 and 2/3 of them place *y* earlier than *x*.^{[3]}

There is an alternative and equivalent statement of the 1/3–2/3 conjecture in the language of probability theory. One may define a uniform probability distribution on the linear extensions in which each possible linear extension is equally likely to be chosen. The 1/3–2/3 conjecture states that, under this probability distribution, there exists a pair of elements *x* and *y* such that the probability that *x* is earlier than *y* in a random linear extension is between 1/3 and 2/3.^{[3]}

Kahn & Saks (1984) define δ(*P*), for any partially ordered set *P*, to be the largest real number δ such that *P* has a pair *x*, *y* with *x* earlier than *y* in a number of linear extensions that is between δ and 1 − δ of the total number of linear extensions. In this notation, the 1/3–2/3 conjecture states that every finite partial order that is not total has δ(*P*) ≥ 1/3.

## History[edit]

The 1/3–2/3 conjecture was formulated by Kislitsyn (1968), and later made independently by Michael Fredman^{[4]} and by Nati Linial (1984).^{[3]} It was listed as a featured unsolved problem at the founding of the journal *Order*, and remains unsolved;^{[3]} Brightwell, Felsner & Trotter (1995) call it "one of the most intriguing problems in the combinatorial theory of posets."

A survey of the conjecture is given by Brightwell (1999).

## Partial results[edit]

The 1/3–2/3 conjecture is known to be true for certain special classes of partial orders, including partial orders of width two,^{[5]} partial orders of height two,^{[6]} partial orders with at most 11 elements,^{[7]} partial orders in which each element is incomparable to at most six others,^{[8]} series-parallel partial orders,^{[9]} and semiorders.^{[10]} In the limit as *n* goes to infinity, the proportion of *n*-element partial orders that obey the 1/3–2/3 conjecture approaches 100%.^{[7]}

Brightwell, Felsner & Trotter (1995) proved that, for any finite partial order *P* that is not total, δ(*P*) ≥ 1/2 − √5/10 ≈ 0.276. Their results improve previous weaker bounds of the same type.^{[11]} They use the probabilistic interpretation of δ(*P*) to extend its definition to certain infinite partial orders; in that context, they show that their bounds are optimal, in that there exist infinite partial orders with δ(*P*) = 1/2 − √5/10.

## Applications[edit]

Kahn & Saks (1984) proposed the following application for the problem: suppose one wishes to comparison sort a totally ordered set *X*, for which some partial order information is already known in the form of a partial order on *X*. In the worst case, each additional comparison between a pair *x* and *y* of elements may yield as little information as possible, by resolving the comparison in a way that leaves as many linear extensions as possible compatible with the comparison result. The 1/3–2/3 conjecture states that, at each step, one may choose a comparison to perform that reduces the remaining number of linear extensions by a factor of 2/3; therefore, if there are *E* linear extensions of the partial order given by the initial information, the sorting problem can be completed in at most log_{3/2}*E* additional comparisons.

However, this analysis neglects the complexity of selecting the optimal pair *x* and *y* to compare. Additionally, it may be possible to sort a partial order using a number of comparisons that is better than this analysis would suggest, because it may not be possible for this worst-case behavior to occur at each step of a sorting algorithm; in this direction, it has been conjectured that log_{φ}*E* comparisons may suffice, where φ denotes the golden ratio.^{[7]}

A closely related class of comparison sorting problems is considered by Fredman (1976), among them the problem of comparison sorting a set *X* when the sorted order of *X* is known to lie in some set *S* of permutations of *X*. Here *S* is not necessarily generated as the set of linear extensions of a partial order, despite this added generality, Fredman shows that *X* can be sorted using log_{2}|*S*| + O(|*X*|) comparisons. This same bound applies as well to the case of partial orders and shows that log_{2}*E* + O(*n*) comparisons suffice.

## [edit]

Kahn & Saks (1984) conjectured that, in the limit as *w* tends to infinity, the value of δ(*P*) for partially ordered sets of width *w* should tend to 1/2. In particular, they expect that only partially ordered sets of width two can achieve the worst case value δ(*P*) = 1/3, and Aigner (1985) stated this explicitly as a conjecture. The smallest known value of δ(*P*) for posets of width three is 14/39,^{[12]} and computer searches have shown that no smaller value is possible for width-3 posets with nine or fewer elements.^{[6]}

Marcin Peczarski^{[7]}^{[8]} has formulated a "gold partition conjecture" stating that in each partial order that is not a total order one can find two consecutive comparisons such that, if *t*_{i} denotes the number of linear extensions remaining after *i* of the comparisons have been made, then (in each of the four possible outcomes of the comparisons) *t*_{0} ≥ *t*_{1} + *t*_{2}. If this conjecture is true, it would imply the 1/3–2/3 conjecture: the first of the two comparisons must be between a pair that splits the remaining comparisons by at worst a 1/3–2/3 ratio. The gold partition conjecture would also imply that a partial order with *E* linear extensions can be sorted in at most log_{φ}*E* comparisons; the name of the conjecture is derived from this connection with the golden ratio.

It is #P-complete, given a finite partial order *P* and a pair of elements *x* and *y*, to calculate the proportion of the linear extensions of *P* that place *x* earlier than *y*.^{[13]}

## Notes[edit]

**^**Kahn & Saks (1984); Brightwell, Felsner & Trotter (1995).**^**Aigner (1985).- ^
^{a}^{b}^{c}^{d}Brightwell, Felsner & Trotter (1995). **^**However, despite the close connection of Fredman (1976) to the problem of sorting partially ordered data and hence to the 1/3–2/3 conjecture, it is not mentioned in that paper.**^**Linial (1984), Theorem 2.- ^
^{a}^{b}Trotter, Gehrlein & Fishburn (1992). - ^
^{a}^{b}^{c}^{d}Peczarski (2006). - ^
^{a}^{b}Peczarski (2008). **^**Zaguia (2012)**^**Brightwell (1989).**^**Kahn & Saks (1984); Khachiyan (1989); Kahn & Linial (1991); Felsner & Trotter (1993).**^**Saks (1985).**^**Brightwell & Winkler (1991).

## References[edit]

- Aigner, Martin (1985), "A note on merging",
*Order*,**2**(3): 257–264, doi:10.1007/BF00333131 (inactive 2017-01-19). - Brightwell, Graham R. (1989), "Semiorders and the 1/3–2/3 conjecture",
*Order*,**5**(4): 369–380, doi:10.1007/BF00353656. - Brightwell, Graham R. (1999), "Balanced pairs in partial orders",
*Discrete Mathematics*,**201**(1–3): 25–52, doi:10.1016/S0012-365X(98)00311-2. - Brightwell, Graham R.; Felsner, Stefan; Trotter, William T. (1995), "Balancing pairs and the cross product conjecture",
*Order*,**12**(4): 327–349, MR 1368815, doi:10.1007/BF01110378. - Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions",
*Order*,**8**(3): 225–242, doi:10.1007/BF00383444. - Felsner, Stefan; Trotter, William T. (1993), "Balancing pairs in partially ordered sets",
*Combinatorics, Paul Erdős is eighty*, Bolyai Society Mathematical Studies,**1**, Budapest: János Bolyai Mathematical Society, pp. 145–157, MR 1249709. - Fredman, M. L. (1976), "How good is the information theory bound in sorting?",
*Theoretical Computer Science*,**1**(4): 355–361, doi:10.1016/0304-3975(76)90078-5 - Kahn, Jeff; Linial, Nati (1991), "Balancing extensions via Brunn-Minkowski",
*Combinatorica*,**11**(4): 363–368, doi:10.1007/BF01275670. - Kahn, Jeff; Saks, Michael (1984), "Balancing poset extensions",
*Order*,**1**(2): 113–126, doi:10.1007/BF00565647. - Khachiyan, Leonid (1989), "Optimal algorithms in convex programming decomposition and sorting", in Jaravlev, J.,
*Computers and Decision Problems*(in Russian), Moscow: Nauka, pp. 161–205. As cited by Brightwell, Felsner & Trotter (1995). - Kislitsyn, S. S. (1968), "A finite partially ordered set and its corresponding set of permutations",
*Mathematical Notes*,**4**(5): 798–801, doi:10.1007/BF01111312. - Linial, Nati (1984), "The information-theoretic bound is good for merging",
*SIAM Journal on Computing*,**13**(4): 795–801, doi:10.1137/0213049. - Peczarski, Marcin (2006), "The gold partition conjecture",
*Order*,**23**(1): 89–95, doi:10.1007/s11083-006-9033-1. - Peczarski, Marcin (2008), "The gold partition conjecture for 6-thin posets",
*Order*,**25**(2): 91–103, doi:10.1007/s11083-008-9081-9. - Saks, Michael (1985), "Balancing linear extensions of ordered sets", Unsolved problems,
*Order*,**2**: 327–330, doi:10.1007/BF00333138 (inactive 2017-01-19) - Trotter, William T.; Gehrlein, William V.; Fishburn, Peter C. (1992), "Balance theorems for height-2 posets",
*Order*,**9**(1): 43–53, doi:10.1007/BF00419038. - Zaguia, Imed (2012), "The 1/3-2/3 Conjecture for
*N*-free ordered sets",*Electronic Journal of Combinatorics*,**19**(2): P29.