A short summary: The beautiful decade-old conjectures on random sorting networks by Omer Angel, Alexander Holroyd, Dan Romik, and Bálint Virág, have now been settled by Duncan Dauvergne and Bálint Virág in two papers: Circular support in random sorting networks, by Dauvergne and Virág, and The Archimedean limit of random sorting networks by Duncan Dauvergne.
Sorting is one of the most important algorithmic tasks and it is closely related to much beautiful mathematics. In this post, a sorting network is a shortest path from 12…n to n…21 in the Cayley graph of S_n generated by nearest-neighbour swaps. In other words, a sorting networks is a sequence of transpositions of the form whose product is the permutation .
Sorting networks, as we just defined, appear in other contexts and under other names. Also the term “sorting networks” is sometimes used in a different way, and in particular, allows swaps that are not nearest neighbors. (See the slides for Uri Zwick’s lecture on sorting networks.)
Richard Stanley proved a remarkable formula
for the number of sorting networks or reduced decomposition of the permutation n…21. (We mentioned it in this post. )
We can also think about sorting networks as maximal chains in the weak Bruhat order of the symmetric group. Another related notion in combinatorial geometry is that of “(simple) allowable sequence of permutations”. an allowable sequence of permutation is a sequence of permutations starting with 12…n and ending with n…21 such that each permotation in the sequence is obtained by the previous one by reverseing one set or several disjoint sets of consecutive elements. See, e.g., this paper of Hagit last on two proofs of the Sylvester-Gallai theorem via allowable sequence of permutations.
Random Sorting networks
Random sorting networks were considered a decade ago in a beautiful paper by Angel, Holroyd, Romik, and Virág . In this paper some brave conjectures were made
Conjecture 1: the trajectories of individual particles converge to random sine curves,
Conjecture 2: the permutation matrix at half-time converges to the projected surface measure of the 2-sphere.
There are more conjectures! I will just show you one additional picture
The rhombic tiling corresponding to a uniform random sorting network:
The works by Dauvergne and Virág
In two recent breakthrough papers all those conjectures were proved. The papers are
- Circular support in random sorting networks, by Dauvergne and Virag
…in which they show the tight support bound for the circle seen in the halfway permutation, as well as the tight Lipschitz bound for trajectories.
2. The Archimedean limit of random sorting networks, by Dauvergne.
…in which all the 2007 conjectures are proved. Here is the abstract:
A sorting network (also known as a reduced decomposition of the reverse permutation), is a shortest path from 12⋯n to n⋯21 in the Cayley graph of the symmetric group Sn generated by adjacent transpositions. We prove that in a uniform random n-element sorting network , that all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-t permutation matrix measures of . As a corollary of these results, we show that if is embedded into via the map τ↦(τ(1),τ(2),…τ(n)), then with high probability, the path σn is close to a great circle on a particular (n−2)-dimensional sphere in . These results prove conjectures of Angel, Holroyd, Romik, and Virag.
These papers build on previous results, including some in the 2007 paper, recent results by Gorin and Rahman from Random sorting networks: local statistics via random matrix laws, as well as those of Angel, Dauvergne, Holroyd and Virág from their paper on the local limit of random sorting networks.
The halving (pseudo)lines problem
Let me mention an important conjecture on sorting networks,
Conjecture: For every k, and the number of appearances of the transposition (k,k+1) in every sorting network is .
This is closely related to the halving line problem. The best lower bound (Klawe, Paterson, and Pippenger) behaves like . A geometric construction giving this bound is a famous theorem by Geza Toth. The best known upper bound by Tamal Dey is .
I am amazed that I did not blog about the halving lines problem and about allowable sequences of permutations in the past. (I only briefly mentioned the problem and allowable sequences of permutations in one earlier post on a certain beautiful geometric discrepancy problem.)
The permutahedron makes an appearance
The permutahedron is the Cayley graph of the symmetric group Sn generated by the nearest-neighbour swaps (12), (23), (34) and (n-1n). (Here .) Are there analogous phenomena for the associahedron? one can ask.