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
Link from a Wikipage to another Wikipage
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
Link from a Wikipage to an external page
Wikipage page ID
28.745.947
page length (characters) of wiki page
Wikipage revision ID
1.000.611.232
Link from a Wikipage to another Wikipage
authorlink
Nati Linial
@en
first
Nati
@en
last
Linial
@en
wikiPageUsesTemplate
hypernym
type
comment
In order theory, a branch of m ...... order place x earlier than y.
@en
label
1/3–2/3 conjecture
@en