The pop-stack-sorting operator on Tamari lattices. (English) Zbl 07540628
Summary: Motivated by the pop-stack-sorting map on the symmetric groups, C. Defant [Adv. Appl. Math. 134, Article ID 102303, 34 p. (2022; Zbl 07461716)] defined an operator \(\mathsf{Pop}_M : M \to M\) for each complete meet-semilattice \(M\) by
\[
\mathsf{Pop}_M(x) = \land(\{y \in M : y \lessdot x\} \cup \{x \}).
\] This paper concerns the dynamics of \(\mathsf{Pop}_{\operatorname{Tam}_n} \), where \(\operatorname{Tam}_n\) is the \(n\)-th Tamari lattice.
We say an element \(x \in \operatorname{Tam}_n\) is \(t\)-\(\mathsf{Pop}\)-sortable if \(\mathsf{Pop}_M^t(x)\) is the minimal element and we let \(h_t(n)\) denote the number of \(t-\mathsf{Pop} \)-sortable elements in \(\operatorname{Tam}_n\). We find an explicit formula for the generating function \(\sum_{n \geq 1} h_t(n) z^n\) and verify Defant’s conjecture that it is rational. We furthermore prove that the size of the image of \(\mathsf{Pop}_{\operatorname{Tam}_n}\) is the Motzkin number \(M_n\), settling a conjecture of Defant and Williams.
We say an element \(x \in \operatorname{Tam}_n\) is \(t\)-\(\mathsf{Pop}\)-sortable if \(\mathsf{Pop}_M^t(x)\) is the minimal element and we let \(h_t(n)\) denote the number of \(t-\mathsf{Pop} \)-sortable elements in \(\operatorname{Tam}_n\). We find an explicit formula for the generating function \(\sum_{n \geq 1} h_t(n) z^n\) and verify Defant’s conjecture that it is rational. We furthermore prove that the size of the image of \(\mathsf{Pop}_{\operatorname{Tam}_n}\) is the Motzkin number \(M_n\), settling a conjecture of Defant and Williams.
MSC:
| 06A12 | Semilattices |
| 06B10 | Lattice ideals, congruence relations |
| 05A15 | Exact enumeration problems, generating functions |
| 05A05 | Permutations, words, matrices |
| 68R10 | Graph theory (including graph drawing) in computer science |
Citations:
Zbl 07461716Software:
OEISReferences:
| [1] | Asinowski, A.; Banderier, C.; Billey, S.; Hackl, B.; Linusson, S., Pop-stack sorting and its image: permutations with overlapping runs, Acta Math. Univ. Comen., 88, 395-402 (2019) |
| [2] | Asinowski, A.; Banderier, C.; Hackl, B., Flip-sort and combinatorial aspects of pop-stack sorting, Discrete Math. Theor. Comput. Sci., 22 (2021) · Zbl 1532.68013 |
| [3] | Avis, D. M.; Newborn, M., On pop-stacks in series, Util. Math., 19, 129-140 (1981) · Zbl 0461.68060 |
| [4] | Bergeron, F.; Préville-Ratelle, L. F., Higher trivariate diagonal harmonics via generalized Tamari posets, J. Comb., 3, 317-341 (2012) · Zbl 1291.05213 |
| [5] | Björner, A.; Wachs, M., Shellable nonpure complexes and posets. II, Trans. Am. Math. Soc., 349, 3945-3975 (1997) · Zbl 0886.05126 |
| [6] | Ceballos, C.; Padrol, A.; Sarmiento, C., The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes, Electron. J. Comb., 27 (2020) · Zbl 1480.06003 |
| [7] | Claesson, A.; Guðmundsson, B. A., Enumerating permutations sortable by k passes through a pop-stack, Adv. Appl. Math., 108, 79-96 (2019) · Zbl 1415.05012 |
| [8] | Defant, C., Meeting covered elements in ν-Tamari lattices, Adv. Appl. Math., 134 (2022) · Zbl 07461716 |
| [9] | Defant, C., Pop-stack-sorting for Coxeter groups · Zbl 1498.05286 |
| [10] | Defant, C.; Hopkins, S., Symmetry of Narayana numbers and rowvacuation of root posets, Forum Math. Sigma, 9 (2021) · Zbl 1471.05119 |
| [11] | Defant, C.; Williams, N., Semidistrim lattices · Zbl 07692107 |
| [12] | Dukes, M., Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson’s sorting conjecture, Electron. J. Comb., 21, 2, Article P2.2 pp. (2014) · Zbl 1300.05007 |
| [13] | Elder, M.; Goh, Y. K., k-pop stack sortable permutations and 2-avoidance, Electron. J. Comb., 28 (2021) · Zbl 1464.05005 |
| [14] | Hivert, F.; Novelli, J. C.; Thibon, J. Y., The algebra of binary search trees, Theor. Comput. Sci., 339, 129-165 (2005) · Zbl 1072.05052 |
| [15] | Knuth, D., The Art of Computer Programming, vol. 1: Fundamental Algorithms (1968), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903 |
| [16] | Müller-Hoissen, F.; Pallo, J. M.; Stasheff, J., Associahedra, Tamari Lattices, and Related Structures, Progress in Mathematics, vol. 299 (2012), Birkhäuser · Zbl 1253.00013 |
| [17] | Petersen, T. K., Eulerian Numbers (2015), Birkhäuser, Section 4.3 · Zbl 1337.05001 |
| [18] | Préville-Ratelle, L. F.; Viennot, X., An extension of Tamari lattices, Trans. Am. Math. Soc., 369, 5219-5239 (2017), (assigned the incorrect title “The enumeration of generalized Tamari intervals” by the journal) · Zbl 1433.05323 |
| [19] | Pudwell, L.; Smith, R., Two-stack-sorting with pop stacks, Australas. J. Comb., 74, 179-195 (2019) · Zbl 1419.05010 |
| [20] | Reading, N., Cambrian lattices, Adv. Math., 205, 313-353 (2006) · Zbl 1106.20033 |
| [21] | Sloane, N. J.A., The Online Encyclopedia of Integer Sequences (2021), published electronically at |
| [22] | Tamari, D., The algebra of bracketings and their enumeration, Nieuw Arch. Wiskd. (3), 10, 131-146 (1962) · Zbl 0109.24502 |
| [23] | West, J., Permutations with restricted subsequences and stack-sortable permutations (1990), MIT, Ph.D. thesis |
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.
