One Hundred Twenty-Seven Subsemilattices and Planarity
- PDF / 461,135 Bytes
- 11 Pages / 439.642 x 666.49 pts Page_size
- 12 Downloads / 214 Views
One Hundred Twenty-Seven Subsemilattices and Planarity ´ ´ 1 Gabor Czedli Received: 1 July 2019 / Accepted: 4 December 2019 / © The Author(s) 2019
Abstract Let L be a finite n-element semilattice. We prove that if L has at least 127 · 2n−8 subsemilattices, then L is planar. For n > 8, this result is sharp since there is a non-planar semilattice with exactly 127 · 2n−8 − 1 subsemilattices. Keywords Planar semilattice · Planar lattice · Subsemilattice · Number of subalgebras · Number of subuniverses · Computer-assisted proof · Finite semilattice
1 Our result and introduction This paper is dedicated to the memory of Ivo G. Rosenberg (1934–2018). In addition to his celebrated theorem describing the maximal clones of operations on a finite set, he has published many important results in many fields of mathematics. According to MathSciNet, thirteen of his papers belong to the category “Order, lattices, ordered algebraic structures”; [2] is one of these thirteen and it is a great privilege to me that I was included. In the present paper, semilattices (without adjectives) are understood as join-semilattices. In spite of this convention, sometimes we write “join-semilattice” for emphasis. Note that Theorem 1.1 below is valid also for commutative idempotent semigroups, because they are, in a well-known sense, equivalent to join-semilattices. A finite semilattice is said to be planar if it has a Hasse diagram that is also a planar representation of a graph. Our goal is to prove that finite semilattices with many subsemilattices are planar. Namely, we are going to prove the following theorem. Theorem 1.1 Let L be a finite semilattice, and let n := |L| denote the number of its elements. If L has at least 127 · 2n−8 subsemilattices, then it is a planar semilattice. This research was supported by the Hungarian Research, Development and Innovation Office under grant number KH 126581. Dedicated to the memory of Ivo G. Rosenberg G´abor Cz´edli
[email protected] http://www.math.u-szeged.hu/∼czedli/ 1
Bolyai Institute, Szeged, University of Szeged, Aradi v´ertan´uk tere 1, Szeged, 6720, Hungary
Order
Another variant of this result will be stated in Theorem 2.2. Remark 1.2 For n ≥ 9, Theorem 1.1 is sharp, since there exists an n-element non-planar semilattice with exactly 127 · 2n−8 − 1 subsemilattices. Remark 1.3 Every semilattice with at most seven elements is planar, regardless the number of its subsemilattices. While (A0 ; ∨) from Lemma 3.2 is an 8-element non-planar semilattice with 121 subsemilattices, every eight-element semilattice with at least 122 = 122 · 28−8 subsemilattices is planar. This remark will be proved at the end of Section 4. Remark 1.4 Although the numbers 63.5·2n−7 , 31.75·2n−6 , 15.875·2n−5 , . . . and 254·2n−9 , 508 · 2n−10 , 1016 · 2n−11 , . . . are all equal to 127 · 2n−8 , we want to avoid fractions as well as large coefficients of powers of 2. This explains the formulation of Theorem 1.1. Our result is motivated by similar or analogous results for lattices and for congruences; see Ahmed and
Data Loading...
