Proof shows large posets force near equal ordering probabilities
Proof of the Kahn Saks Conjecture
Discrete Mathematics
Summary
This paper settles a long-standing question about how items are arranged in special ordered sets called posets. The authors prove that when these sets are wide enough, certain pairs of items almost equally likely appear before one another in random arrangements. They identify two specific patterns that must exist in such large posets. This improves our understanding of how order behaves in complex structured data.
What this means in practice
- •For complexity theorists: Benefit from clarified structure in posets to refine complexity analyses relying on ordering probabilities.
- •For algorithm designers: Use guaranteed poset configurations to improve algorithms for sampling or approximation involving poset linear extensions.
A theory result. No direct application yet.
Authors
Max Aires
Abstract
Let $\mathbb{P}(x\prec 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(\mathbb{P}(x\prec y),\mathbb{P}(y\prec 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})$.