Videos

Balancing Extensions in Posets of Large Width

Presenter
September 22, 2025
Abstract
A linear extension of P is a linear ordering compatible with the poset relations. Let p(x less than y) be the probability that xprecedes y in a uniformly random linear extension, and let δ(x,y)=min(p(x less than y),p(y less than x)) and δ(P) be the maximum value of δ(x,y)over all x,y in P. The following two conjectures about δ(P)are both well-known: (The "1/3-2/3 Conjecture") δ(P) greater than or equal to 13whenever P is not a chain.(The "Kahn-Saks Conjecture") δ(P)→12 as w(P)→∞ (where w(P) is the maximum size of an antichain in P).While still far from either of these, we prove a number of conditions for δ(P)→12 and δ(P) greater than or equal to 1e−o(1), using a mix of geometric and probabilistic techniques. Joint with Jeff Kahn.