Departmental Colloquium

Event Information The Archimedean limit of random sorting networks
16:00 on Wednesday September 26, 2018
17:00 on Wednesday September 26, 2018
BA6183, Bahen Center, 40 St. George St.
Duncan Dauvergne
http://www.math.toronto.edu/ddauver/
University of Toronto

Consider a list of n particles labelled in increasing order. A sorting network is a way of sorting this list into decreasing order by swapping adjacent particles, using as few swaps as possible. Simulations of large-n uniform random sorting networks reveal a surprising and beautiful global structure involving sinusoidal particle trajectories, a semicircle law, and a theorem of Archimedes. Based on these simulations, Angel, Holroyd, Romik, and Virag made a series of conjectures about the limiting behaviour of sorting networks. In this talk, I will discuss how to use the local structure of random sorting networks to prove these conjectures.