Algebraic Combinatorics Seminar - Greta Panova

Title: Sorting probabilities for Young diagrams and beyond

Abstract:

Sorting probability for a partially ordered set P is defined as the min |Pr[x<y] - Pr[y<x]| going over all pairs of elements x,y in P, where Pr[x<y] is the probability that in a uniformly random linear extension (extension to total order) x appears before y.

The celebrated 1/3-2/3 conjecture states that for every poset the sorting probability is at most 1/3, i.e. there are two elements x and y, such that 1/3\leq Pr[x<y] \leq 2/3.

The asymptotic extension of this conjecture states that the sorting probability goes to 0 as the width (maximal antichain) of the poset grows to infinity.

We will prove the last conjecture for Young diagrams, where the linear extensions are Standard Young Tableaux.

Beyond SYTs, these conjectures bring out a variety of poset inequalities, which have connections to both algebra as in group actions and probability as in random walks.  

Based on joint works with Swee Hong Chan and Igor Pak.