Reducing the lengths of slim planar semimodular lattices without changing their congruence lattices
Gábor Czédli
Received January 10, 2023. Published online February 27, 2024.
Abstract: Following G. Grätzer and E. Knapp (2007), a slim planar semimodular lattice, SPS lattice for short, is a finite planar semimodular lattice having no $M_3$ as a sublattice. An SPS lattice is a slim rectangular lattice if it has exactly two doubly irreducible elements and these two elements are complements of each other. A finite poset $P$ is said to be JConSPS-representable if there is an SPS lattice $L$ such that $P$ is isomorphic to the poset ${\rm J}({\rm Con} L)$ of join-irreducible congruences of $L$. We prove that if $1<n\in\mathbb N$ and $P$ is an $n$-element JConSPS-representable poset, then there exists a slim rectangular lattice $L$ such that ${\rm J}({\rm Con} L)\cong P$, the length of $L$ is at most $2n^2$, and $|L|\leq4n^4$. This offers an algorithm to decide whether a finite poset $P$ is JConSPS-representable (or a finite distributive lattice is "ConSPS-representable"). This algorithm is slow as G. Czédli, T. Dékány, G. Gyenizse, and J. Kulin proved in 2016 that there are asymptotically $\frac12(k-2)! {\rm e}^2$ slim rectangular lattices of a given length $k$, where ${\rm e}$ is the famous constant $\approx2.71828$. The known properties and constructions of JConSPS-representable posets can accelerate the algorithm; we present a new construction.
References: [1] K. Adaricheva, G. Czédli: Note on the description of join-distributive lattices by permutations. Algebra Univers. 72 (2014), 155-162. DOI 10.1007/s00012-014-0295-y | MR 3257652 | Zbl 1301.06024
[2] D. Ahmed, E. K. Horváth: Yet two additional large numbers of subuniverses of finite lattices. Discuss. Math., Gen. Algebra Appl. 39 (2019), 251-261. DOI 10.7151/dmgaa.1309 | MR 4020360 | Zbl 1463.06014
[3] G. Czédli: Representing homomorphisms of distributive lattices as restrictions of congruences of rectangular lattices. Algebra Univers. 67 (2012), 313-345. DOI 10.1007/s00012-012-0190-3 | MR 2970728 | Zbl 1269.06004
[4] G. Czédli: Coordinatization of finite join-distributive lattices. Algebra Univers. 71 (2014), 385-404. DOI 10.1007/s00012-014-0282-3 | MR 3207613 | Zbl 1302.06011
[5] G. Czédli: Patch extensions and trajectory colorings of slim rectangular lattices. Algebra Univers. 72 (2014), 125-154. DOI 10.1007/s00012-014-0294-z | MR 3257651 | Zbl 1312.06005
[6] G. Czédli: Diagrams and rectangular extensions of planar semimodular lattices. Algebra Univers. 77 (2017), 443-498. DOI 10.1007/s00012-017-0437-0 | MR 3662480 | Zbl 1380.06006
[7] G. Czédli: Lamps in slim rectangular planar semimodular lattices. Acta Sci. Math. 87 (2021), 381-413. DOI 10.14232/actasm-021-865-y | MR 4333915 | Zbl 1499.06025
[8] G. Czédli: A property of meets in slim semimodular lattices and its application to retracts. Acta Sci. Math. 88 (2022), 595-610. DOI 10.1007/s44146-022-00040-z | MR 4536393 | Zbl 7672122
[9] G. Czédli: Cyclic congruences of slim semimodular lattices and non-finite axiomatizability of some finite structures. Arch. Math., Brno 58 (2022), 15-33. DOI 10.5817/AM2022-1-15 | MR 4412964 | Zbl 7511505
[10] G. Czédli: $C_1$-diagrams of slim rectangular semimodular lattices permit quotient diagrams. To appear in Acta Sci. Math. DOI 10.1007/s44146-023-00101-x
[11] G. Czédli: Infinitely many new properties of the congruence lattices of slim semimodular lattices. Acta. Sci. Math. 89 (2023), 319-337. DOI 10.1007/s44146-023-00069-8 | MR 4671397
[12] G. Czédli, T. Dékány, G. Gyenizse, J. Kulin: The number of slim rectangular lattices. Algebra Univers. 75 (2016), 33-50. DOI 10.1007/s00012-015-0363-y | MR 3519569 | Zbl 1345.06005
[13] G. Czédli, G. Grätzer: A new property of congruence lattices of slim, planar, semimodular lattices. Categ. Gen. Algebr. Struct. Appl. 16 (2022), 1-28. MR 4399396 | Zbl 1497.06008
[14] G. Czédli, Á. Kurusa: A convex combinatorial property of compact sets in the plane and its roots in lattice theory. Categ. Gen. Algebr. Struct. Appl. 11 (2019), 57-92. DOI 10.29252/CGASA.11.1.57 | MR 3988338 | Zbl 1428.52002
[15] G. Czédli, E. T. Schmidt: Frankl's conjecture for large semimodular and planar semimodular lattices. Acta Univ. Palacki. Olomuc., Fac. Rerum Nat., Math. 47 (2008), 47-53. MR 2482716 | Zbl 1187.05002
[16] G. Czédli, E. T. Schmidt: The Jordan-Hölder theorem with uniqueness for groups and semimodular lattices. Algebra Univers. 66 (2011), 69-79. DOI 10.1007/s00012-011-0144-1 | MR 2844921 | Zbl 1233.06006
[17] G. Czédli, E. T. Schmidt: Slim semimodular lattices. I. A visual approach. Order 29 (2012), 481-497. DOI 10.1007/s11083-011-9215-3 | MR 2979644 | Zbl 1257.06005
[18] G. Grätzer: Congruences of fork extensions of slim, planar, semimodular lattices. Algebra Univers. 76 (2016), 139-154. DOI 10.1007/s00012-016-0394-z | MR 3551218 | Zbl 1370.06004
[19] G. Grätzer: Notes on planar semimodular lattices. VIII. Congruence lattices of SPS lattices. Algebra Univers. 81 (2020), Article ID 15, 3 pages. DOI 10.1007/s00012-020-0641-1 | MR 4067804 | Zbl 1477.06024
[20] G. Grätzer, E. Knapp: Notes on planar semimodular lattices. I. Construction. Acta Sci. Math. 73 (2007), 445-462. MR 2380059 | Zbl 1223.06007
[21] G. Grätzer, E. Knapp: Notes on planar semimodular lattices. III. Rectangular lattices. Acta Sci. Math. 75 (2009), 29-48. MR 2533398 | Zbl 1199.06029
[22] G. Grätzer, H. Lakser, E. T. Schmidt: Congruence lattices of finite semimodular lattices. Can. Math. Bull. 41 (1998), 290-297. DOI 10.4153/CMB-1998-041-7 | MR 1637653 | Zbl 0918.06004
[23] D. Kelly, I. Rival: Planar lattices. Can. J. Math. 27 (1975), 636-665. DOI 10.4153/CJM-1975-074-0 | MR 0382086 | Zbl 0312.06003
Affiliations: Gábor Czédli, Department of Algebra and Number Theory, Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, Szeged, Hungary 6720, e-mail: czedli@math.u-szeged.hu
