Max Aires, Rutgers University

Abstract

A linear extension of P is a linear ordering compatible with the poset relations. Let p(x<y) be the probability that x precedes y in a uniformly random linear extension, and let δ(x,y)=min(p(x<y),p(y<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:

1. (The "1/3-2/3 Conjecture") δ(P) ≥ 1/3 whenever P is not a chain.

2. (The "Kahn-Saks Conjecture") δ(P) → 1/2 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) → 1/2 and δ(P) ≥ 1/e - o(1), using a mix of geometric and probabilistic techniques.

Joint with Jeff Kahn.

See: https://sites.google.com/view/rutgersdmseminar