Kahn–Saks conjecture on balancing probabilities in linear extensions

About 1 year old · traced to

Let PP be a finite poset, let w(P)w(P) denote its width, and for distinct elements x,y∈Px,y\in P define

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

with

δ(P)=max⁡x≠yδ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.

References

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.