Coxeter Pop-Tsack Torsing

Defant, Colin; Williams, Nathan

Algebraic Combinatorics, Tome 5 (2022) no. 3, pp. 559-581.

Given a finite irreducible Coxeter group $W$ with a fixed Coxeter element $c$, we define the Coxeter pop-tsack torsing operator ${\mathsf{Pop}}_T:W\to W$ by ${\mathsf{Pop}}_T\left(w\right)=w·{\pi }_T{\left(w\right)}^{-1}$, where ${\pi }_T\left(w\right)$ is the join in the noncrossing partition lattice $\mathrm{NC}(w,c)$ of the set of reflections lying weakly below $w$ in the absolute order. This definition serves as a “Bessis dual” version of the first author’s notion of a Coxeter pop-stack sorting operator, which, in turn, generalizes the pop-stack sorting map on symmetric groups. We show that if $W$ is coincidental or of type $D$, then the identity element of $W$ is the unique periodic point of ${\mathsf{Pop}}_T$ and the maximum size of a forward orbit of ${\mathsf{Pop}}_T$ is the Coxeter number $h$ of $W$. In each of these types, we obtain a natural lift from $W$ to the dual braid monoid of $W$. We also prove that $W$ is coincidental if and only if it has a unique forward orbit of size $h$. For arbitrary $W$, we show that the forward orbit of $c^{-1}$ under ${\mathsf{Pop}}_T$ has size $h$ and is isolated in the sense that none of the non-identity elements of the orbit have preimages lying outside of the orbit.

Classification : 05E16, 05A05, 05A18
Mots clés : Coxeter group, pop-stack sorting, noncrossing partition, dual braid monoid

[1] Albert, Michael; Vatter, Vincent How many pop-stacks does it take to sort a permutation? (2021) (https://arxiv.org/abs/2012.05275)

[2] Ardila, Federico; Rincón, Felipe; Williams, Lauren Positroids and non-crossing partitions, Trans. Amer. Math. Soc., Volume 368 (2016) no. 1, pp. 337-363 | DOI | MR | Zbl

[3] Armstrong, Drew Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc., 202, American Mathematical Society, Providence, RI, 2009 no. 949, x+159 pages | DOI | MR | Zbl

[4] Asinowski, Andrei; Banderier, Cyril; Billey, Sara; Hackl, Benjamin; Linusson, Svante Pop-stack sorting and its image: permutations with overlapping runs, Acta Math. Univ. Comenian. (N.S.), Volume 88 (2019) no. 3, pp. 395-402 | MR

[5] Asinowski, Andrei; Banderier, Cyril; Hackl, Benjamin Flip-sort and combinatorial aspects of pop-stack sorting, Discrete Math. Theor. Comput. Sci., Volume 22 (2021) no. 2, 4, 39 pages | MR | Zbl

[6] Athanasiadis, Christos A.; Reiner, Victor Noncrossing partitions for the group $D_n$, SIAM J. Discrete Math., Volume 18 (2004) no. 2, pp. 397-417 | DOI | MR | Zbl

[7] Bessis, David The dual braid monoid, Ann. Sci. École Norm. Sup. (4), Volume 36 (2003) no. 5, pp. 647-683 | DOI | Numdam | MR | Zbl

[8] Bessis, David Finite complex reflection arrangements are $K(\pi ,1)$, Ann. of Math. (2), Volume 181 (2015) no. 3, pp. 809-904 | DOI | MR | Zbl

[9] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv+363 pages | DOI | MR | Zbl

[10] Blitvić, Natasha Stabilized-interval-free permutations and chord-connected permutations, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (Discrete Math. Theor. Comput. Sci. Proc., AT), Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2014), pp. 801-813 | MR | Zbl

[11] Brady, Thomas; Watt, Colum $K(\pi ,1)$’s for Artin groups of finite type, Geom. Dedicata, Volume 94 (2002), pp. 225-250 | DOI | MR | Zbl

[12] Brady, Thomas; Watt, Colum Non-crossing partition lattices in finite real reflection groups, Trans. Amer. Math. Soc., Volume 360 (2008) no. 4, pp. 1983-2005 | DOI | MR | Zbl

[13] Brieskorn, Egbert Die Fundamentalgruppe des Raumes der regulären Orbits einer endlichen komplexen Spiegelungsgruppe, Invent. Math., Volume 12 (1971), pp. 57-61 | DOI | MR | Zbl

[14] Brieskorn, Egbert; Saito, Kyoji Artin-Gruppen und Coxeter-Gruppen, Invent. Math., Volume 17 (1972), pp. 245-271 | DOI | MR | Zbl

[15] Callan, David Counting stabilized-interval-free permutations, J. Integer Seq., Volume 7 (2004) no. 1, 04.1.8, 7 pages | MR | Zbl

[16] Carter, Roger W. Conjugacy classes in the Weyl group, Compositio Math., Volume 25 (1972), pp. 1-59 | Numdam | MR | Zbl

[17] Claesson, Anders; Guðmundsson, Bjarki Á. Enumerating permutations sortable by $k$ passes through a pop-stack, Adv. in Appl. Math., Volume 108 (2019), pp. 79-96 | DOI | MR | Zbl

[18] Claesson, Anders; Guðmundsson, Bjarki Á.; Pantone, Jay Counting pop-stacked permutations in polynomial time (2019) (https://arxiv.org/abs/1908.08910)

[19] Defant, Colin Pop-Stack-Sorting for Coxeter Groups (2021) (https://arxiv.org/abs/2104.02675)

[20] Elder, Murray; Goh, Yoong Kuan $k$-pop stack sortable permutations and 2-avoidance, Electron. J. Combin., Volume 28 (2021) no. 1, 1.54, 15 pages | DOI | MR | Zbl

[21] Geck, Meinolf; Hiss, Gerhard; Lübeck, Frank; Malle, Gunter; Pfeiffer, Götz CHEVIE – A system for computing and processing generic character tables, Appl. Algebra Eng. Commun. Comput., Volume 7 (1996) no. 3, pp. 175-210 | DOI | MR | Zbl

[22] Pudwell, Lara; Smith, Rebecca Two-stack-sorting with pop stacks, Australas. J. Combin., Volume 74 (2019), pp. 179-195 | MR | Zbl

[23] Reading, Nathan Noncrossing partitions, clusters and the Coxeter plane, Sém. Lothar. Combin., Volume 63 (2010), B63b, 32 pages | MR | Zbl

[24] Reiner, Victor; Ripoll, Vivien; Stump, Christian On non-conjugate Coxeter elements in well-generated reflection groups, Math. Z., Volume 285 (2017) no. 3-4, pp. 1041-1062 | DOI | MR | Zbl

[25] Schönert, Martin et al. GAP – Groups, Algorithms, and Programming – version 3 release 4 patchlevel 4 (1997)

[26] Springer, Tonny A. Regular elements of finite reflection groups, Invent. Math., Volume 25 (1974), pp. 159-198 | DOI | MR | Zbl

[27] SageMath, the Sage Mathematics Software System (Version 9.2) (2021) (https://www.sagemath.org)

[28] Ungar, Peter $2N$ noncollinear points determine at least $2N$ directions, J. Combin. Theory Ser. A, Volume 33 (1982) no. 3, pp. 343-347 | DOI | MR | Zbl