Seminar
| Parent Program: | -- |
|---|---|
| Location: | SLMath: Eisenbud Auditorium |
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
Virag.
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification
Secondary Mathematics Subject Classification