×

Meeting covered elements in \(\nu\)-Tamari lattices. (English) Zbl 07461716

Summary: For each meet-semilattice \(M\), we define an operator \(\mathsf{Pop}_M : M \to M\) by \[ \mathsf{Pop}_M (x) = \bigwedge (\{ y \in M : y \lessdot x\} \cup \{ x\}). \] When \(M\) is the right weak order on a symmetric group, \( \mathsf{Pop}_M\) is the pop-stack-sorting map. We prove some general properties of these operators, including a theorem that describes how they interact with certain lattice congruences. We then specialize our attention to the dynamics of \(\mathsf{Pop}_{\operatorname{Tam} (\nu)}\), where \(\operatorname{Tam}(\nu)\) is the \(\nu\)-Tamari lattice. We determine the maximum size of a forward orbit of \(\mathsf{Pop}_{\operatorname{Tam} (\nu)}\). When \(\operatorname{Tam}(\nu)\) is the \(n^{\text{th}}\, m\)-Tamari lattice, this maximum forward orbit size is \(m+n-1\); in this case, we prove that the number of forward orbits of size \(m+n-1\) is \[ \frac{1}{n-1} \begin{pmatrix} (m+1) (n-2) + m-1 \\ n - 2 \end{pmatrix}. \] Motivated by the recent investigation of the pop-stack-sorting map, we define a lattice path \(\mu \in \operatorname{Tam}(\nu)\) to be \(t\)-\(\mathsf{Pop}\)-sortable if \(\mathsf{Pop}_{\operatorname{Tam} (\nu)}^t (\mu) = \nu\). We enumerate \(1\)-\(\mathsf{Pop}\)-sortable lattice paths in \(\operatorname{Tam}(\nu)\) for arbitrary \(\nu\). We also give a recursive method to generate \(2\)-\(\mathsf{Pop}\)-sortable lattice paths in \(\operatorname{Tam}(\nu)\) for arbitrary \(\nu\); this allows us to enumerate \(2\)-\(\mathsf{Pop}\)-sortable lattice paths in a large variety of \(\nu\)-Tamari lattices that includes the \(m\)-Tamari lattices.

MSC:

06A12 Semilattices
06B10 Lattice ideals, congruence relations
05A15 Exact enumeration problems, generating functions

Software:

OEIS

References:

[1] Albert, M.; Bouvel, M.; Féray, V., Two first-order logics of permutations, J. Comb. Theory, Ser. A, 171 (2020) · Zbl 1433.05004
[2] Albert, M.; Vatter, V., How many pop-stacks does it take to sort a permutation?, Comput. J. (2021)
[3] 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
[4] 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)
[5] Avis, D.; Newborn, M., On pop-stacks in series, Util. Math., 19, 129-140 (1981) · Zbl 0461.68060
[6] Banderier, C.; Bousquet-Mélou, M.; Denise, A.; Flajolet, P.; Gardy, D.; Gouyou-Beauchamps, D., Generating functions for generating trees, Discrete Math., 246, 29-55 (2002) · Zbl 0997.05007
[7] von Bell, M.; González D’León, R. S.; Mayorga Cetina, F. A.; Yip, M., A unifying framework for the ν-Tamari lattice and principal order ideals in Young’s lattice
[8] von Bell, M.; Yip, M., Schröder combinatorics and ν-associahedra, Eur. J. Comb., 98 (2021) · Zbl 1471.05009
[9] Bergeron, F.; Préville-Ratelle, L.-F., Higher trivariate diagonal harmonics via generalized Tamari posets, J. Comb., 3, 317-341 (2012) · Zbl 1291.05213
[10] Bentz, H.-J., Proof of the Bulgarian solitaire conjectures, Ars Comb., 23, 151-170 (1987) · Zbl 0643.05007
[11] Bitar, J.; Goles, E., Parallel chip firing games on graphs, Theor. Comput. Sci., 92, 291-300 (1992) · Zbl 0745.05054
[12] Björner, A.; Brenti, F., Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, vol. 231 (2005), Springer · Zbl 1110.05001
[13] Björner, A.; Wachs, M., Shellable nonpure complexes and posets. II, Trans. Am. Math. Soc., 349, 3945-3975 (1997) · Zbl 0886.05126
[14] Bóna, M., A survey of stack-sorting disciplines, Electron. J. Comb., 9 (2003) · Zbl 1028.05003
[15] Bousquet-Mélou, M.; Chapuy, G.; Préville-Ratelle, L.-F., The representation of the symmetric group on m-Tamari intervals, Adv. Math., 247, 309-342 (2013) · Zbl 1283.05268
[16] Bousquet-Mélou, M.; Fusy, E.; Préville-Ratelle, L.-F., The number of intervals in the m-Tamari lattices, Electron. J. Comb., 18 (2011) · Zbl 1262.05005
[17] Ceballos, C.; Padrol, A.; Sarmiento, C., Geometry of ν-Tamari lattices in types A and B, Trans. Am. Math. Soc., 371, 2575-2622 (2019) · Zbl 1402.05221
[18] Ceballos, C.; Padrol, A.; Sarmiento, C., The ν-Tamari lattice via ν-trees, ν-bracket vectors, and subword complexes, Electron. J. Comb., 27 (2020) · Zbl 1480.06003
[19] Châtel, G.; Pons, V., Counting smaller elements in the Tamari and m-Tamari lattices, J. Comb. Theory, Ser. A, 134, 58-97 (2015) · Zbl 1315.05143
[20] Chung, F. R.K.; Graham, R. L.; Hoggatt, V. E.; Kleiman, M., The number of Baxter permutations, J. Comb. Theory, Ser. A, 24, 382-394 (1978) · Zbl 0398.05003
[21] Claesson, A.; Guðmundsson, B.Á., Enumerating permutations sortable by k passes through a pop-stack, Adv. Appl. Math., 108, 79-96 (2019) · Zbl 1415.05012
[22] Claesson, A.; Guðmundsson, B.Á.; Pantone, J., Counting pop-stacked permutations in polynomial time · Zbl 1519.05013
[23] Defant, C., Counting 3-stack-sortable permutations, J. Comb. Theory, Ser. A, 172 (2020) · Zbl 1433.05005
[24] Defant, C., Pop-stack-sorting for Coxeter groups · Zbl 1498.05286
[25] Defant, C., Stack-sorting for Coxeter groups · Zbl 07621175
[26] Defant, C.; Elvey Price, A.; Guttmann, A. J., Asymptotics of 3-stack-sortable permutations, Electron. J. Comb., 28 (2021) · Zbl 1466.05002
[27] Defant, C.; Kravitz, N., Promotion sorting · Zbl 07701692
[28] Defant, C.; Zheng, K., Stack-sorting with consecutive-pattern-avoiding stacks, Adv. Appl. Math., 128 (2021) · Zbl 1467.05003
[29] Elder, M.; Goh, Y. K., k-pop stack sortable permutations and 2-avoidance, Electron. J. Comb., 28 (2021) · Zbl 1464.05005
[30] Etienne, G., Tableux de Young et Solitaire Bulgare, J. Comb. Theory, Ser. A, 58, 181-197 (1991) · Zbl 0747.05101
[31] Fang, W.; Préville-Ratelle, L.-F., The enumeration of generalized Tamari intervals, Eur. J. Comb., 61, 69-84 (2017) · Zbl 1352.05191
[32] Goulden, I.; West, J., Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations, J. Comb. Theory, Ser. A, 75, 220-242 (1996) · Zbl 0864.05044
[33] Grätzer, G., The Congruences of a Finite Lattice, a “Proof-by-Picture” Approach (2016), Birkhäuser · Zbl 1348.06001
[34] Griggs, J. R.; Ho, C.-C., The cycling of partitions and composition under repeated shifts, Adv. Appl. Math., 21, 205-227 (1998) · Zbl 0917.05008
[35] Hivert, F.; Novelli, J.-C.; Thibon, J.-Y., The algebra of binary search trees, Theor. Comput. Sci., 339, 129-165 (2005) · Zbl 1072.05052
[36] Igusa, K., Solution of the Bulgarian solitaire conjecture, Math. Mag., 58, 259-271 (1985) · Zbl 0607.90106
[37] Klivans, C., The Mathematics of Chip-Firing (2018), Taylor and Francis Group
[38] Latapy, M.; Phan, H. D., The lattice structure of chip firing games, Phys. D, 155, 69-82 (2000) · Zbl 0978.68109
[39] Mühle, H., The core label order of a congruence-uniform lattice, Algebra Univers., 80 (2019) · Zbl 1506.06003
[40] Mühle, H., Hochschild lattices and shuffle lattices · Zbl 07524340
[41] 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
[42] The on-line encyclopedia of integer sequences (2021), published electronically at · Zbl 1494.68308
[43] 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
[44] Pudwell, L.; Smith, R., Two-stack-sorting with pop stacks, Australas. J. Comb., 74, 179-195 (2019) · Zbl 1419.05010
[45] Reading, N., Cambrian lattices, Adv. Math., 205, 313-353 (2006) · Zbl 1106.20033
[46] Reading, N., Lattice theory of the poset of regions, (Grätzer, G.; Wehrung, F., Lattice Theory: Special Topics and Applications (2016), Birkhäuser: Birkhäuser Cham) · Zbl 1404.06004
[47] Reading, N., Noncrossing partitions and the shard intersection order, J. Algebraic Comb., 33, 483-530 (2011) · Zbl 1290.05163
[48] Reading, N., Sortable elements and Cambrian lattices, Algebra Univers., 56, 411-437 (2007) · Zbl 1184.20038
[49] Sapounakis, A.; Tasoulas, I.; Tsikouras, P., On the dominance partial ordering on Dyck paths, J. Integer Seq., 9 (2006) · Zbl 1104.05003
[50] Stanley, R. P., Enumerative Combinatorics, vol. 1 (2012), Cambridge University Press · Zbl 1247.05003
[51] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press · Zbl 0928.05001
[52] Tamari, D., The algebra of bracketings and their enumeration, Nieuw Arch. Wiskd., 10, 131-146 (1962) · Zbl 0109.24502
[53] Ungar, P., 2N noncollinear points determine at least 2N directions, J. Comb. Theory, Ser. A, 33, 343-347 (1982) · Zbl 0496.05001
[54] West, J., Generating trees and forbidden subsequences, Discrete Math., 157, 363-374 (1996) · Zbl 0877.05002
[55] West, J., Generating trees and the Catalan and Schröder numbers, Discrete Math., 146, 247-262 (1995) · Zbl 0841.05002
[56] West, J., Permutations with restricted subsequences and stack-sortable permutations (1990), MIT, Ph.D. Thesis
[57] Zeilberger, D., A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is \(2(3 n)! /((n + 1)!(2 n + 1)!)\), Discrete Math., 102, 85-93 (1992) · Zbl 0754.05006
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.