PreprintCC BY 4.0arXiv
Proof of the Kahn Saks Conjecture
Abstract
Let ℙ(x≺ y) be the probability that x precedes y in a uniformly random linear extension of an n-element poset P, and define the balancing coefficient to be δ(x,y)=min(ℙ(x≺ y),ℙ(y≺ x)) with δ(P)=maxx,yδ(x,y). We prove (Theorem 1) that sufficiently large width forces δ(P) to be arbitrarily close to 1/2, answering a long-standing conjecture of Kahn and Saks. In fact, we prove the stronger result (Theorem 2) that large width forces one of two configurations in our poset: either a nearly uniform order on k vertices, or an almost fixed order on t vertices with one further vertex inserted uniformly among the t+1 slots. We also show that, for fixed k, the first possibility must occur within any antichain X of size Ω(n2/3).
Related
BibTeX
@misc{aires2026proof,
title = {{Proof of the Kahn Saks Conjecture}},
author = {Max Aires},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30895},
eprint = {2609.30895},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30895},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Proof of the Kahn Saks Conjecture
AU - Max Aires
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.30895
UR - https://arxiv.org/abs/2609.30895
AB - Let ℙ(x≺ y) be the probability that x precedes y in a uniformly random linear extension of an n-element poset P, and define the balancing coefficient to be δ(x,y)=min(ℙ(x≺ y),ℙ(y≺ x)) with δ(P)=max_x,yδ(x,y). We prove (Theorem 1) that sufficiently large width forces δ(P) to be arbitrarily close to 1/2, answering a long-standing conjecture of Kahn and Saks. In fact, we prove the stronger result (Theorem 2) that large width forces one of two configurations in our poset: either a nearly uniform order on k vertices, or an almost fixed order on t vertices with one further vertex inserted uniformly among the t+1 slots. We also show that, for fixed k, the first possibility must occur within any antichain X of size Ω(n^2/3).
ER -