Every unsorted pair is almost fair — the 1/3–2/3 conjecture

A linear extension of a poset P is a total order of its elements consistent with every relation of P1. Draw one uniformly at random and write P(x < y) for the probability that x lands below y.

The constant 1/3 is the best possible: the three-element poset made of a two-element chain plus one incomparable point — 1+2— has exactly three linear extensions, and its isolated point falls below the chain's bottom in exactly one of them2.

Why anyone cares: sorting under partial information. A pair with both outcomes ≥ 1/3 means a single comparison shrinks the count of consistent rankings by a factor of at least 3/2 no matter the answer — so any poset could be fully sorted in about log_3/2 of its extension count comparisons3.

• Open since Kislitsyn posed it in 1968 (rediscovered by Fredman and by Linial).
• The proven constant is (5−√5)/10 ≈ 0.2764, not 1/3: Kahn–Saks (1984) first broke the problem open with 3/114, and Brightwell–Felsner–Trotter (1995) pushed to the golden-ratio constant.
• The golden-ratio constant is a real wall: there is an infinite poset where (5−√5)/10 is exactly tight — so any proof of 1/3 must genuinely use finiteness5.
• Proved for classes:width-2 posets (Linial 1984), semiorders (Brightwell 1989), N-free posets (Zaguia), posets whose comparability structure is otherwise special — and, by Peczarski's computations, every poset with at most 11 elements6.

The conjecture, executable. Pick a poset — or roll a random one — and get every incomparable pair's exact order probability as a BigInt fraction, the best balanced pair (★, highlighted in the diagram), and the exact comparison against 1/3. No floating point participates in any verdict.

Things worth trying: 1+2, the extremal seed, sits at exactly 1/3. The hook H(4) and the tower (1+2) ⊕ (1+2)land at exactly 1/3 too — they are the §5 characterization made clickable (note the tower's 9 = 3² extensions and every pair at 1/3). The Boolean cube B₃ is rigid with symmetry: its best pair is perfectly fair at 1/2. Random posets essentially never come close to 1/3.

Iteration 1 of our campaign: enumerate every poset up to isomorphism on n ≤ 9 elements — growing each poset by attaching a new maximal element over every order ideal, deduplicating canonically, and cross-checking the census against OEIS A000112 at every size7. Verdict:

• Zero posets below 1/3 — the conjecture survives, exactly, on all 2,769,953 non-chain posets with at most 10 elements. (The n = 10 level — all 2,567,284 posets, reached through 8,070,524 generation candidates — runs in an early-exit mode that records the verdict and the extremal census but not the full spectrum; n ≤ 9 has the complete spectrum above.)
• The minimum never moves: min b(P) is exactly 1/3 at every size, achieved by 1, 2, 3, 5, 8, 12, 18, 27 posets for n = 3…108.
• The spectrum hugs 1/3 from above: the runner-up balance — the smallest value strictly greater than 1/3 — decreases at every level: 2/5, 4/11, 5/14, 5/14, 16/45, 6/17, and 37/106 at n = 109.
• Beyond exhaustion, sampling: 8,000 random posets on 10–13 elements (two generation models, seeded and reproducible) — none below 1/3, several landing exactly on it. Sampling is evidence, not proof, and is logged as such.

Who lives at exactly 1/3? The campaign's later iterations dissected the census, and one observation graduated to a proof:

• Theorem (in-house, elementary).The hook H(k) — a chain c₁ < … < c_kwith two incomparable feet x < c₁ and y < c₂ — satisfies b(H(k)) = 1/3 exactly, for every k ≥ 110.
• Theorem 2 (in-house — the Tower Theorem). Every ordinal sum of blocks, each a single point or a 1+2, with h ≥ 1 blocks of the 1+2 kind, has e = 3^h, every incomparable pair at exactly {1/3, 2/3}, and hence b = 1/311.
• And the converse holds everywhere we can see: every extremal poset in the verified range issuch a tower. All 175 known extremal posets (exhaustive through n = 10, grown class through n = 12) ordinal-decompose into {point, 1+2} blocks, and generating one tower per composition of n into parts {1, 3} (excluding the all-1s chain) reproduces the extremal class exactly — canonical set equality at every level. The census therefore obeys census(n) = #compositions(n; {1,3}) − 112.

The picture is now sharp: 1/3 is not a small-n accident — it is the exact floor of an explicit, fully characterized family (towers of 1+2 blocks) that exists at every size, and nothing else touches it anywhere in the verified range. A proof of the conjecture has to explain why nothing does worse than a 1+2 block; a disproof has to beat one — and our sweeps certify nothing does, anywhere below 11 elements.

• The good tools overshoot their target.The Kahn–Saks machinery controls balance through geometry (order polytopes, Alexandrov–Fenchel), and geometry doesn't know the poset is finite — which is fatal, because at the infinite limit the true constant really is (5−√5)/10, not 1/3 (§2). The gap between 0.2764 and 0.3333 is exactly the gap between geometric and combinatorial control.
• The extremal structure is delicate. Equality demands extension counts in perfect 1:2 ratio — a Diophantine coincidence that the hook family manufactures at every size (§5). Inequality proofs hate families of exact equality cases: there is no slack anywhere near them to give away.
• Exhaustion cannot finish. Poset counts grow super-exponentially (A000112: 183,231 at n = 9; over 2.5 million at n = 10). Machine sweeps sharpen the target and kill conjectured strengthenings, but the statement quantifies over all finite posets — same asymmetry as every problem in this lab.

• S. S. Kislitsyn, Finite partially ordered sets and their associated sets of permutationsMat. Zametki 4 (1968). Where the conjecture begins.
• J. Kahn & M. Saks, Balancing poset extensionsOrder 1 (1984). The 3/11 breakthrough; mixed volumes enter combinatorics.
• G. Brightwell, S. Felsner & W. T. Trotter, Balancing pairs and the cross product conjectureOrder 12 (1995). The (5−√5)/10 bound, still the record.
• G. Brightwell, Balanced pairs in partial ordersDiscrete Mathematics 201 (1999). The survey of record for the conjecture.
• M. Peczarski, The gold partition conjectureOrder 23 (2006). The computational frontier: every poset with ≤ 11 elements.
• G. Brightwell & P. Winkler, Counting linear extensionsOrder 8 (1991). Why exact counting is #P-complete in general — and why small cases are still fully computable.