Balancing extensions in posets of large width

We revisit two old conjectures on linear extensions in finite partially ordered sets (posets) P. [A linear extension of P is a linear ordering compatible with the poset relations. A chain (antichain) is a totally ordered (unordered) set, and the width, w(P), is the maximum size of an antichain in P.] Let p(x ≺ y) be the probability that x precedes y in a uniformly random linear extension, and set δxy = min{p(x ≺ y),p(y ≺ x)} and δ(P) = maxδxy, the max over distinct x,y ∈ P. The conjectures are: Conjecture 1 (the “1/3-2/3 Conjecture”). If P is not a chain then δ(P) ≥ 1/3. Conjecture 2. If w(P) → ∞, then δ(P) → 1/2 (that is, δ(P) > 1/2 −o(1), where o(1) → 0 as w(P) → ∞). We are still far from proving either of these, but make some interesting progress. Joint with Max Aires.

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/