Mathematical Sciences Research Institute

Home » Random sorting networks


Random sorting networks December 02, 2010 (01:00 PM PST - 02:00 PM PST)
Parent Program: --
Location: MSRI: Simons Auditorium
Description Speaker: Dan Romik

Abstract:  I will describe results and conjectures about "random sorting
processes", which are interacting particle systems involving N numbered
particles on a finite one-dimensional lattice. Initially the particles are
arranged in increasing order, so that the particle numbered k is in
position k. They then start performing adjacent swaps until their order
has been completely reversed, so that each particle k is in position
N+1-k. Swaps are only performed if they move the configuration closer to the
final one; in other words, any pair of particles will only swap once from
increasing to decreasing order and then never swap back. In this
combinatorial picture, randomness can be introduced in two natural ways:
first, by considering uniformly random sequences of swaps that are valid
"sorting sequences". Secondly (and inequivalently), by performing swaps in
uniformly chosen random positions at each given time, conditioned not to
swap pairs of particle that have already swapped. The first model can be
partially understood using a connection to the combinatorics of Young
tableaux, but an important (and visually very compelling) question remains
open. The second model can be represented in terms of a coupled system of
totally asymmetric simple exclusion processes (TASEPs), which allows us to
derive precise asymptotic results, including a Tracy-Widom limiting law
for the "finishing times" of individual particles.
The talk is based on joint works with Omer Angel, Ander Holroyd and Balint
No Video Uploaded
Abstract/Media No Abstract No Notes/Supplements Uploaded No Video Files Uploaded