Diameters of graphs of reduced words and rank-two root subsystems
HTML articles powered by AMS MathViewer
- by Christian Gaetz and Yibo Gao PDF
- Proc. Amer. Math. Soc. 150 (2022), 3283-3296 Request permission
Abstract:
We study the diameter of the graph $G(w)$ of reduced words of an element $w$ in a Coxeter group $W$ whose edges correspond to applications of the Coxeter relations. We resolve conjectures of Reiner–Roichman [Trans. Amer. Math. Soc. 365 (2013), pp. 2279-2802] and Dahlberg–Kim [Diameters of graphs on reduced words of 12 and 21-inflations, arXiv:2010.15758, 2020] by proving a tight lower bound on this diameter when $W=S_n$ is the symmetric group and by characterizing the equality cases. We also give partial results in other classical types which illustrate the limits of current techniques.References
- Samantha Dahlberg and Younghwan Kim, Diameters of graphs on reduced words of 12 and 21-inflations, arXiv:2010.15758, 2020.
- Patrick Dehornoy and Marc Autord, On the distance between the expressions of a permutation, European J. Combin. 31 (2010), no. 7, 1829–1846. MR 2673022, DOI 10.1016/j.ejc.2010.03.003
- Christian Gaetz and Yibo Gao, Separable elements in Weyl groups, Adv. in Appl. Math. 113 (2020), 101974, 23. MR 4035975, DOI 10.1016/j.aam.2019.101974
- James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
- 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
- Victor Reiner and Yuval Roichman, Diameter of graphs of reduced words and galleries, Trans. Amer. Math. Soc. 365 (2013), no. 5, 2779–2802. MR 3020115, DOI 10.1090/S0002-9947-2012-05719-9
- Rodica Simion, Combinatorial statistics on type-B analogues of noncrossing partitions and restricted permutations, Electron. J. Combin. 7 (2000), Research Paper 9, 27. MR 1741331
- 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
- Richard P. Stanley, An introduction to hyperplane arrangements, Geometric combinatorics, IAS/Park City Math. Ser., vol. 13, Amer. Math. Soc., Providence, RI, 2007, pp. 389–496. MR 2383131, DOI 10.1090/pcms/013/08
- J. Tits, A local approach to buildings, The geometric vein, Springer, New York-Berlin, 1981, pp. 519–547. MR 661801
- Jacques Tits, Le problème des mots dans les groupes de Coxeter, Symposia Mathematica (INDAM, Rome, 1967/68) Academic Press, London, 1969, pp. 175–185 (French). MR 0254129
- Fan Wei, Product decompositions of the symmetric group induced by separable permutations, European J. Combin. 33 (2012), no. 4, 572–582. MR 2864442, DOI 10.1016/j.ejc.2011.11.009
Additional Information
- Christian Gaetz
- Affiliation: Department of Mathematics, Harvard University, Cambridge, Massachusetts 02138
- MR Author ID: 1156664
- ORCID: 0000-0002-3748-4008
- Email: crgaetz@gmail.com
- Yibo Gao
- Affiliation: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
- MR Author ID: 1283652
- ORCID: 0000-0003-3060-2259
- Email: gaoyibo@mit.edu
- Received by editor(s): May 31, 2021
- Received by editor(s) in revised form: November 15, 2021
- Published electronically: March 24, 2022
- Additional Notes: The author was supported by a National Science Foundation Graduate Research Fellowship under Grant No. 1122374.
- Communicated by: Patricia L. Hersh
- © Copyright 2022 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 150 (2022), 3283-3296
- MSC (2020): Primary 05E16, 20F55
- DOI: https://doi.org/10.1090/proc/15912
- MathSciNet review: 4439453