Kahn–Saks conjecture on balancing probabilities in linear extensions

Let PP be a finite poset, let w(P)w(P) denote its width, and 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)\},

with

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

where the probabilities are over a uniformly random linear extension of PP. Kahn–Saks conjecture. If w(P)w(P)\to\infty, then δ(P)1/2\delta(P)\to 1/2. The conjecture formalizes the expectation that posets of increasingly large width contain a pair of elements whose relative order is asymptotically balanced. Its status is not resolved in the supplied text.

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.