Search

For a lattice L of finite length n, let RCSub(L) be the collection consisting of the empty set and those sublattices of L that are closed under taking relative complements. That is, a subset X of L belongs to RCSub(L) if and only if X is join-closed, meet-closed, and whenever {a, x, b} ⊆ S, y ∈ L, x ∧ y = a, and x ∨ y = b, then y ∈ S. We prove that (1) the poset RCSub(L) with respect to set inclusion is lattice of length n + 1, (2) if RCSub(L) is a ranked lattice and L is modular, then L is 2-distributive in András P. Huhn’s sense, and (3) if L is distributive, then RCSub(L) is a ranked lattice.

We prove that a tolerance relation of a lattice is a homomorphic image of a congruence relation.

The Swing Lemma, proved by G. Gratzer in 2015, describes how a congruence spreads from a prime interval to another in a slim (having no $$\mathsf {M}_{3}$$ sublattice), planar, semimodular lattice. We generalize the Swing Lemma to planar semimodular lattices.

A planar (upper) semimodular lattice $L$ is slim if the five-element nondistributive modular lattice $M_3$ does not occur among its sublattices. (Planar lattices are finite by definition.) Slim rectangular lattices as particular slim planar semimodular lattices were defined by G. Gr\"atzer and E. Knapp in 2007. In 2009, they also proved that the congruence lattices of slim planar semimodular lattices with at least three elements are the same as those of slim rectangular lattices. In order to provide an effective tool for studying these congruence lattices, we introduce the concept of lamps of slim rectangular lattices and prove several of their properties. Lamps and several tools based on them allow us to prove in a new and easy way that the congruence lattices of slim planar semimodular lattices satisfy the two previously known properties. Also, we use lamps to prove that these congruence lattices satisfy four new properties including the two-pendant four-crown property and the forbidden marriage property., Comment: 26 pages, 11 figures

Let $n>3$ be a natural number. By a 1975 result of H. Strietz, the lattice Part$(n)$ of all partitions of an $n$-element set has a four-element generating set. In 1983, L. Z\'adori gave a new proof of this fact with a particularly elegant construction. Based on his construction from 1983, the present paper gives a lower bound on the number $\nu(n)$ of four-element generating sets of Part$(n)$. We also present a computer assisted statistical approach to $\nu(n)$ for small values of $n$. In his 1983 paper, L. Z\'adori also proved that for $n\geq 7$, the lattice Part$(n)$ has a four element generating set that is not an antichain. He left the problem whether such a generating set for $n\in\{5,6\}$ exists open. Here we solve this problem in negative for $n=5$ and in affirmative for $n=6$. Finally, the main theorem asserts that the direct product of some powers of partition lattices is four-generated. In particular, by the first part of this theorem, Part$(n_1)\times$ Part$(n_2)$ is four-generated for any two distinct integers $n_1$ and $n_2$ that are at least 5. The second part of the theorem is technical but it has two corollaries that are easy to understand. Namely, the direct product Part$(n)$ $\times$ Part$(n+1)$ $\times\dots\times$ Part$(3n-14)$ is four-generated for each integer $n\geq 9$. Also, for every positive integer $u$, the $u$-th the direct power of the direct product Part$(n)$ $\times$ Part$(n+1)$ $\times\dots\times$ Part$(n+u-1)$ is four-generated for all but finitely many $n$. If we do not insist on too many direct factors, then the exponent can be quite large. For example, our theorem implies that the $10^{127}$-th direct power of Part$(1011)$ $\times$ Part$(1012)$ $\times \dots \times$ Part$(2020)$ is four-generated., Comment: 34 pages, 6 figures

Finite (upper) nearlattices are essentially the same mathematical entities as finite semilattices, finite commutative idempotent semigroups, finite join-enriched meet semilattices, and chopped lattices. We prove that if an $n$-element nearlattice has at least $83\cdot 2^{n-8}$ subnearlattices, then it has a planar Hasse diagram. For $n>8$, this result is sharp., Comment: 71 pages, 7 figures

Let $L$ be a finite $n$-element semilattice. We prove that if $L$ has at least $127\cdot 2^{n-8}$ subsemilattices, then $L$ is planar. For $n>8$, this result is sharp since there is a non-planar semilattice with exactly $127\cdot 2^{n-8}-1$ subsemilattices., Comment: 15 pages, 2 figures

K. Adaricheva and M. Bolat have recently proved that if $U_0$ and $U_1$ are circles in a triangle with vertices $A_0,A_1,A_2$, then there exist $j\in \{0,1,2\}$ and $k\in\{0,1\}$ such that $U_{1-k}$ is included in the convex hull of $U_k\cup(\{A_0,A_1, A_2\}\setminus\{A_j\})$. One could say disks instead of circles. Here we prove the existence of such a $j$ and $k$ for the more general case where $U_0$ and $U_1$ are compact sets in the plane such that $U_1$ is obtained from $U_0$ by a positive homothety or by a translation. Also, we give a short survey to show how lattice theoretical antecedents, including a series of papers on planar semimodular lattices by G. Gratzer and E. Knapp, lead to our result., Comment: 28 pages, 7 figures

We describe the absolute retracts for the following classes of finite lattices: (1) slim semimodular lattices, (2) finite distributive lattices, and for each positive integer $n$, (3) at most $n$-dimensional finite distributive lattices. Although the singleton lattice is the only absolute retract for the first class, this result has paved the way to some other classes. For the second class, we prove that the absolute retracts are exactly the finite boolean lattices; this generalizes a 1979 result of J. Schmid. For the third class, the absolute retracts are the finite boolean lattices of dimension at most $n$ and the direct products of $n$ nontrivial finite chains. Also, we point out that in each of these classes, the algebraically closed lattices and the strongly algebraically closed lattices are the same as the absolute retracts. Slim (and necessarily planar) semimodular lattices were introduced by G. Gr\"atzer and E. Knapp in 2007, and they have been intensively studied since then. Algebraically closed and strongly algebraically closed lattices have been investigated by J. Schmid and, in several papers, by A. Molkhasi., Comment: 22 pages, 2 figures

A lattice is $(1+1+2)$-generated if it has a four-element generating set such that exactly two of the four generators are comparable. We prove that the lattice Quo$(n)$ of all quasiorders (also known as preorders) of an $n$-element set is $(1+1+2)$-generated for $n=3$ (trivially), $n=6$ (when Quo(6) consists of $209\,527$ elements), n=11, and for every natural number $n\geq 13$. In 2017, the second author and J. Kulin proved that Quo$(n)$ is $(1+1+2)$-generated if either $n$ is odd and at least $13$ or $n$ is even and at least $56$. Compared to the 2017 result, this paper presents twenty-four new numbers $n$ such that Quo$(n)$ is $(1+1+2)$-generated. Except for Quo(6), an extension of Z\'adori's method is used., Comment: 14 pages, 4 figures

We give a new proof of the fact that finite bipartite graphs cannot be axiomatized by finitely many first-order sentences among FINITE graphs. (This fact is a consequence of a general theorem proved by L. Ham and M. Jackson, and the counterpart of this fact for all bipartite graphs in the class of ALL graphs is a well-known consequence of the compactness theorem.) Also, to exemplify that our method is applicable in various fields of mathematics, we prove that neither finite simple groups, nor the ordered sets of join-irreducible congruences of slim semimodular lattices can be described by finitely many axioms in the class of FINITE structures. Since a 2007 result of G. Gr\"atzer and E. Knapp, slim semimodular lattices have constituted the most intensively studied part of lattice theory and they have already led to results even in group theory and geometry. In addition to the non-axiomatizability results mentioned above, we present a new property, called Decomposable Cyclic Elements Property, of the congruence lattices of slim semimodular lattices., Comment: 19 pages, 4 figures

For an integer $n\geq 5$, H. Strietz (1975) and L. Z\'adori (1986) proved that the lattice Part$(n)$ of all partitions of $\{1,2,\dots,n\}$ is four-generated. Developing L. Z\'adori's particularly elegant construction further, we prove that even the $k$-th direct power Part$(n)^k$ of Part$(n)$ is four-generated for many but only finitely many exponents $k$. E.g., Part$(n)^k$ is four-generated for every $k\leq 3\cdot 10^{89}$, and it has a four element generating set that is not an antichain for every $k\leq 1.4\cdot 10^{34}$. In connection with these results, we outline a protocol how to use these lattices in authentication and secret key cryptography., Comment: 20 pages, 5 figures

For bounded lattices L1 and L2, let $${f\colon L_1 \to L_2}$$ be a lattice homomorphism. Then the map $${{\rm Princ}(f)\colon \rm {Princ}(\it L_1) \to {\rm Princ}(\it L_2)}$$ , defined by $${{\rm con}(x,y) \mapsto {\rm con}(f(x),f(y))}$$ , is a 0-preserving isotone map from the bounded ordered set Princ(L1) of principal congruences of L1 to that of L2. We prove that every 0-preserving isotone map between two bounded ordered sets can be represented in this way. Our result generalizes a 2016 result of G. Gratzer from $${\{0,1}\}$$ -preserving isotone maps to 0-preserving isotone maps.

By a 1991 result of R. Freese, G. Gratzer, and E. T. Schmidt, every complete lattice A is isomorphic to the lattice Com(K) of complete congruences of a strongly atomic, 3-distributive, complete modular lattice K. In 2002, Gratzer and Schmidt improved 3-distributivity to 2-distributivity. Here, we represent morphisms between two complete lattices with complete lattice congruences in three ways. Namely, for \({i \in \{1, 2, 3\},}\) let \({A_i}\) and \({A^{\prime}_{i}}\) be arbitrary complete lattices and let \({f_i}\) : \({A_{i} \rightarrow A^{\prime}_{i}}\) be maps such that (i) \({f_1}\) is \({(\bigvee, 0)}\)-preserving and 0-separating, (ii) \({f_2}\) is \({(\bigwedge, 0, 1)}\)-preserving, and (iii) \({f_3}\) is \({(\bigvee, 0)}\)-preserving. We prove that for \({i \in \{1, 2, 3\},}\) there exist strongly atomic, 2-distributive, complete modular lattices \({K_i}\) and \({K^{\prime}_{i}}\) such that \({A_{i} \cong {\rm Com}({K_{i}}), A^{\prime}_{i} \cong {\rm Com}({K^{\prime}_{i}}),}\) and, in addition, (i) \({K_1}\) is a principal ideal of \({{K^{\prime}_{1}}}\) and \({f_1}\) is represented by complete congruence extension, (ii) \({K^{\prime}_{2}}\) is a sublattice of \({K_2}\) and \({f_2}\) is represented by restriction, and (iii) \({f_3}\) is represented as the composite of a map naturally induced by a complete lattice homomorphism from \({K_3}\) to \({K^{\prime}_{3}}\) and the complete congruence generation in \({K^{\prime}_{3}}\). Also, our approach yields a relatively easy construction that proves the above-mentioned 2002 result of Gratzer and Schmidt.

As the main achievement of the paper, we construct a three-generated, 2-distributive, atomless lattice that is not finitely presented. Also, the paper contains the following three observations. First, every coatomless three-generated lattice has at least one atom. Second, we give some sufficient conditions implying that a three-generated lattice has at most three atoms. Third, we present a three-generated meet-distributive lattice with four atoms., Comment: 12 pages, 3 figures

In addition to the unique cover $M^+$ of the variety of modular lattices, we also deal with those twenty-three known covers of $M^+$ that can be extracted from the literature. For $M^+$ and for each of these twenty-three known varieties covering it, we determine what the pair formed by the number of atoms and that of coatoms of a three-generated lattice belonging to the variety in question can be. Furthermore, for each variety $W$ of lattices that is obtained by forming the join of some of the twenty-three varieties mentioned above, that is, for $2^{23}$ possible choices of $W$, we determine how many atoms a three-generated lattice belonging to $W$ can have. The greatest number of atoms occurring in this way is only six. In order to point out that this need not be so for larger varieties, we construct a $47\,092$-element three-generated lattice that has exactly eighteen atoms. In addition to purely lattice theoretical proofs, which constitute the majority of the paper, some computer-assisted arguments are also presented., Comment: 24 pages, 4 figures (plus a logo). In the earlier version, the main result stated less then promised in the abstract. This error and some small imperfections have been corrected

Let $L$ be a lattice of finite length and let $d$ denote the minimum path length metric on the covering graph of $L$. For any $\xi=(x_1,\dots,x_k)\in L^k$, an element $y$ belonging to $L$ is called a median of $\xi$ if the sum $d(y,x_1)+\cdots+d(y,x_k)$ is minimum. The lattice $L$ satisfies the $c_1$-median property if, for any $\xi=(x_1,\dots,x_k)\in L^k$ and for any median $y$ of $\xi$, $y\leq x_1\vee\dots\vee x_k$. Our main theorem asserts that if $L$ is an upper semimodular lattice of finite length and the breadth of $L$ is less than or equal to $2$, then $L$ satisfies the $c_1$-median property. Also, we give a construction that yields semimodular lattices, and we use a particular case of this construction to prove that our theorem is sharp in the sense that $2$ cannot be replaced by $3$., Comment: 12 pages, 1 figure