Proof of the Kahn Saks Conjecture
In the authors' words
Let be the probability that precedes in a uniformly random linear extension of an -element poset , and define the balancing coefficient to be with . We prove (Theorem 1) that sufficiently large width forces to be arbitrarily close to , 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 vertices, or an almost fixed order on vertices with one further vertex inserted uniformly among the slots. We also show that, for fixed , the first possibility must occur within any antichain of size .
Main resultThe abstract does not state a limitation.
Appeared: Monday, September 28. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 25 pages