A sorting network is a shortest path from 12···n to n···21 in the Cayley graph of the symmetric group generated by adjacent transpositions. For a uniform random sorting network, we prove that in the global limit, particle trajectories are supported on π-Lipschitz paths. We show that the weak limit of the permutation matrix of a random sorting network at any fixed time is supported within a particular ellipse. This is conjectured to be an optimal bound on the support. We also show that in the global limit, trajectories of particles that start within distance #x220A; of the edge are within √2#x220A; of a sine curve in uniform norm.
|Original language||English (US)|
|Number of pages||25|
|Journal||Transactions of the American Mathematical Society|
|State||Published - 2020|
All Science Journal Classification (ASJC) codes
- Applied Mathematics