1/3–2/3 conjecture

Unsolved problem on partial orders thumb|A partial order formed by the series composition of one-element and three-element partial orders. Among its 27 linear extensions, the bottom left element occurs prior to the bottom right element in 9 out of 27. Partial orders with this structure are the only known extreme cases for the 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. Example 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.Kahn Saks 1984; Brightwell Felsner Trotter 1995. 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.Aigner 1985 Definitions 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.Brightwell Felsner Trotter 1995 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.Brightwell Felsner Trotter 1995 In 1984, Jeff Kahn and Michael Saks defined δ(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.Kahn Saks 1984 History The 1/3–2/3 conjecture was formulated by Sergey Kislitsyn in 1968,Kislitsyn 1968 and later made independently by Michael FredmanHowever, 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. and by Nati Linial in 1984.Brightwell Felsner Trotter 1995 It was listed as a featured unsolved problem at the founding of the journal Order, and remains unsolved; being called "one of the most intriguing problems in the combinatorial theory of posets."Brightwell Felsner Trotter 1995 A survey of the conjecture was produced in 1999.Brightwell 1999 Partial results The 1/3–2/3 conjecture is known to be true for certain special classes of partial orders, including partial orders of width two,Linial 1984, Theorem 2; Sah 2021. partial orders of height two,Trotter Gehrlein Fishburn 1992 partial orders with at most 13 elements,De Loof De Baets De Meyer 2010, §4.2.2 and Fig. 2; the exhaustive computation identifies the extremal cases through 13 elements. partial orders in which each element is incomparable to at most six others,Peczarski 2008. series-parallel partial orders, partial orders whose Hasse diagram is N-free,Zaguia 2012 semiorders,Brightwell 1989 and polytrees.Zaguia 2019 A 2026 preprint reports verification through 14 elements.Gupta 2026 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%.Peczarski 2006. In 1995, Graham Brightwell, Stefan Felsner, and William Trotter proved that, for any finite partial order P that is not total, . Their results improve previous weaker bounds of the same type.Brightwell Felsner Trotter 1995; Kahn Saks 1984; Khachiyan 1989; Kahn Linial 1991; Felsner Trotter 1993. They use the probabilistic interpretation of 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 . In 2026, a preprint by Max Aires, Swee Hong Chan, Igor Pak, and Greta Panova reported an improved bound to for finite posets, where Aires Max Breaking the Infinite Barrier in the $\frac{1}{3}$--$\frac{2}{3}$ Conjecture 2026-09-25 http://arxiv.org/abs/2609.30888 2026-10-11 arXiv 10.48550/arXiv.2609.30888 arXiv:2609.30888 Chan Swee Hong Pak Igor Panova Greta. Taken together, these results establish a separation between finite and infinite partial orders in the context of the 1/3-2/3 conjecture. Applications In 1984 Jeff Kahn and Saks 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 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 comparisons may suffice, where denotes the golden ratio. A closely related class of comparison sorting problems was considered by Fredman in 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 showed that X can be sorted using comparisons, expressed in big O notation. This same bound applies as well to the case of partial orders and shows that comparisons suffice.Fredman 1976 Generalizations and related results In 1984, Kahn and Saks conjectured that, in the limit as tends to infinity, the value of for partially ordered sets of width should tend to . In particular, they expect that only partially ordered sets of width two can achieve the worst case value Kahn Saks 1984 and in 1985 Martin Aigner stated this explicitly as a conjecture.Aigner 1985 The smallest known value of for posets of width three is ,Saks 1985 and computer searches have shown that no smaller value is possible for width-3 posets with nine or fewer elements.Trotter Gehrlein Fishburn 1992 Another related conjecture, again based on computer searches, states that there is a gap between and the other possible values of : whenever a partial order does not have exactly , it has .Peczarski 2019 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 denotes the number of linear extensions remaining after of the comparisons have been made, then (in each of the four possible outcomes of the comparisons) . 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 linear extensions can be sorted in at most comparisons; the name of the conjecture is derived from this connection with the golden ratio. It is #P-complete, given a finite partial order and a pair of elements and , to calculate the proportion of the linear extensions of that place earlier than .Brightwell Winkler 1991. Notes 35em References Aigner Martin Martin Aigner 10.1007/BF00333131 https://link.springer.com/article/10.1007/BF00333131 3 Order 257–264 A note on merging 2 1985 118877843 subscription . Brightwell Graham R. 10.1007/BF00353656 4 Order 369–380 Semiorders and the 1/3–2/3 conjecture 5 1989 86860160 . Brightwell Graham R. 10.1016/S0012-365X(98)00311-2 1–3 Discrete Mathematics 25–52 Balanced pairs in partial orders 201 1999 . Brightwell Graham R. Felsner Stefan Trotter William T. 10.1007/BF01110378 1368815 4 Order 327–349 Balancing pairs and the cross product conjecture 12 1995 14793475 . Brightwell Graham R. Winkler Peter Peter Winkler 10.1007/BF00383444 3 Order 225–242 Counting linear extensions 8 1991 119697949 . De Loof Karel De Baets Bernard De Meyer Hans 10.1016/j.camwa.2009.12.021 4 Computers & Mathematics with Applications 1541–1547 Counting linear extension majority cycles in partially ordered sets on up to 13 elements 59 2010 . Felsner Stefan Trotter William T. Balancing pairs in partially ordered sets 1249709 Budapest 145–157 János Bolyai Mathematical Society Bolyai Society Mathematical Studies Combinatorics, Paul Erdős is eighty 1 1993. Fredman M. L. Michael Fredman 10.1016/0304-3975(76)90078-5 4 Theoretical Computer Science 355–361 How good is the information theory bound in sorting? 1 1976 Gupta Anish 2607.23926 Balance Constants, Majority Cycles, and the Gold Partition Conjecture through Fourteen Elements 2026 . Kahn Jeff Jeff Kahn (mathematician) Linial Nati Nati Linial 10.1007/BF01275670 4 Combinatorica 363–368 Balancing extensions via Brunn-Minkowski 11 1991 206793172 . Kahn Jeff Jeff Kahn (mathematician) Saks Michael Michael Saks (mathematician) 10.1007/BF00565647 2 Order 113–126 Balancing poset extensions 1 1984 123370506 . Khachiyan Leonid Leonid Khachiyan Optimal algorithms in convex programming decomposition and sorting Jaravlev J. Russian Moscow 161–205 Nauka Computers and Decision Problems 1989. As cited by Brightwell Felsner Trotter 1995. Kislitsyn S. S. Sergey Kislitsyn 10.1007/BF01111312 5 Mathematical Notes 798–801 A finite partially ordered set and its corresponding set of permutations 4 1968 120228193 . Linial Nati 5149351 Nati Linial 10.1137/0213049 4 SIAM Journal on Computing 795–801 The information-theoretic bound is good for merging 13 1984. Peczarski Marcin 10.1007/s11083-006-9033-1 1 Order 89–95 The gold partition conjecture 23 2006 42415160 . Peczarski Marcin 10.1007/s11083-008-9081-9 2 Order 91–103 The gold partition conjecture for 6-thin posets 25 2008 42034095 . Peczarski Marcin 10.1080/10586458.2017.1368050 2 Experimental Mathematics 3955809 181–184 The worst balanced partially ordered sets—ladders with broken rungs 28 2019 125593629 . Sah Ashwin 10.1007/s00493-020-4091-3 1 Combinatorica 4235316 99–126 Improving the – conjecture for width two posets 41 2021 1811.01500 119604901 Saks Michael Michael Saks (mathematician) Balancing linear extensions of ordered sets Unsolved problems https://link.springer.com/article/10.1007/BF00333138 10.1007/BF00333138 Order 327–330 2 1985 189901558 subscription Trotter William T. Gehrlein William V. Fishburn Peter C. Peter C. Fishburn 10.1007/BF00419038 1 Order 43–53 Balance theorems for height-2 posets 9 1992 16157076 . Zaguia Imed 2 Electronic Journal of Combinatorics P29 The 1/3-2/3 Conjecture for N-free ordered sets 19 2012 1107.5626 10.37236/2345 1979845 . Zaguia Imed 10.1007/s11083-018-9469-0 2 Order 3983482 335–347 The 1/3–2/3 conjecture for ordered sets whose cover graph is a forest 36 2019 1610.00809 119631612 . Category:Order theory Category:Conjectures Category:Unsolved problems in mathematics