Circular support in random sorting networks
HTML articles powered by AMS MathViewer
- by Duncan Dauvergne and Bálint Virág PDF
- Trans. Amer. Math. Soc. 373 (2020), 1529-1553 Request permission
Abstract:
A sorting network is a shortest path from $12 \cdots n$ to $n \cdots 2 1$ 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 $\sqrt {2\epsilon }$ of a sine curve in uniform norm.References
- Omer Angel, Duncan Dauvergne, Alexander E. Holroyd, and Bálint Virág, The local limit of random sorting networks, Ann. Inst. Henri Poincaré Probab. Stat. 55 (2019), no. 1, 412–440. MR 3901651, DOI 10.1214/18-aihp887
- Omer Angel, Vadim Gorin, and Alexander E. Holroyd, A pattern theorem for random sorting networks, Electron. J. Probab. 17 (2012), no. 99, 16. MR 3005717, DOI 10.1214/EJP.v17-2448
- Omer Angel and Alexander E. Holroyd, Random subnetworks of random sorting networks, Electron. J. Combin. 17 (2010), no. 1, Note 23, 7. MR 2644860
- Omer Angel, Alexander Holroyd, and Dan Romik, The oriented swap process, Ann. Probab. 37 (2009), no. 5, 1970–1998. MR 2561438, DOI 10.1214/09-AOP456
- Omer Angel, Alexander E. Holroyd, Dan Romik, and Bálint Virág, Random sorting networks, Adv. Math. 215 (2007), no. 2, 839–868. MR 2355610, DOI 10.1016/j.aim.2007.05.019
- Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups, Graduate Texts in Mathematics, vol. 231, Springer, New York, 2005. MR 2133266
- Duncan Dauvergne, The Archimedean limit of random sorting networks, preprint, arXiv:1802.08934, 2018.
- Paul Edelman and Curtis Greene, Balanced tableaux, Adv. in Math. 63 (1987), no. 1, 42–99. MR 871081, DOI 10.1016/0001-8708(87)90063-6
- Jason Fulman and Larry Goldstein, Stein’s method, semicircle distribution, and reduced decompositions of the longest element in the symmetric group, preprint, arXiv:1405.1088, 2014.
- Adriano Mario Garsia. The saga of reduced factorizations of elements of the symmetric group. Université du Québec [Laboratoire de combinatoire et d’informatique mathématique (LACIM)], 2002.
- Vadim Gorin and Mustazee Rahman, Random sorting networks: local statistics via random matrix laws, preprint, arXiv:1702.07895, 2017.
- Zachary Hamaker and Benjamin Young, Relating Edelman-Greene insertion to the Little map, J. Algebraic Combin. 40 (2014), no. 3, 693–710. MR 3265229, DOI 10.1007/s10801-014-0503-z
- Michał Kotowski and Bálint Virág, Limits of random permuton processes and large deviations for the interchange process, in preparation, 2018.
- David P. Little, Combinatorial aspects of the Lascoux-Schützenberger tree, Adv. Math. 174 (2003), no. 2, 236–253. MR 1963694, DOI 10.1016/S0001-8708(02)00038-5
- Laurent Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs, vol. 6, American Mathematical Society, Providence, RI; Société Mathématique de France, Paris, 2001. Translated from the 1998 French original by John R. Swallow; Cours Spécialisés [Specialized Courses], 3. MR 1852463
- Victor Reiner, Note on the expected number of Yang-Baxter moves applicable to reduced decompositions, European J. Combin. 26 (2005), no. 6, 1019–1021. MR 2143207, DOI 10.1016/j.ejc.2004.06.010
- Mustazee Rahman, Bálint Virág, and Máté Vizer, Geometry of permutation limits, preprint, arXiv:1609.03891, 2016.
- Richard P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin. 5 (1984), no. 4, 359–372. MR 782057, DOI 10.1016/S0195-6698(84)80039-6
- Bridget Eileen Tenner, Reduced decompositions and permutation patterns, J. Algebraic Combin. 24 (2006), no. 3, 263–284. MR 2260018, DOI 10.1007/s10801-006-0015-6
- Bridget Eileen Tenner, On the expected number of commutations in reduced words, Australas. J. Combin. 62 (2015), 147–154. MR 3337183
- Benjamin Young, A Markov growth process for Macdonald’s distribution on reduced words, preprint, arXiv:1409.7714, 2014.
Additional Information
- Duncan Dauvergne
- Affiliation: Department of Mathematics, University of Toronto, 40 St. George Street, Toronto, Ontario M35 2E4, Canada
- Address at time of publication: Department of Mathematics, Princeton University, 304 Washington Road, Princeton, New Jersey 08544
- MR Author ID: 641409
- Bálint Virág
- Affiliation: Department of Mathematics, University of Toronto, 40 St. George Street, Toronto, Ontario M35 2E4, Canada
- MR Author ID: 1114287
- Received by editor(s): May 22, 2018
- Received by editor(s) in revised form: October 31, 2018
- Published electronically: November 15, 2019
- Additional Notes: The first author was supported by an NSERC CGS D scholarship.
The second author was supported by the Canada Research Chair program, the NSERC Discovery Accelerator grant, the MTA Momentum Random Spectra research group, and the ERC consolidator grant 648017 (Abert). - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 373 (2020), 1529-1553
- MSC (2010): Primary 60C05; Secondary 05E10, 68P10
- DOI: https://doi.org/10.1090/tran/7819
- MathSciNet review: 4068272