Probability and Statistics Seminar: Balancing Posets and the 1/3-2/3 Conjecture

Max Aires, USC Title: Balancing Posets and the 1/3-2/3 Conjecture Abstract: A linear extension of P is a total 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 famous "1/3-2/3" Conjecture, first made over 50 years ago, posits that δ(P)≥1/3 for all posets with at least 2 linear extensions. For three decades, the best progress on this conjecture was a lower bound of (5-√5)/10, which is tight in the case of infinite …