The 1/3-2/3 conjecture for linear extensions

Let PP be a finite poset. For distinct elements x,yPx,y\in P, define

δxy=min{P(xy),P(yx)},\delta_{xy}=\min\{\mathbb{P}(x\prec y),\mathbb{P}(y\prec x)\},

and let

δ(P)=maxxyδxy,\delta(P)=\max_{x\ne y}\delta_{xy},

where the probabilities are taken over a uniformly random linear extension of PP. The 1/3-2/3 conjecture. If PP is not a chain, then δ(P)1/3\delta(P)\geq 1/3. This conjecture is motivated by sorting problems; the bound is known to be tight, but the conjectured constant 1/31/3 remains unresolved, with the best stated general lower bound being (55)/10(5-\sqrt{5})/10.

Sources & referencesView supporting material

Primary source

Max Aires and Jeff Kahn, “Variance vs. range for linear extensions, and balancing extensions in posets of bounded width”, arXiv:2510.26134 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.