Duncan Dauvergne and Bálint Virág Settled the Random Sorting Networks Conjectures

Posted on May 20, 2018 by Gil Kalai

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.

 

Dan Romik, see also Romik’s mathematical gallery and Romik’s moving sofa page

Sorting networks

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 {{n} \choose {2}} transpositions of the form (i,i+1) whose product is the permutation (n,n-1,\dots,1).

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

{{n}\choose{2}}!/1^n3^{n-1}5^{n-2}\cdots (2n-3)^1,

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 \pi_1,\pi_2,\pi_t 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

Alexander Holroyd’s videotaped lecture on random sorting networks. Holroyd’s random sorting gallery (pictures below are taken from there), and his six other amazing mathematical gallerys. 

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

  1. 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 \sigma^n, 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 \sigma^n. As a corollary of these results, we show that if S_n is embedded into \mathbb R^n 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 \mathbb R^n. 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 \epsilon >0 the number of appearances of the transposition (k,k+1) in every sorting network is O(n^{1+\epsilon}).

This is closely related to the halving line problem. The best lower bound (Klawe, Paterson, and Pippenger) behaves like n \exp (\sqrt {\log n}). A geometric construction giving this bound  is a famous theorem by Geza Toth.   The best known upper bound by Tamal Dey is n^{4/3}.

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 n=5.) Are there analogous phenomena for the associahedron? one can ask.

This entry was posted in Combinatorics, Probability, Updates and tagged , , . Bookmark the permalink.

3 Responses to Duncan Dauvergne and Bálint Virág Settled the Random Sorting Networks Conjectures

  1. JSE says:
    May 20, 2018 at 10:52 pm

    Awesome to see this proved! It was a question one almost couldn’t help but think about.

    Here’s a followup which maybe makes sense. The set of random sorting networks carries a natural “Hurwitz action” of the braid group on (n choose 2) strands — namely, twining strands i and i+1 sends

    (t_1, ..t_i,t_{i+1}, …) to

    (t_1, …. t_i t_{i+1} t_i^{-1}, t_i, ….)

    If whp a sorting network tracks a great circle on the sphere, is there a meaningful way to talk about how a braid “moves” that circle?

    Reply
  2. David Speyer says:
    May 25, 2018 at 8:43 pm

    Great to see this proved!

    @JSE: If I understand your construction correctly then you have misunderstood the definition of sorting network in this paper. A sorting network here is only supposed to use adjacent transpositions (j j+1), where as your action uses all transpositions. Sorting networks with all transpositions are also studied (and also called sorting networks) but they have less structure.

    Reply

  3. Pingback: Greatest Hits 2015-2022, Part I | Combinatorics and more

Leave a comment