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.
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.
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.
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.
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.
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.
The 1/3–2/3 conjecture was formulated by Kislitsyn (1968), and later made independently by Michael Fredman and by Nati Linial (1984). It was listed as a featured unsolved problem at the founding of the journal Order, and remains unsolved; 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).
The 1/3–2/3 conjecture is known to be true for certain special classes of partial orders, including partial orders of width two, partial orders of height two, partial orders with at most 11 elements, partial orders in which each element is incomparable to at most six others, series-parallel partial orders, and semiorders. 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%.
Brightwell, Felsner & Trotter (1995) proved that, for any finite partial order P that is not total, δ(P) ≥ 1/2 − √/10 ≈ 0.276. Their results improve previous weaker bounds of the same type. 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 − √/10.
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 log3/2E 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.
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 log2|S| + O(|X|) comparisons. This same bound applies as well to the case of partial orders and shows that log2E + O(n) comparisons suffice.
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, and computer searches have shown that no smaller value is possible for width-3 posets with nine or fewer elements.
Marcin Peczarski 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 ti 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) t0 ≥ t1 + t2. 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.
- Kahn & Saks (1984); Brightwell, Felsner & Trotter (1995).
- Aigner (1985).
- 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.
- Trotter, Gehrlein & Fishburn (1992).
- Peczarski (2006).
- Peczarski (2008).
- Zaguia (2012)
- Brightwell (1989).
- Kahn & Saks (1984); Khachiyan (1989); Kahn & Linial (1991); Felsner & Trotter (1993).
- Saks (1985).
- Brightwell & Winkler (1991).
- Aigner, Martin (1985), "A note on merging", Order, 2 (3): 257–264, doi:10.1007/BF00333131 (inactive 2018-08-27).
- 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, CiteSeerX 10.1.1.38.7841, doi:10.1007/BF01110378, MR 1368815.
- 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 2018-08-27)
- 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.