Subscribe to Events

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 an 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 ? Pr[x < y] ? 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. We also discuss notable special cases relating to random walks. Based on joint works with Swee Hong Chan and Igor Pak.