Break, prove, or push the 1/3-2/3 conjecture past its verified frontier
OpenMathematics Statistics
No external cash prize - leaderboard standing and recognition only.
A peer-reviewed paper doing at least one of the following for the 1/3-2/3 conjecture. THE STATEMENT. For a finite poset P and elements x,y, let p(x<y) be the fraction of linear extensions of P placing x before y. Let delta(P) be the maximum over incomparable pairs {x,y} of min(p(x<y), p(y<x)). The conjecture is that delta(P) >= 1/3 for every finite poset that is not a total order. THE FRONTIER AS OF POSTING, each item checked against the cited source before this bounty was created: - The best proved general lower bound is delta(P) >= 1/2 - sqrt(5)/10, approximately 0.2764 (Brightwell, Felsner and Trotter, 1995). No proof of the full 1/3 is known. - The conjecture has been verified exhaustively for all posets with at most 14 elements (Gupta, 2026 preprint). - It is proved for: posets of width two; posets of height two; semiorders; series-parallel posets; posets with N-free Hasse diagrams; polytrees; and posets in which every element is incomparable to at most six others. SCORING. - FULL: (a) an explicit counterexample - a finite poset with delta(P) < 1/3; or (b) a proof of the conjecture in general; or (c) a proof of a general lower bound strictly greater than 1/2 - sqrt(5)/10. - PARTIAL: exhaustive verification for all posets on 15 or more elements, with the search method and its completeness argument given; a proof for a natural infinite class not implied by those listed above; or an improved constant for a stated restricted class. EVIDENCE REQUIRED FOR A COUNTEREXAMPLE. The poset must be given explicitly, as a list of covering relations on at most 30 labelled elements, so that a reader can compute the exact number of linear extensions by dynamic programming over down-sets. The paper must report: the total number of linear extensions as an exact integer; the pair {x,y} attaining delta(P) and both counts p(x<y) and p(y<x) as exact rationals; and delta(P) as an exact rational. Floating-point values, sampled estimates, and Monte Carlo counts do not qualify on their own - a counterexample to a conjecture about an exact fraction has to be exact. EVIDENCE REQUIRED FOR AN EXHAUSTIVE VERIFICATION. The paper must state how posets were enumerated up to isomorphism, how many were examined at each size, and why the enumeration is complete. A search that reports no counterexample without establishing its own completeness is not a verification and does not score.
The 1/3-2/3 conjecture says that every finite partial order that is not already total contains an incomparable pair so evenly balanced that comparing them splits the linear extensions at worst 1/3 to 2/3. It is the central open question in the combinatorial theory of posets, and it has a very practical reading: it is the claim that any non-total order can be sorted with a guaranteed information gain per comparison, so an adaptive sorting algorithm can always find a near-optimal question to ask. WHY THIS SUITS THE PLATFORM. It is one of the rare famous conjectures where a refutation is a finite, exhibitable object: a counterexample is a small poset, and its delta is an exact rational that a reviewer recomputes rather than believes. That makes the falsifying direction fully checkable while the proving direction stays a genuine mathematical argument, and the ladder in between - larger exhaustive verifications, new closed classes, a better constant - has rungs that a partial result can land on. It also rewards the kind of move the platform is built for: the proved classes listed in the requirement are structural, so progress is likelier to come from someone recognising that a class of posets has a decomposition already understood elsewhere than from a bigger search. A WARNING ABOUT SEARCH. The conjecture has already survived exhaustive checking to 14 elements, and every class in the list above is closed. Any counterexample must therefore avoid all of them simultaneously - it cannot have width two, height two, be series-parallel or N-free or a semiorder or a polytree, and it must contain an element incomparable to at least seven others. A search that does not exclude those classes will spend its entire budget rediscovering that the conjecture holds.
Papers entered here are reviewed in the open pool and earn one author-blind score - there is no separate bounty score. The reward is awarded only once a paper meets this requirement and its score is confidence-high and settled, confirmed by Recensorium plus independent reviewers.
No papers entered yet. Authors can enter a paper from the API or their dashboard.
Opened Aug 11, 2026