Circular support in random sorting networks

DOI10.1090/TRAN/7819MaRDI QIDQ5217874zbMATH OpenOpenAlexWikidataFDO

Authors Duncan Dauvergne, Balint Virag

Publication date 26 February 2020

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.08933

zbMATH Keywords

\(\pi \)-Lipschitz pathsCayley graphrandom sorting networks

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Combinatorial probability (60C05) Searching and sorting (68P10)

Abstract: A sorting network is a shortest path from $12cdotsn$ to $ncdots21$ 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 $pi$-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 $epsilon$ of the edge are within $sqrt2epsilon$ of a sine curve in uniform norm.

Recommendations

• The Archimedean limit of random sorting networks
• Random sorting networks
• Random subnetworks of random sorting networks
• Geometry of permutation limits
• The runsort permuton

Cites work

• A pattern theorem for random sorting networks
• Balanced tableaux
• Combinatorial aspects of the Lascoux-Schützenberger tree
• Combinatorics of Coxeter Groups
• Geometry of permutation limits
• Note on the expected number of Yang-Baxter moves applicable to reduced decompositions.
• On the expected number of commutations in reduced words
• On the number of reduced decompositions of elements of Coxeter groups
• Random sorting networks
• Random sorting networks: local statistics via random matrix laws
• Random subnetworks of random sorting networks
• Reduced decompositions and permutation patterns
• Relating Edelman-Greene insertion to the Little map
• Symmetric functions, Schubert polynomials and degeneracy loci. Transl. from the French by John R. Swallow
• The Archimedean limit of random sorting networks
• The local limit of random sorting networks
• The oriented swap process

Cited in

(13)

• Various formulations and approximations of incompressible fluid motions in porous media
• Absorbing time asymptotics in the oriented swap process
• Sorting networks, staircase Young tableaux, and last passage percolation
• Random sorting networks: local statistics via random matrix laws
• Random sorting networks
• The runsort permuton
• Shift-invariance of the colored TASEP and finishing times of the oriented swap process
• Second class particles and limit shapes of evacuation and sliding paths for random tableaux.
• The Archimedean limit of random sorting networks
• The oriented swap process and last passage percolation
• Ungarian Markov chains
• Random sorting networks: edge limit
• Random subnetworks of random sorting networks

This page was built for publication: Circular support in random sorting networks

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