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. 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).