Reducing the lengths of slim planar semimodular lattices without changing their congruence lattices

Abstract

Following G. Grätzer and E. Knapp (2007), a slim 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 J(Con $L$) of join-irreducible congruences of $L$. We prove that if $1<n\in N$ and $P$ is an $n$-element JConSPS-representable poset, then there exists a slim rectangular lattice $L$ such that J(Con $L$) is isomorphic to $P$, the length of $L$ is at most $2n^2$, and $|L|\le 4n^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 $(k-2)!\cdot e^2/2$ many slim rectangular lattices of a given length $k$, where $e$ is the famous constant $\approx 2.71828$. The known properties and constructions of JConSPS-representable posets can accelerate the algorithm; we present a new construction.

arXiv comment24 pages, 6 figures. Compared to the previous versions, |P|>1 has been added at some places; furthermore, a little gap and some typos have been corrected