The Archimedean limit of random sorting networks
HTML articles powered by AMS MathViewer
- by Duncan Dauvergne;
- J. Amer. Math. Soc. 35 (2022), 1215-1267
- DOI: https://doi.org/10.1090/jams/993
- Published electronically: November 17, 2021
- HTML | PDF | Request permission
Abstract:
A sorting network (also known as a reduced decomposition of the reverse permutation) is a shortest path from $12 \cdots n$ to $n \cdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by adjacent transpositions. We prove that in a uniform random $n$-element sorting network $\sigma ^n$, 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 $\tau \mapsto (\tau (1), \tau (2), \dots \tau (n))$, then with high probability, the path $\sigma ^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 Virág.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, DOI 10.37236/472
- 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
- Arkady Berenstein, Sergey Fomin, and Andrei Zelevinsky, Parametrizations of canonical bases and totally positive matrices, Adv. Math. 122 (1996), no. 1, 49–149. MR 1405449, DOI 10.1006/aima.1996.0057
- Sara Billey and Mark Haiman, Schubert polynomials for the classical groups, J. Amer. Math. Soc. 8 (1995), no. 2, 443–482. MR 1290232, DOI 10.1090/S0894-0347-1995-1290232-1
- Sara C. Billey, William Jockusch, and Richard P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), no. 4, 345–374. MR 1241505, DOI 10.1023/A:1022419800503
- Yann Brenier, The least action principle and the related concept of generalized flows for incompressible perfect fluids, J. Amer. Math. Soc. 2 (1989), no. 2, 225–255. MR 969419, DOI 10.1090/S0894-0347-1989-0969419-8
- Yann Brenier, Generalized solutions and hydrostatic approximation of the Euler equations, Phys. D 237 (2008), no. 14-17, 1982–1988. MR 2449787, DOI 10.1016/j.physd.2008.02.026
- Duncan Dauvergne and Bálint Virág, Circular support in random sorting networks, Trans. Amer. Math. Soc. 373 (2020), no. 3, 1529–1553. MR 4068272, DOI 10.1090/tran/7819
- 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
- Serge Elnitsky, Rhombic tilings of polygons and classes of reduced words in Coxeter groups, J. Combin. Theory Ser. A 77 (1997), no. 2, 193–221. MR 1429077, DOI 10.1006/jcta.1997.2723
- 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.
- Max Gross and Nicole Marsaglia, Vexillary permutations, https://sites.math.washington.edu/~reu/papers/2012/nicole_max/vex.pdf, 2012.
- Jacob E. Goodman and Richard Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A 29 (1980), no. 2, 220–235. MR 583961, DOI 10.1016/0097-3165(80)90011-4
- Vadim Gorin and Mustazee Rahman, Random sorting networks: local statistics via random matrix laws, Probab. Theory Related Fields 175 (2019), no. 1-2, 45–96. MR 4009705, DOI 10.1007/s00440-018-0886-1
- Mark D. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math. 99 (1992), no. 1-3, 79–113. MR 1158783, DOI 10.1016/0012-365X(92)90368-P
- 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
- Olav Kallenberg, Foundations of modern probability, Probability Theory and Stochastic Modelling, vol. 99, Springer, Cham, [2021] ©2021. Third edition [of 1464694]. MR 4226142, DOI 10.1007/978-3-030-61871-1
- Michael Kotowski and Bálint Virág, Large deviations for the interchange process on the interval and incompressible flows, preprint arXiv:2110.12203, 2021.
- 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
- Svante Linusson, Samu Potka, and Robin Sulzgruber, On random shifted standard Young tableaux and 132-avoiding sorting networks, Algebr. Comb. 3 (2020), no. 6, 1231–1258. MR 4184044, DOI 10.5802/alco
- Alain Lascoux and Marcel-Paul Schützenberger, Schubert polynomials and the Littlewood-Richardson rule, Lett. Math. Phys. 10 (1985), no. 2-3, 111–124. MR 815233, DOI 10.1007/BF00398147
- Bernard Leclerc and Andrei Zelevinsky, Quasicommuting families of quantum Plücker coordinates, Kirillov’s seminar on representation theory, Amer. Math. Soc. Transl. Ser. 2, vol. 181, Amer. Math. Soc., Providence, RI, 1998, pp. 85–108. MR 1618743, DOI 10.1090/trans2/181/03
- Peter Magyar, Schubert polynomials and Bott-Samelson varieties, Comment. Math. Helv. 73 (1998), no. 4, 603–636. MR 1639896, DOI 10.1007/s000140050071
- 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
- Eric Marberg, A symplectic refinement of shifted Hecke insertion, J. Combin. Theory Ser. A 173 (2020), 105216, 50. MR 4067984, DOI 10.1016/j.jcta.2020.105216
- 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
- Dan Romik, The surprising mathematics of longest increasing subsequences, Institute of Mathematical Statistics Textbooks, vol. 4, Cambridge University Press, New York, 2015. MR 3468738
- Mustazee Rahman, Bálint Virág, and Máté Vizer, Geometry of permutation limits, Combinatorica 39 (2019), no. 4, 933–960. MR 4015358, DOI 10.1007/s00493-019-3817-6
- A. I. Shnirel′man, The geometry of the group of diffeomorphisms and the dynamics of an ideal incompressible fluid, Mat. Sb. (N.S.) 128(170) (1985), no. 1, 82–109, 144 (Russian). MR 805697
- 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
- John R. Stembridge, Some combinatorial aspects of reduced words in finite Coxeter groups, Trans. Amer. Math. Soc. 349 (1997), no. 4, 1285–1332. MR 1389789, DOI 10.1090/S0002-9947-97-01805-9
- Michael Struwe, Variational methods, 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 34, Springer-Verlag, Berlin, 1996. Applications to nonlinear partial differential equations and Hamiltonian systems. MR 1411681, DOI 10.1007/978-3-662-03212-1
- 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.
Bibliographic Information
- Duncan Dauvergne
- Affiliation: Department of Mathematics, University of Toronto, 40 St. George St, Toronto, ON M5S 2E4, Canada
- MR Author ID: 1114287
- Email: duncan.dauvergne@utoronto.ca
- Received by editor(s): June 21, 2019
- Received by editor(s) in revised form: August 17, 2021
- Published electronically: November 17, 2021
- © Copyright 2021 American Mathematical Society
- Journal: J. Amer. Math. Soc. 35 (2022), 1215-1267
- MSC (2020): Primary 60C05; Secondary 05A05, 68P10
- DOI: https://doi.org/10.1090/jams/993
- MathSciNet review: 4467309