G. Grätzer]http://server.maths.umanitoba.ca/homepages/gratzer/

Atom-generated planar lattices

(Date: Submitted Jan. 14, 2020; revised Sept. 3, 2020)

Abstract.

In this note, we discuss planar lattices generated by their atoms. We prove that if $L$ is a planar lattice generated by $n$ atoms, then both the left and the right boundaries of $L$ have at most $n+1$ elements.

On the other hand, $L$ can be arbitrarily large. For every $k>1$ , we construct a planar lattice $L$ generated by $4$ atoms such that $L$ has more than $k$ elements.

Key words and phrases:

lattice, planar, atom-generated.

2010 Mathematics Subject Classification:

Primary: 06B05.

1. Introduction

In this note, we deal with atom-generated planar lattices (AGP lattices, for short), that is, planar lattices (finite, by definition) generated by their sets of atoms; see Figure 1 for some small examples and Figures 2–4 for some larger ones.

Refer to caption — Figure 1. $3$ -generated AGP lattices

We have two results.

Theorem 1.

Let $L$ be a planar lattice generated its atoms. If $L$ has $n$ atoms, then both the left and the right boundaries of $L$ have at most $n+1$ elements.

Theorem 2.

For every pair of integers $k,n$ with $k>1$ and $n>3$ , there is a planar lattice $L$ with the following two properties:

(i)

$L$ is generated by its $n$ atoms;
(ii)

$L$ has more than $k$ elements.

$2$ - and $3$ -generated AGP lattices are enumerated in Section 2. We prove Theorem 1 in Section 3 and Theorem 2 in Section 4.

For the basic concept and notation, see my books [6] and [7].

As usual, a planar lattice (finite, by definition) is a lattice with a planar diagram understood but not specified. For a more precise approach, see G. Czédli and G. Grätzer [5] and K. A. Baker and G. Grätzer [2].

Acknowledgement

I would like to thank Kirby Baker for his help and his contributions to this topic.

2. Small AGP lattices

We will utilize the following statement, see G. Czédli [4, 3.13A].

Lemma 3 (Left-right Inequality).

If $L$ is a planar lattice and $a<_{\textup{lr}}b$ and $b<_{\textup{lr}}c$ in $L$ , then $b<a\vee c$ .

If the AGP lattice $L$ has $2$ atoms, then $L$ must be isomorphic to $\mathsf{C}_{2}^{2}=\mathsf{B}_{2}$ . The following lemma describes an AGP lattice with $3$ atoms.

Lemma 4.

Let $L$ be an AGP lattice with $3$ atoms, $a_{1},a_{2},a_{3}$ , enumerated from left to right. Then $a_{1}\vee a_{3}$ is the unit element of $L$ .

Proof.

Since $L$ is an AGP lattice with $3$ atoms, it follows that $1=a_{1}\vee a_{2}\vee a_{3}$ . So we obtain that $1=a_{1}\vee a_{3}$ by the Left-right Inequality. ∎

If $L$ has $3$ atoms, then by Lemma 4, there are four possibilities, up to isomorphism, see Figure 1. We see that Theorem 1 holds in all four cases.

3. Boundary chains

To prepare for the proof of Theorem 1, we need some preliminary results. In this section, let $L$ be an AGP lattice with its atoms $a_{1},\dots,a_{n}$ enumerated from left to right. For $u\in L$ , define

(1)

\operatorname{At}(u)=\{\,i\mid a_{i}\leq u\,\}.

Let

(2)

\mathsf{C}_{n}=\{1\prec 2\prec\dots\prec n\}

be the $n$ element chain.

Lemma 5.

The set $\operatorname{At}(u)$ is an interval of $\mathsf{C}_{n}$ for any $u\in L$ . Moreover,

(3)		$\displaystyle\operatorname{At}(x)\subseteq\operatorname{At}(y)$	for all $x\leq y\in L$ ,
(4)		$\displaystyle\operatorname{At}(u\wedge v)=\operatorname{At}(u)\cap\operatorname{At}(v)$	for all $u,v\in L$ .

Proof.

Let $u\in L$ and let $1\leq i<j\leq n$ with $i,j\in\operatorname{At}(u)$ . By the Left-right Inequality, $k\in\operatorname{At}(u)$ for any $i<k<j$ . Therefore, $\operatorname{At}(u)$ is an interval. The other two statements are also obvious. ∎

Lemma 6.

For $k\in\{1,\dots,n\}$ , let

(5)

M_{k}=\bigcup(\,\,\uparrow\!a_{i}\mid k\leq i\leq n\,)\cup\{0\}.

Then $M_{k}$ is a sublattice of $L$ .

Proof.

By construction, $M_{k}$ is closed under joins. To show that $M_{k}$ is closed under meets, let $x,y\in M_{k}$ . Assume that $x\wedge y\notin M_{k}$ . Since $0\in M_{k}$ but $x\wedge y\notin M_{k}$ , there exists an atom $a_{i}\in\,\downarrow\!(x\wedge y)$ . Clearly, $i<k$ since otherwise $x\wedge y\in\,\uparrow\!a_{i}\subseteq M_{k}$ would contradict that $x\wedge y\notin M_{k}$ . By definition, we can pick $j_{x},j_{y}\in[k,\dots,n]$ such that $j_{x}\subseteq\operatorname{At}(x))$ and $j_{y}\in\operatorname{At}(y)$ . Using equation (3) of Lemma 5, we have that $i\in\operatorname{At}(x\wedge y)\subseteq\operatorname{At}(x)$ and $i\in\operatorname{At}(x\wedge y)\subseteq\operatorname{At}(y)$ . Since $i,j_{x}\in\operatorname{At}(x)$ and $i<k\leq j_{x}$ , Lemma 5 gives that $k\in\operatorname{At}(x)$ . Similarly, $k\in\operatorname{At}(y)$ . Equation (4) of Lemma 5 yields that $k\in\operatorname{At}(x)\cap\operatorname{At}(y)=\operatorname{At}(x\wedge y)$ , that is, $x\wedge y\in\,\uparrow\!a_{k}\subseteq M_{k}$ , contradicting the assumption that $x\wedge y\in M_{k}$ . ∎

Note an easy consequence of Lemma 6.

Corollary 7.

For $k<k^{\prime}\in\{1,\dots,n\}$ , let

(6)

M_{k,k^{\prime}}=\bigcup(\,\,\uparrow\!a_{i}\mid k\leq i\leq k^{\prime}\,)\cup\{0\}.

Then $M_{k,k^{\prime}}$ is a sublattice of $L$ .

Proof.

Intersect the sublattice of Lemma 6 and its left-right reverse. ∎

Lemma 8.

Define the principal ideals

(7)

J_{k}=\,\downarrow\!(a_{1}\vee\cdots\vee a_{k-1})

for $k=1,\dots,n$ . Then $L=J_{k}\cup M_{k}$ for $k=1,\dots,n$ .

Proof.

Let $S=J_{k}\cup M_{k}$ . Observe that $S=J_{k}\cup(M_{k}-\{0\})$ . Using that $J_{k}$ is a sublattice and a down-set, and also that $M_{k}-\{0\}$ is an up-set, it is easy to see that $S$ is a sublattice of $L$ . ∎

Now we prove Theorem 1 in the following form.

Theorem 9.

Let $L$ be an AGP lattice with all its atoms $a_{1},\dots,a_{n}$ enumerated from left to right. Define the elements $c_{\textup{l},1}=a_{1}$ , $c_{\textup{l},2}=a_{1}\vee a_{2}$ , …, $c_{\textup{l},n}=a_{1}\vee a_{n}$ . Then the chain $C$ :

(8)

0<c_{\textup{l},1}\leq c_{\textup{l},2}\leq\dots\leq c_{\textup{l},n}=1

is a maximal chain in $L$ , in fact, the left boundary of $L$ .

Proof.

The inequalities in (8) follow from the Left-right Inequality. Let $L$ be as in the theorem and let us assume that $C$ is not maximal, that is,

(9)

a_{1}\vee\cdots\vee a_{k-1}<x<a_{1}\vee\cdots\vee a_{k}

for some $x\in L$ . By Lemma 8, we can decompose $L$ as $J_{k}\cup M_{k}$ . By (9), $x\in M_{k}$ holds, and so $x\geq a_{j}$ for some $j\in\{k,\dots,n\}$ . Therefore, $[1,k]\subseteq[1,j]\subseteq\operatorname{At}(x)$ , and so $a_{1}\vee\cdots\vee a_{k}\leq x$ , contradicting (9), so $C$ is maximal.

Since all the elements of $L$ on or to the right of $C$ form a sublattice containing all its atoms $a_{1},\dots,a_{n}$ generating $L$ (see for instance, David Kelly and Ivan Rival [8]), it follows that $C$ is on the left boundary of $L$ . ∎

Theorem 9 implies Theorem 1 by left-right symmetry.

4. Large AGP lattices with $4$ atoms

To prove Theorem 2, we have to construct arbitrarily large AGP lattices with $4$ atoms.

We start with the lattice $\mathsf{K}_{1}$ , the ten-element lattice of Figure 2. It is planar. It is generated by its atoms; in fact, all but two of its elements are joins of atoms. The exceptions are $b_{1}$ and $b_{2}$ . However, $b_{1}=(a_{1}\vee a_{2})\wedge(a_{2}\vee a_{3})$ and symmetrically for $b_{2}$ .

We construct the lattice $\mathsf{K}_{n}$ inductively. To illustrate the inductive step, we first construct the lattice $\mathsf{K}_{2}$ of Figure 4.

We obtain $\mathsf{K}_{2}$ from $\mathsf{K}_{1}$ by adding six elements, $\alpha_{1},\beta_{1},\gamma_{1},\delta_{1},\varepsilon_{1},\varphi_{1}$ ; see the black filled elements of Figure 4. Observe that $\mathsf{K}_{1}$ is a meet-subsemilattice of $\mathsf{K}_{2}$ and it is almost a join-subsemilattice (hence a sublattice) of $\mathsf{K}_{2}$ . The exceptions are $a_{1}\vee c$ and $d_{1}\vee c$ (they both equal $i$ in $\mathsf{K}_{1}$ and they both equal $\alpha_{1}$ in $\mathsf{K}_{2}$ ) and symmetrically.

For the new elements, we have the following order relations:

(10)		$\displaystyle b_{1}$	$\displaystyle<\varepsilon_{1}<d_{1},$	$\displaystyle b_{2}$	$\displaystyle<\varphi_{1}<d_{2},$	$\displaystyle d_{1}$	$\displaystyle<\alpha_{1}<i,$
	$\displaystyle d_{2}$	$\displaystyle<\beta_{1}<i,$	δ₁	$\displaystyle<\varphi_{1},$
and the following joins and meets:
(11)		γ₁	$\displaystyle=\alpha_{1}\wedge\beta_{1},$	α₁	$\displaystyle=d_{1}\vee c,$	β₁	$\displaystyle=d_{2}\vee c,$	γ₁	$\displaystyle=\alpha_{1}\wedge\beta_{1}$
	ε₁	$\displaystyle=d_{1}\wedge\gamma_{1}$	φ₁	$\displaystyle=\gamma_{1}\wedge d_{1}$	$\displaystyle 1$	$\displaystyle=\varepsilon_{1}\wedge\varphi_{1}.$

Since $\mathsf{K}_{2}$ is planar ordered set with bounds, it is a lattice.

To see that $\mathsf{K}_{2}$ is generated by its atoms, first observe that the $4$ changed joins in $\mathsf{K}_{1}$ participate only in verifying that $i$ is generated by the atoms, but, of course, we have $i=a_{1}\vee a_{2}\vee a_{3}\vee a_{4}$ . So all elements of $\mathsf{K}_{2}$ are generated by the atoms in $\mathsf{K}_{2}$ .

Now the induction step is very similar. We start with the lattice $\mathsf{K}_{n-1}$ —as illustrated by Figure 4—and extend it to the lattice $\mathsf{K}_{n}$ by adding the six elements $\alpha_{n-1},\beta_{n-1},\gamma_{n-1},\delta_{n-1},\varepsilon_{n-1},\varphi_{n-1}$ , black filled in Figure 4. With obvious changes in (10) and (11), we describe $\mathsf{K}_{n}$ and verify its properties.

References

[1] K. A. Baker, P. C. Fishburn, and F. S. Roberts, Partial orders of dimension $2$ . Networks 2 (1972), 11–28.
[2] K. A. Baker and G. Grätzer, Zilber’s Theorem for planar lattices, revisited. Acta Sci. Math. (Szeged).
[3] G. Birkhoff, Lattice theory. Third edition. American Mathematical Society Colloquium Publications, Vol. XXV. American Mathematical Society, Providence, R.I. 1967.
[4] G. Czédli, Finite convex geometries of circles. Discrete Mathematics 330 (2014), 61–75.
[5] G. Czédli and G. Grätzer, Planar Semimodular Lattices: Structure and Diagrams. Chapter 3 in [6].
[6] G. Grätzer, Lattice Theory: Foundation. Birkhäuser Verlag, Basel (2011)
[7] G. Grätzer, The Congruences of a Finite Lattice, A Proof-by-Picture Approach, second edition. Birkhäuser, 2016.
[8] David Kelly and Ivan Rival, Planar lattices. Canadian J. Math. 27 (1975), 636–665.

Atom-generated planar lattices

Abstract.

Key words and phrases:

2010 Mathematics Subject Classification:

1. Introduction

Theorem 1.

Theorem 2.

Acknowledgement

2. Small AGP lattices

Lemma 3 (Left-right Inequality).

Lemma 4.

Proof.

3. Boundary chains

Lemma 5.

Proof.

Lemma 6.

Proof.

Corollary 7.

Proof.

Lemma 8.

Proof.

Theorem 9.

Proof.

4. Large AGP lattices with 44 atoms

References

4. Large AGP lattices with $4$ atoms