Mathematics Atlas

How Proof Is Made
Sign In
Text size
100%
Theme

Switch Atlas

Conjecture

1/3-2/3 Conjecture

Combinatorics

The 1/3-2/3 conjecture, in order theory, states that when comparison sorting a set of items, no matter what comparisons have already been performed, it is always possible to choose the next comparison so that it reduces 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 such that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Statement
In every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y such that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y. 1
Proposed Year
1968 1
Progress Toward Resolution
Unresolved. In 1995 Brightwell, Felsner and Trotter proved the bound of about 0.276 in place of 1/3, and the conjecture is verified for width two, height two and small posets. 1
Classification
Resolution Status
Open 1
Prize Status
Prize Status (category)
No Prize Offered 1
Connections

In Branch

Order Theory, Branches of Mathematics
Source 1/3-2/3 conjecture (Wikipedia)
Sources
1. 1/3-2/3 Conjecture (Wikipedia)
Wikimedia Foundation
  • Lead section
    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
  • Statement section
    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.
  • History section
    The conjecture was initially formulated by Sergey Kislitsyn in 1968.
  • Progress on bounds section
    for any finite partial order P that is not total, δ(P) ≥ 1/2 − √5/10 ≈ 0.276.
View the Source
1/3-2/3 conjecture (Wikipedia)
In Branch: Order Theory, Lead sentenceView the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.