Sorting probabilities and random walksMathematical Physics & Probability
|Speaker:||Greta Panova, University of Southern California|
|Start time:||Wed, Oct 27 2021, 4:10PM|
Linear extensions (completions to total order) of partially ordered sets (posets) is a central theme in combinatorics and beyond. The famous 1/3-2/3 conjecture states that in every not totally ordered poset there are two elements x,y, such that the probability Pr[x<y] that x appears before y in a uniformly random total order is between 1/3 and 2/3. The asymptotic version of this conjecture [Kahn-Saks conjecture] states that the sorting probability (the minimum of |Pr[x<y]-Pr[y<x]| over all x,y) goes to 0 as the size of the maximal antichain grows to infinity.
We consider the last question for posets which are Young diagrams and study random Standard Young Tableaux (SYTs) of skew shapes, proving a stronger version of the Kahn-Saks conjecture for Young diagrams of fixed length. The proof uses a variety of techniques: a correspondence with restricted monotonous random walks, tight asymptotics of the number of SYTs of skew shapes and evaluations of Schur functions. As a biproduct of these interpretations we generalize results about random walks in "monotone" domains and on various grids proving that the exit probabilities at a vertical boundary are log-concave.
Based on a series of works with Swee Hong Chan and Igor Pak.