×

Pop-stack-sorting for Coxeter groups. (English) Zbl 1498.05286

Summary: Let \(W\) be an irreducible Coxeter group. We define the Coxeter pop-stack-sorting operator \(\mathsf{Pop}:W\to W\) to be the map that fixes the identity element and sends each nonidentity element \(w\) to the meet of the elements covered by \(w\) in the right weak order. When \(W\) is the symmetric group \(S_n\), \(\mathsf{Pop}\) coincides with the pop-stack-sorting map. Generalizing a theorem about the pop-stack-sorting map due to Ungar, we prove that \[\sup\limits_{w\in W}\left|O_{\mathsf{Pop}}(w)\right|=h,\] where \(h\) is the Coxeter number of \(W\) (with \(h=\infty\) if \(W\) is infinite) and \(O_f(w)\) denotes the forward orbit of \(w\) under a map \(f\). When \(W\) is finite, this result is equivalent to the statement that the maximum number of terms appearing in the Brieskorn normal form of an element of \(W\) is \(h-1\). More generally, we define a map \(f:W\to W\) to be compulsive if for every \(w\in W, f(w)\) is less than or equal to \(\mathsf{Pop}(w)\) in the right weak order.
We prove that if \(f\) is compulsive, then \(\sup\limits_{w\in W}|O_f(w)|\leq h\). This result is new even for symmetric groups. We prove that \(2\)-pop-stack-sortable elements in type \(B\) are in bijection with \(2\)-pop-stack-sortable permutations in type \(A\), which were enumerated by L. Pudwell and R. Smith [Australas. J. Comb. 74, Part 1, 179–195 (2019; Zbl 1419.05010)]. A. Claesson and B. Á. Guðmundsson [Adv. Appl. Math. 108, 79–96 (2019; Zbl 1415.05012)] proved that for each fixed nonnegative integer \(t\), the generating function that counts \(t\)-pop-stack-sortable permutations in type \(A\) is rational; we establish analogous results in types \(B\) and \(\widetilde{A}\).

MSC:

05E16 Combinatorial aspects of groups and algebras
37E15 Combinatorial dynamics (types of periodic orbits)
05A05 Permutations, words, matrices
20F55 Reflection and Coxeter groups (group-theoretic aspects)

References:

[1] R. M. Adin, V. Reiner, and Y. Roichman, On cyclic descents for tableaux. Int. Math. Res. Not. IMRN, 2020 (2020), 10231-10276. · Zbl 1459.05339
[2] M. H. Albert, M. D. Atkinson, M. Bouvel, A. Claesson, and M. Dukes, On the inverse image of pattern classes under bubble sort. J. Comb., 2 (2011), 231-243. · Zbl 1247.05005
[3] M. Albert, M. Bouvel, and V. Féray, Two first-order logics of permutations. J. Combin. Theory Ser. A, 171 (2020). · Zbl 1433.05004
[4] M. Albert and V. Vatter, How many pop-stacks does it take to sort a permutation? Comput. J., (2021).
[5] A. Asinowski, C. Banderier, and B. Hackl, Flip-sort and combinatorial aspects of pop-stack sorting. Discrete Math. Theor. Comput. Sci., 22 (2021). · Zbl 1532.68013
[6] A. Asinowski, C. Banderier, S. Billey, B. Hackl, and S. Linusson, Pop-stack sorting and its image: permutations with overlapping runs. Acta. Math. Univ. Comenian., 88 (2019), 395-402.
[7] D. Avis and M. Newborn. On pop-stacks in series. Util. Math., 19 (1981), 129-140. · Zbl 0461.68060
[8] A. Björner, Orderings of Coxeter groups. In Combinatorics and algebra (Boulder, Colo., 1983), vol. 34 of Contemp. Math., American Mathematical Society, 1984. · Zbl 0594.20029
[9] A. Björner and F. Brenti, Combinatorics of Coxeter groups, vol. 231 of Graduate Texts in Mathematics. Springer, 2005. · Zbl 1110.05001
[10] M. Bóna, A survey of stack-sorting disciplines. Electron. J. Combin., 9 (2003). · Zbl 1028.05003
[11] M. Bóna, Symmetry and unimodality in t-stack sortable permutations. J. Combin. Theory Ser. A, 98.1 (2002), 201-209. · Zbl 1009.05003
[12] N. Bourbaki, Lie groups and Lie algebras. Springer-Verlag, 2002. · Zbl 0983.17001
[13] P. Brändén, On linear transformations preserving the Pólya frequency property. Trans. Amer. Math. Soc., 358 (2006), 3697-3716. · Zbl 1086.05007
[14] E. Brieskorn, Die fundamentalgruppe des raumes der regulären orbits einer endlichen kom-plexen spiegelungsgruppe. Invent. Math., 12 (1971), 57-61. · Zbl 0204.56502
[15] E. Brieskorn and K. Saito, Artin-gruppen und Coxeter-gruppen. Invent. Math., 17 (1972), 245-271. · Zbl 0243.20037
[16] G. Cerbai, A. Claesson, and L. Ferrari, Stack sorting with restricted stacks. J. Combin. Theory Ser. A, 173 (2020). · Zbl 1435.05004
[17] F. Chung, A. Claesson, M. Dukes, and R. Graham, Descent polynomials for permutations with bounded drop size. European J. Combin., 31 (2010), 1853-1867. · Zbl 1227.05011
[18] L. Cioni and L. Ferrari, Preimages under the Queuesort algorithm. Discrete Math., 344 (2021). · Zbl 1472.05005
[19] A. Claesson and B. Á. Guðmundsson, Enumerating permutations sortable by k passes through a pop-stack. Adv. Appl. Math., 108 (2019), 79-96. · Zbl 1415.05012
[20] A. Claesson, B. Á. Guðmundsson, and J. Pantone, Counting pop-stacked permutations in polynomial time. arXiv:1908.08910. · Zbl 1519.05013
[21] C. Defant, Counting 3-stack-sortable permutations. J. Combin. Theory Ser. A, 172 (2020). · Zbl 1433.05005
[22] C. Defant, Fertility monotonicity and average complexity of the stack-sorting map. Euro-pean J. Combin., 93 (2021). · Zbl 1478.05004
[23] C. Defant, Meeting covered elements in ν-Tamari lattices. Adv. Appl. Math., 134 (2022). · Zbl 07461716
[24] C. Defant, Polyurethane toggles. Electron. J. Combin., 27 (2020). · Zbl 1441.05007
[25] C. Defant, Stack-sorting for Coxeter groups. Comb. Theory, 2 (2022). · Zbl 07621175
[26] C. Defant, Troupes, cumulants, and stack-sorting. Adv. Math., 399 (2022). · Zbl 1515.05091
[27] C. Defant, A. Elvey Price, and A. J. Guttmann, Asymptotics of 3-stack-sortable permuta-tions. Electron. J. Combin., 28 (2021). · Zbl 1466.05002
[28] M. Dukes, Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable per-mutations, and Steingrímsson’s sorting conjecture. Electron. J. Combin., 21 (2014). · Zbl 1300.05007
[29] M. Elder and Y. K. Goh, k-pop stack sortable permutations and 2-avoidance. Electron. J. Combin., 28 (2021). · Zbl 1464.05005
[30] P. Flajolet and R. Sedgewick, Analytic combinatorics. Cambridge University Press, 2009. · Zbl 1165.05001
[31] M. Geck and G. Pfeiffer, Characters of finite Coxeter groups and Iwahori-Hecke alge-bras, vol. 21 of London Mathematical Society Monographs, New Series, The Clarendon Press/Oxford University Press, 2000. · Zbl 0996.20004
[32] S. Giraudo. Algebraic and combinatorial structures on pairs of twin binary trees. J. Algebra, 360 (2012), 115-157. · Zbl 1253.05146
[33] J. E. Goodman and R. Pollack, A combinatorial perspective on some problems in geometry. Congr. Numer., 32 (1981), 383-394. · Zbl 0495.05012
[34] F. Hivert, J.-C. Novelli, and J.-Y. Thibon, The algebra of binary search trees. Theoret. Com-put. Sci., 339 (2005), 129-165. · Zbl 1072.05052
[35] H. P. Hoang and T. Mütze, Combinatorial generation via permutation languages. II. Lattice congruences. To appear in Israel J. Math., (2021). · Zbl 1479.05182
[36] J. E. Humphreys, Reflection groups and Coxeter groups. Cambridge University Press, 1990. · Zbl 0725.20028
[37] D. E. Knuth, The Art of Computer Programming, volume 3, Sorting and Searching. Addison-Wesley, Reading, 2nd ed., 1998. · Zbl 0895.65001
[38] S. Law and N. Reading. The Hopf algebra of diagonal rectangulations. J. Combin. Theory Ser. A, 119 (2012), 788-824. · Zbl 1246.16027
[39] P. Linz, An introduction to formal languages and automata. Jones & Bartlett Learning, 5th ed., 2012. · Zbl 1244.68001
[40] H. Magnusson, Sorting operators and their preimages, M.Sc. Thesis, Reykjavík University, 2013.
[41] H. Mühle, The core label order of a congruence-uniform lattice. Algebra Universalis, 80 (2019). · Zbl 1506.06003
[42] H. Mühle, Hochschild lattices and shuffle lattices. European J. Combin., 103 (2022). · Zbl 07524340
[43] V. Pilaud. Brick polytopes, lattice quotients, and Hopf algebras. J. Combin. Theory Ser. A, 155 (2018), 418-457. · Zbl 1377.05024
[44] V. Pilaud and V. Pons, Permutrees. Algebr. Comb., 1 (2018), 173-224. · Zbl 1388.05039
[45] L. Pudwell and R. Smith, Two-stack-sorting with pop stacks. Australas. J. Combin., 74 (2019), 179-195. · Zbl 1419.05010
[46] N. Reading, Cambrian lattices. Adv. Math., 205 (2006), 313-353. · Zbl 1106.20033
[47] N. Reading. Finite Coxeter groups and the weak order. In Lattice theory: special topics and applications. vol. 2, pages 489-561. Birkhäuser/Springer, 2016. · Zbl 1388.20056
[48] N. Reading, Lattice congruences, fans and Hopf algebras. J. Combin. Theory Ser. A, 110 (2005), 237-273. · Zbl 1133.20027
[49] N. Reading and D. Speyer, Cambrian frameworks for cluster algebras of affine type. Trans. Amer. Math. Soc., 370 (2018), 1429-1468. · Zbl 1423.13131
[50] N. Reading and D. Speyer, Sortable elements in infinite Coxeter groups. Trans. Amer. Math. Soc., 363 (2011), 699-761. · Zbl 1231.20036
[51] J. R. Stembridge, On the fully commutative elements of Coxeter groups. J. Algebraic Com-bin., 5 (1996), 353-385. · Zbl 0864.20025
[52] P. Ungar, 2N noncollinear points determine at least 2N directions. J. Combin. Theory Ser. A, 33 (1982), 343-347. · Zbl 0496.05001
[53] J. West, Permutations with restricted subsequences and stack-sortable permutations, Ph.D. Thesis, MIT, 1990.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.