Random Sorting Processes (06frg501)

Objectives

Our goal is to make progess on rigorous analysis of random sorting networks. The main conjectures are the Sphere Geodesic Conjecture mentioned above, and the Flattened Sphere Measure Conjecture, which describes the limiting distribution of the sphere geodesics. We hope to make progress on these and other natural conjectures and open problems. It would also be desirable to further our understanding of the correlation between the particles in the half-way permutation. The particles in this graphical representation of a sorting network seem to exhibit a kind of repulsion which is typical of determinantal point processes such as the eigenvalues of random matrices or the zeroes of Gaussian analytic functions.

Progress on this fascinating and challenging subject appears to require combination of ideas from several different areas of mathematics. A BIRS Focussed Research Group would provide the perfect opportunity for this by allowing free interchange of ideas between experts in these areas for a concentrated period. Much of the progress so far on the subject was achieved in this way at a recent programme held at MSRI. We plan to start with informal presentations covering various aspects of the problem and current progress, and identifying key goals and possible approaches. The remainder of the time would be spent working collaboratively on these goals.