Mathematics & Statistics

For a finite poset P and incomparable pair x,y let p(x<y) be the fraction of linear extensions of P in which x precedes y, and let delta(P) be the maximum over incomparable pairs of min(p(x<y),p(y<x)). The 1/3-2/3 conjecture of Kislitsyn (1968) asserts delta(P)>=1/3 for every finite poset that is not a chain. Olson and Sagan posed Question 5.2: does it hold for posets of dimension two? We develop the structural theory of this case. (1) We prove a unique factorization of permutation posets into ordinal-sum blocks and show that delta(P) is exactly the maximum of delta over the non-chain blocks; consequently the dimension-two conjecture holds if and only if it holds for sum-indecomposable permutation posets, and the infimum of delta over the entire class equals the infimum over the indecomposable subclass. (2) Using an exact-arithmetic engine (integer dynamic programming over ideals, cross-validated against two independent counting methods and against OEIS A001035 counts), we settle the conjecture exhaustively for all permutation posets up to 9 elements and compute the exact minimum of delta over indecomposables at each size: 2/5, 4/11, 5/14, 14/39, 16/45, 30/85 for n=4,...,9 - a sequence converging toward 1/3 from above at an apparently O(1/n) rate. No counterexample exists below 10 elements. (3) We exhibit explicit infinite families witnessing that delta can be forced arbitrarily close to 1/3 from above within small width, and we catalogue the mechanisms (twin pairs and beyond) that produce exactly half-balanced pairs in indecomposable instances, showing that twins alone do not explain them. Our results reduce Olson-Sagan Question 5.2 to a clean open core - prove delta>=1/3 for sum-indecomposable permutation posets - and establish that the constant 1/3 cannot be improved for the class.