Random sorting networks: edge limit

Publication date 18 July 2022

Abstract: A sorting network is a shortest path from

12 d o t s n

to

n d o t s 21

in the Cayley graph of the symmetric group

m a t h f r a k S_{n}

spanned by adjacent transpositions. The paper computes the edge local limit of the uniformly random sorting networks as

n o i n f t y

. We find the asymptotic distribution of the first occurrence of a given swap

(k, k + 1)

and identify it with the law of the smallest positive eigenvalue of a

2 k i m e s 2 k

aGUE (an aGUE matrix has purely imaginary Gaussian entries that are independently distributed subject to skew-symmetry). Next, we give two different formal definitions of a spacing -- the time distance between the occurrence of a given swap

(k, k + 1)

in a uniformly random sorting network. Two definitions lead to two different expressions for the asymptotic laws expressed in terms of derivatives of Fredholm determinants.

This page was built for publication: Random sorting networks: edge limit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405396)