1/3–2/3 conjecture

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

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

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

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

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

Generalizations and related results

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 "golden 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 golden 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

  1. ↑ Kahn & Saks (1984); Brightwell, Felsner & Trotter (1995).
  2. ↑ Aigner (1985).
  3. ↑ 3.0 3.1 3.2 3.3 Brightwell, Felsner & Trotter (1995).
  4. ↑ 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.
  5. ↑ Linial (1984), Theorem 2.
  6. ↑ 6.0 6.1 Trotter, Gehrlein & Fishburn (1992).
  7. ↑ 7.0 7.1 7.2 7.3 Peczarski (2006).
  8. ↑ 8.0 8.1 Peczarski (2008).
  9. ↑ Zaguia (2012)
  10. ↑ Brightwell (1989).
  11. ↑ Kahn & Saks (1984); Khachiyan (1989); Kahn & Linial (1991); Felsner & Trotter (1993).
  12. ↑ Saks (1985).
  13. ↑ Brightwell & Winkler (1991).

References