×

Semidistrim lattices. (English) Zbl 07692107

Summary: We introduce semidistrim lattices, a simultaneous generalization of semidistributive and trim lattices that preserves many of their common properties. We prove that the elements of a semidistrim lattice correspond to the independent sets in an associated graph called the Galois graph, that products and intervals of semidistrim lattices are semidistrim, and that the order complex of a semidistrim lattice is either contractible or homotopy equivalent to a sphere. Semidistrim lattices have a natural rowmotion operator, which simultaneously generalizes Barnard’s \(\overline{\kappa}\) map on semidistributive lattices as well as Thomas and the second author’s rowmotion on trim lattices. Every lattice has an associated pop-stack sorting operator that sends an element \(x\) to the meet of the elements covered by \(x\). For semidistrim lattices, we are able to derive several intimate connections between rowmotion and pop-stack sorting, one of which involves independent dominating sets of the Galois graph.

MSC:

06-XX Order, lattices, ordered algebraic structures

Online Encyclopedia of Integer Sequences:

Number of permutations of [n] with overlapping adjacent runs.

References:

[1] K. Adaricheva, J. Hyndman, S. Lempp, and J. B. Nation. “Interval Dismantlable Lattices”. Order35(2018), pp. 133-137. · Zbl 1405.06001
[2] 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), pp. 395-402.
[3] E. Barnard. “The canonical join complex”.Electron. J. Combin.26(2019). · Zbl 1516.06008
[4] A. Björner. “Topological methods in combinatorics”.Handbook of Combinatorics. Vol. 2. Amsterdam: Elsevier, 1995. · Zbl 0851.52016
[5] A. Claesson and B. A. Guðmundsson. “Enumerating permutations sortable bykpasses through a pop-stack”.Adv. Appl. Math.108(2019), pp. 79-96. · Zbl 1415.05012
[6] C. Defant. “Pop-stack-sorting for Coxeter groups”. 2021.arXiv:2104.02675. · Zbl 1498.05286
[7] C. Defant. “Meeting covered elements inν-Tamari lattices”.Adv. Appl. Math.134(2022). · Zbl 07461716
[8] C. Defant and N. Williams. “Semidistrim lattices”. 2021.arXiv:2111.08122.
[9] L. Hong. “The Pop-stack-sorting operator on Tamari lattices”. 2022.arXiv:2201.10030. · Zbl 07540628
[10] G. Markowsky. “Primes, irreducibles and extremal lattices”.Order9(1992), pp. 265-290. · Zbl 0778.06007
[11] T. McConville. “Crosscut-simplicial lattices”.Order34(2017), pp. 465-477. · Zbl 1432.06003
[12] N. Reading, D. E Speyer, and H. Thomas. “The fundamental theorem of finite semidistributive lattices”.Selecta Math. (N.S.)27(2021). · Zbl 1485.06003
[13] A. Sapounakis, I. Tasoulas, and P. Tsikouras. “On the dominance partial ordering on Dyck paths”.J. Integer Seq.9(2006). · Zbl 1104.05003
[14] J. Striker. “Rowmotion and generalized toggle groups”.Discrete Math. Theor. Comput. Sci. 20(2018). · Zbl 1401.05315
[15] H. Thomas. “An analogue of distributivity for ungraded lattices”.Order23(2006), pp. 249- 269. · Zbl 1134.06003
[16] H. Thomas and N. Williams. “Independence posets”.J. Combin.10(2019), pp. 545-578. · Zbl 1411.05104
[17] H. Thomas and N. Williams. “Rowmotion in slow motion”.Proc. Lond. Math. Soc.119 (2019), pp. 1149-1178 · Zbl 1459.06010
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.