Dan Romik: Finishing times in random sorting networks and staircase shape Young tableaux

Abstract

The oriented swap process is a model for a random sorting network, in which N particles labeled 1,...,N arranged on the discrete lattice [1,N] start out in increasing order and then perform successive adjacent swaps at random times until they reach the reverse configuration N,...,1. I will discuss recent joint work with Elia Bisi, Fabio Cunden and Shane Gibbons in which we discovered that the time it takes for this process to terminate is equal in distribution to the time it takes a randomly growing Young diagram to fill a staircase shape with N-1 rows, but were only able to prove this rigorously for N<7. The proof reduces to verifying an algebraic identity between two generating functions, one involving a summation over sorting networks of order N and the other involving a summation over staircase shape Young tableaux. For the general N case that is still conjectural, the well-known Edelman-Greene bijection relating these two sets may end up being relevant, but new ideas seem to be required. The talk will include entertaining computer simulations and a demonstration of computer-assisted proofs, and assumes only an elementary combinatorics background.