Bender–Knuth Billiards in Coxeter Groups

Barkley, Grant ; Defant, Colin ; Hodges, Eliot ; Kravitz, Noah ; Lee, Mitchell

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e7

Résumé

Let $(W,S)$ be a Coxeter system, and write $S=\{s_i:i\in I\}$, where I is a finite index set. Fix a nonempty convex subset $\mathscr {L}$ of W. If W is of type A, then $\mathscr {L}$ is the set of linear extensions of a poset, and there are important Bender–Knuth involutions $\mathrm {BK}_i\colon \mathscr {L}\to \mathscr {L}$ indexed by elements of I. For arbitrary W and for each $i\in I$, we introduce an operator $\tau _i\colon W\to W$ (depending on $\mathscr {L}$) that we call a noninvertible Bender–Knuth toggle; this operator restricts to an involution on $\mathscr {L}$ that coincides with $\mathrm {BK}_i$ in type A. Given a Coxeter element $c=s_{i_n}\cdots s_{i_1}$, we consider the operator $\mathrm {Pro}_c=\tau _{i_n}\cdots \tau _{i_1}$. We say W is futuristic if for every nonempty finite convex set $\mathscr {L}$, every Coxeter element c and every $u\in W$, there exists an integer $K\geq 0$ such that $\mathrm {Pro}_c^K(u)\in \mathscr {L}$. We prove that finite Coxeter groups, right-angled Coxeter groups, rank-3 Coxeter groups, affine Coxeter groups of types $\widetilde A$ and $\widetilde C$, and Coxeter groups whose Coxeter graphs are complete are all futuristic. When W is finite, we actually prove that if $s_{i_N}\cdots s_{i_1}$ is a reduced expression for the long element of W, then $\tau _{i_N}\cdots \tau _{i_1}(W)=\mathscr {L}$; this allows us to determine the smallest integer $\mathrm {M}(c)$ such that $\mathrm {Pro}_c^{{\mathrm {M}}(c)}(W)=\mathscr {L}$ for all $\mathscr {L}$. We also exhibit infinitely many non-futuristic Coxeter groups, including all irreducible affine Coxeter groups that are not of type $\widetilde A$, $\widetilde C$, or $\widetilde G_2$.

Détail

DOI : 10.1017/fms.2024.159

Bibliographie

[1] Ayyer, A., Klee, S. and Schilling, A., ‘Combinatorial Markov chains on linear extensions’, J. Algebraic Combin. 39 (2014), 853–881. Google Scholar | DOI

[2] Björner, A. and Brenti, F., Combinatorics of Coxeter Groups (Graduate Texts in Mathematics) vol. 231 (Springer, 2005). Google Scholar

[3] Bourbaki, N., Lie Groups and Lie Algebras (Springer–Verlag, 2002). Google Scholar | DOI

[4] Brink, B. and Howlett, R. B., ‘A finiteness property and an automatic structure for Coxeter groups’, Math. Ann. 296 (1993). Google Scholar | DOI

[5] Casselman, B., ‘Computation in Coxeter groups II. Constructing minimal roots’, Represent. Theory 12 (2008). Google Scholar | DOI

[6] Chiang, J. H.-H., Hoang, A. T. N., Kendall, M., Lynch, R., Nguyen, S., Przybocki, B. and Xia, J., ‘Bender–Knuth involutions on linear extensions of posets’, Preprint, 2023, . Google Scholar | arXiv | DOI

[7] Defant, C., ‘Polyurethane toggles’, Electron. J. Combin. 27 (2020). Google Scholar | DOI

[8] Defant, C. and Kravitz, N., ‘Friends and strangers walking on graphs’, Comb. Theory 1 (2021). Google Scholar

[9] Defant, C. and Kravitz, N., ‘Promotion sorting’, Order 14 (2022). Google Scholar

[10] Develin, M., Macauley, M., and Reiner, V., ‘Toric partial orders’, Trans. Amer. Math. Soc. 368 (2016), 2263–2287. Google Scholar | DOI

[11] Dyer, M., ‘Reflection subgroups of Coxeter systems’, J. Algebra 135 (1990), 57–73. Google Scholar | DOI

[12] Dyer, M. J., ‘Embeddings of root systems II: Permutation root systems’, J. Algebra 321 (2009), 953–981. Google Scholar | DOI

[13] Edelman, P. and Greene, C., ‘Balanced tableaux’, Adv. Math. 63 (1987), 42–99. Google Scholar | DOI

[14] Fomin, S. and Zelevinsky, A., ‘Cluster algebras IV’, Compos. Math. 143 (2007), 112–164. Google Scholar | DOI

[15] Haiman, M. D., ‘Dual equivalence with applications, including a conjecture of Proctor’, Discrete Math. 99 (1992), 79–113. Google Scholar | DOI

[16] Hasselblatt, B. and Katok, A. (eds.), Handbook of Dynamical Systems vol. 1A (Elsevier, 2002). Google Scholar

[17] Hivert, F., Schilling, A. and Thiéry, N., ‘The biHecke monoid of a finite Coxeter group and its representations’, Algebra Number Theory 7 (2013), 595–671. Google Scholar | DOI

[18] Hodges, E., ‘On promotion and quasi-tangled labelings of posets’, Ann. Comb. 28 (2024), 529–554. Google Scholar | DOI

[19] Kenney, T., ‘Coxeter groups, Coxeter monoids and the Bruhat order’, J. Algebraic Combin. 39 (2014), 719–731. Google Scholar | DOI

[20] Kozlov, V. V. and Treshchëv, D. V., Billiards (Translations of Mathematical Monographs) vol. 89 (American Mathematical Society, 1991). Google Scholar

[21] Kuniba, A., Misra, K., Okado, M., Takagi, T. and Uchiyama, J., ‘Crystals for Demazure modules of classical affine Lie algebras’, J. Algebra 208 (1998), 185–215. Google Scholar | DOI

[22] Lam, T., ‘The shape of a random affine Weyl group element and random core partitions’, Ann. Probab. 43 (2015), 1643–1662. Google Scholar | DOI

[23] Malvenuto, C. and Reutenauer, C., ‘Evacuation of labelled graphs’, Discrete Math. 132 (1994), 137–143. Google Scholar | DOI

[24] Massow, M., ‘Linear extension graphs and linear extension diameter’, PhD thesis, Cuvillier Verlag Göttingen, 2010. Google Scholar

[25] Mcmullen, C., ‘Coxeter groups, Salem numbers and the Hilbert metric’, Publ. Math. Inst. Hautes Etudes Sci. 95 (2002), 151–183. Google Scholar | DOI

[26] Mühlherr, B. M., ‘Coxeter groups in Coxeter groups’, in Finite Geometry and Combinatorics (Deinze, 1992) (London Math. Soc. Lecture Note Ser.) vol. 191 (Cambridge Univ. Press, Cambridge), 277–287. Google Scholar

[27] Poznanović, S. and Stasikelis, K., ‘Properties of the promotion Markov chain on linear extensions’, J. Algebraic Combin. 47 (2018), 505–528. Google Scholar | DOI

[28] Reading, N., ‘Clusters, Coxeter-sortable elements and noncrossing partitions’, Trans. Amer. Math. Soc. 359 (2007), 5931–5958. Google Scholar | DOI

[29] Speyer, D., ‘Powers of Coxeter elements in infinite groups are reduced’, Proc. Amer. Math. Soc. 137 (2009), 1295–1302. Google Scholar | DOI

[30] Stanley, R. P., ‘Promotion and evacuation’, Electron. J. Combin. 16 (2009). Google Scholar | DOI

[31] Stembridge, J., ‘Folding by automorphisms’, Preprint, 2008, https://dept.math.lsa.umich.edu/~jrs/papers/folding.pdf. Google Scholar

[32] Striker, J. and Williams, N., ‘Promotion and rowmotion’, European J. Combin. 33 (2012) 1919–1942. Google Scholar | DOI

[33] Stump, C., Thomas, H. and Williams, N., ‘Cataland: Why the Fuß? To appear in Mem. Amer. Math. Soc. Google Scholar

[34] Tabachnikov, S., Geometry and Billiards (Student Mathematical Library) vol. 30 (American Mathematical Society, 2005). Google Scholar

[35] Tits, J., Buildings of Spherical Type and Finite BN-Pairs (Lecture Notes in Mathematics) vol. 386 (Springer-Verlag, Berlin-New York, 1974). Google Scholar

[36] Wieland, B., ‘A large dihedral symmetry of the set of alternating sign matrices’, Electron. J. Combin. 7 (2000). Google Scholar | DOI