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.

##### Wikipage redirect

##### sameAs

##### primaryTopic

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.

##### has abstract

In order theory, a branch of m ...... order place x earlier than y.

@en

##### thumbnail

##### Link from a Wikipage to an external page

##### Wikipage page ID

28.745.947

##### Wikipage revision ID

728.320.459

##### authorlink

##### subject

##### hypernym

##### type

##### comment

In order theory, a branch of m ...... order place x earlier than y.

@en

##### label

1/3–2/3 conjecture

@en