## The best extending cover-preserving geometric lattices of semimodular lattices ∗

Peng He , Xue-ping Wang 1 † 2 ‡

1. College of Applied Mathematics, Chengdu University of Information Technology Chengdu 610225, Sichuan, People's Republic of China

- 2. School of Mathematical Sciences, Sichuan Normal University

Chengdu 610066, Sichuan, People's Republic of China

Corresponding author's e-mail address: xpwang1@hotmail.com

## Abstract

In 2010, G´bor Cz´ edli and E. Tam´s Schmidt mentioned that the best covera a preserving embedding of a given semimodular lattice is not known yet [A cover-preserving embedding of semimodular lattices into geometric lattices, Advances in Mathematics 225 (2010) 2455-2463]. That is to say: What are the geometric lattices G such that a given finite semimodular lattice L has a coverpreserving embedding into G with the smallest | G | ? In this paper, we propose an algorithm to calculate all the best extending cover-preserving geometric lattices G of a given semimodular lattice L and prove that the length and the number of atoms of every best extending cover-preserving geometric lattice G equal the length of L and the number of non-zero join-irreducible elements of L , respectively. Therefore, we comprehend the best cover-preserving embedding of a given semimodular lattice.

AMS classification:

06C10; 06B15

Keywords : Finite atomistic lattice; Semimodular lattice; Geometric lattice; Cover-preserving embedding

∗ Supported by the National Natural Science Foundation of China (nos.11901064 and 12071325)

† E-mail address : hepeng@cuit.edu.cn

‡ Corresponding author

## 1 Introduction

Let L be a lattice. For all a, b ∈ L a , ‖ b denotes that a /notgreaterequal b and a /notlessequal b , and a ∦ b denotes that a ≥ b or a ≤ b . a ≺ b means that a &lt; b and there is no element c ∈ L such that a &lt; c &lt; b , and a /precedesequal b represents that a ≺ b or a = b . The set of non-zero join-irreducible elements and the set of atoms of L will be denoted by J L ( ) and A L ( ), respectively. The length of L , that is, sup { n : L has an ( n + 1)-element chain } , will be denoted by /lscript ( L ). Let A and B be two sets. We define A -B = { x ∈ A : x / ∈ B } . We assume that the readers are familiar with the basic notions of lattices such as a partially ordered set (poset), a chain, a lattice, a distributive lattice, a modular lattice, a semimodular lattice etc.. Here, we just recall a necessary concept from the theory of lattices (see, e.g., [3, 9]). We say a lattice L is (upper) semimodular if a ≺ b implies a ∨ c /precedesequal b ∨ c for all a, b, c ∈ L . We know from Crawely and Dilworth [3, Theorem 3.7] (see also [9, Theorem 1.7.1]) that for a strongly atomic algebraic lattice L , a semimodularity is equivalent to Birkhoff's condition:

for all a, b ∈ L, if a ∧ b ≺ a and a ∧ b ≺ b, then a ≺ a ∨ b and b ≺ a ∨ b.

It is well known that if L is a semimodular lattice with /lscript ( L ) = m and | J L ( ) | = n , then n ≥ m (see [9]).

Classically semimodular lattices arise out of certain closure operators satisfying what is now usually called the Steinitz-Mac Lane exchange property. A semimodularity is one of the most important links between combinatorics and lattice theory (see, e.g., [4,9]), and the structure of a semimodular lattice plays an important role in lattice theory (see, e.g., [6, 7]). A particular interest is deserved by geometric lattices, originally called matroids, which are semimodular atomistic lattices of finite length.

The Dilworth Embedding Theorem states that each finite lattice L can be embedded in a finite geometric lattice (see [3]). Further, P. Pudl´k, J. T¨ma [8] proved that each a u finite lattice L can be embedded in a finite partition lattice (finite partition lattices are geometric lattices). In 1986, G. Gr¨ atzer and E. W. Kiss [5] showed that each finite semimodular lattice L has a cover-preserving embedding into a finite geometric lattice. Recently, G. Cz´dli and E. T. Schmidt [4] extended the results in [5], and they proved e that each semimodular lattice L of finite length has a cover-preserving embedding into a geometric lattice G of the same length and the number of atoms of G equals the number of non-zero join-irreducible elements of L . That is, they proved the following theorem.

Theorem 1.1 ( [4]) Let L be a semimodular lattice of finite length. Then there exists a geometric lattice G such that L is a cover-preserving sublattice of G , | J L ( ) | = | A G ( ) | and /lscript ( L ) = /lscript ( G ) .

Finally, they mentioned that the best cover-preserving embedding is not known yet. That is to say: What are the geometric lattices G such that a given finite semimodular lattice L has a cover-preserving embedding into G with the smallest | G | ? In this paper, we shall construct all the best cover-preserving embeddings of a given finite semimodular lattice L into geometric lattices G and prove that the length and the number of atoms of every best extending cover-preserving geometric lattice G equal the length of L and the number of non-zero join-irreducible elements of L , respectively.

For the detailed information on semimodular lattices and partially ordered sets the readers are referred to [1,3,6,9]. We use the terminologies and notations of [1,3].

## 2 Atomistic partially ordered sets

In this section, we shall introduce the concept of an atomistic partially ordered set and then investigate some of its basic properties.

Definition 2.1 Let ( P, ≤ ) be a finite partially ordered set and

$$\ell ( P ) = \sup \{ n \, \colon P \text{ has an } ( n + 1 ) \text{-element chain} \}.$$

Then we say that /lscript ( P ) is the length of P .

If P has the minimum element 0, then let /lscript P ( x ), or /lscript ( x ) for brevity, denote the length of [0 , x ] for each element x ∈ P . Thus, /lscript (0) = 0 and /lscript (1) = /lscript ( P ) when 1 is the maximum element of P .

Similar to the definitions of atoms of lattices, an element that covers the least element 0 of a partially ordered set P is referred to as an atom of P , and denoted by A P ( ) the set of atoms of P , i.e., A P ( ) = { x ∈ P : x /follows 0 } . In particular, A P ( y ) = A ([0 , y ]), or A y ( ) = A ([0 , y ]) for brevity, for each y ∈ P .

Example 2.1 The Hasse diagram of a partially ordered set P is shown as Fig.1.

Fig.1 The partially ordered set P .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-1619a513-afd4-4ccd-a40a-e227c26e580e.jpg)

In Fig.1, A P ( ) = A (1) = { a, b, c } , A x ( ) = A y ( ) = { a, b } and A (0) = ∅ .

Definition 2.2 A finite partially ordered set P with the minimum element 0 is atomistic if and only if the following two conditions are satisfied: for all x, y ∈ P ,

- (1) x &lt; y implies that A x ( ) /subsetnoteql A y ( );
- (2) x ‖ y yields that A x ( ) /notsubseteql A y ( ) and A y ( ) /notsubseteql A x ( ).

Fig.2 The atomistic partially ordered set P .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-488da6bf-2fde-472a-8df7-492bb5f5b617.jpg)

By Definition 2.2, one can check that Fig.1 is not atomistic since x ‖ y but A x ( ) = A y ( ), and Fig.2 is atomistic. Clearly, every finite atomistic lattice is an atomistic partially ordered set, but the inverse is not true generally. For example, Fig.2 is an atomistic partially ordered set, but it is not a finite atomistic lattice since it is not a lattice. However, the following lemma is clear.

Lemma 2.1 If a finite atomistic partially ordered set P is a lattice, then P is an atomistic lattice.

Let P ( X ) be the power set of a nonempty set X . Then we easily verify the following lemma.

Lemma 2.2 Let | X &lt; | ∞ and P ⊆ P ( X ) . If ∅ ∈ P and {{ x } : x ∈ X } ⊆ P then ( P, ⊆ ) is a finite atomistic partially ordered set.

For convenience, in the following, if P is a finite atomistic partially ordered set then we denote S P = { A x ( ) : x ∈ P } .

Lemma 2.3 If P is a finite atomistic partially ordered set, then ( P, ≤ ∼ S ) = ( P , ⊆ ) .

Proof. For x ∈ P , define f : P -→ S P to be a map such that

$$f ( x ) = A ( x ) \text{ for any } x \in P.$$

We will show that the map f is an isomorphism of partially ordered sets.

/negationslash

It is clear that the map f is well-defined. If x, y ∈ P and x = y , then f ( x ) = A x ( ) = A y ( ) = f ( y ) by Definition 2.2. Hence, the map f is injective. Moreover, it is clearly that there exists x ∈ P such that U = A x ( ) = f ( x ) for any U ∈ S P from the definition of S P , i.e., the map f is surjective. Consequently, the map f is a one-to-one map. Below, we only need to prove that both f and its inverse are order-preserving.

/negationslash

Set x, y ∈ P and x &lt; y , and observe that application of the condition (1) of Definition 2.2 yields f ( x ) = A x ( ) /subsetnoteql A y ( ) = f ( y ). Thus the map f is order-preserving. Now suppose that U, V ∈ S P and U /subsetnoteql V . Then there exist x, y ∈ P such that U = A x ( ) /subsetnoteql V = A y ( ). By Definition 2.2, x &lt; y . Thus, the inverse of f is order-preserving. Therefore, ( P, ≤ ∼ ) = ( S P , ⊆ ).

By Lemma 2.3, every finite atomistic partially ordered set can be considered as a set of sets. For instance, Fig.2 and Fig.3 are isomorphic.

}

Fig.3 The atomistic partially ordered set S P .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-17d3b6b7-55ad-4102-9f7c-54d9b15f3c37.jpg)

Definition 2.3 Let P be a finite atomistic partially ordered set. A map I P from P to the power sets of P ( A P ( )) is called an independent function on P if it has the following two properties: for any x ∈ P ,

- (1) if /lscript ( x ) = 0, then I P ( x ) = {∅} ;
- (2) if /lscript ( x ) ≥ 1, then

$$\mathfrak { I } _ { P } ( x ) = \{ S \cup \{ a \} \colon S \in \mathfrak { I } _ { P } ( y ), a \in A ( x ) - A ( y ), \ell ( x ) = \ell ( y ) + 1 \text{ and } x \succ y \}.$$

Clearly, ⋃ I P ( x ) = A x ( ) for any x ∈ P . Let P be a finite atomistic lattice. If x, y ∈ P , x ‖ y , then σ /notsubseteql A y ( ) for any σ ∈ I P ( x ).

From Definition 2.3 and Theorem 6.5 in [3], the following lemma is obviously.

Lemma 2.4 Let L be a finite geometric lattice and x ∈ L . Then the following three conditions are equivalent:

- (1) S ∈ I L ( x ) ;
- (2) S is a maximal independent set of atoms of [0 , x ] ;
- (3) S is an independent set of atoms of L and ∨ S = x .

The diamond M 3 (see Fig.4) is a geometric lattice and I M 3 (1) = {{ a, b } { , a, c } { , b, c }} . One can verify that a ∨ b = a ∨ c = b ∨ c =1, and { a, b } { , a, c } and { b, c } are maximal independent sets of atoms of M 3 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-e97aa99e-29d6-4930-8d65-f314d76a1524.jpg)

## 3 Constructions of geometric lattices

/negationslash

For the rest of this paper, unless otherwise stated, let L be a fixed finite semimodular lattice. Following the convention of, say, Crawley and Dilworth [3] or Birkhoff [1], we assume that L is non-empty. Let H L ( ) = L -A L ( ) ∪ { 0 } . For x ∈ H L ( ), let ∆( ) be x a finite set satisfying that ∆( x ) ∩ L = ∅ and ∆( x ) ∩ ∆( ) = y ∅ while x = y , where ∆( x ) may be empty set. Insert every element in ∆( x ) into L . Extend the original order by 0 ≺ x ′ ≺ x for every x ′ ∈ ∆( ); this way we obtain a finite partially ordered set ( x P, ≤ ) with P = L ∪ ⋃ x ∈ H L ( ) ∆( ). Notice that if ( x P, ≤ ) is a lattice, then we call it an extending lattice of L . The constructions of three new finite partially ordered sets P , P 1 2 and P 3 are depicted in Fig.5; the black-filled elements are the inserted ones.

Fig.5 An example of L and the three extensions P , P 1 2 and P 3 , respectively.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-fe0e6b91-548e-4fd5-8097-b0af9ffd992f.jpg)

/negationslash

Definition 3.1 If ∆( x ) = ∅ for every x ∈ J L ( ) ∩ H L ( ), then ( P, ≤ ) is called an extending standard form of L where P = L ∪ ⋃ x ∈ H L ( ) ∆( ). x

Now, let E ( L ) be the set of all the finite extending standard forms of L . In Fig.5, one can check that P , P 2 3 ∈ E ( L ) but P 1 / ∈ E ( L ).

In what follows, we write L ↪ → ≺ P when L is a cover-preserving sublattice of a lattice P , and symbols L ↪ → P , L ↪ → ∨ P and L ↪ → ∧ P stand for that L is a sublattice, a ∨ -subsemilattice and a ∧ -subsemilattice of a lattice P , respectively. Then the following lemma is obvious.

Lemma 3.1 Suppose that P ∈ E ( L ) . Then P is an atomistic lattice, /lscript ( L ) = /lscript ( P ) and L ↪ → ≺ P .

For convenience, if P ∈ E ( L ), then we denote ∆ P ( L ) = P -L . It is well known that a finite semimodular lattice L can also be expressed as sets of set (see [2]). Therefore, by Lemma 3.1 and Definition 3.1, if P ∈ E ( L ), then there exists a lattice ( T P L , ⊆ ) with T P L ⊆ S P such that

$$L \cong \mathcal { T } _ { L } ^ { P } \hookrightarrow \overset { \sim } { \mathcal { S } } _ { P } \cong P$$

and the identity map i d is a cover-preserving embedding map from T P L to S P . (2)

In fact, T P L ∪ A ( S P ) = S P .

Consider the semimodular lattice L and L 's extending standard form P 2 represented in Fig.5 again. Then the two lattices ( T P 2 L , ⊆ ) and ( S P 2 , ⊆ ) in Fig.6 satisfy formula (1).

Fig.6 Two lattices ( T P 2 L , ⊆ ) and ( S P 2 , ⊆ ).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-1697f3a9-d524-48a3-a2c0-dbbd7b3cc610.jpg)

By formula (1) and the construction of L 's extending standard forms, the following lemma is clearly.

Lemma 3.2 Let Q ∈ E ( L ) with | A Q ( ) | &gt; J L | ( ) . | Then there exists an element r ∈ ∆ ( Q L ) such that Q - { } r ∈ E ( L ). Further, let P = Q - { } r . Then we have that L ∼ T = P L ↪ → S ≺ P and T P L = { X -{ } r : X ∈ T Q L } where T Q L satisfies formulas (1) and (2).

The following example illustrates Lemma 3.2.

Example 3.1 Consider the semimodular lattice L and L 's extending standard form P 3 represented in Fig.5 again. Then the two lattices ( T P 3 L , ⊆ ) and ( S P 3 , ⊆ ) in Fig.7 satisfy formulas (1) and (2).

Fig.7 Two lattices ( T P 3 L , ⊆ ) and ( S P 3 , ⊆ ) .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-d5d2be36-fa1d-4bea-9ecf-edd89d1da5ba.jpg)

Obviously, P 2 = P 3 -{ d ′ 1 } . Then, from Fig.6, we know that L ∼ T = P 2 L ↪ → S ≺ P 2 and T P 2 L = { X -{ d ′ 1 } : X ∈ T P 3 L } .

As a conclusion of this section, we shall supply an algorithm to construct a finite geometric lattice G which satisfies that L ↪ → ≺ G and /lscript ( G ) = /lscript ( L ).

In the following, for each finite atomistic partially ordered set P with /lscript ( P ) = m , we define two maps φ P and ϕ P from { 1 , · · · , m } to the power set of P ( A P ( )) and P ( P ) as

$$\phi _ { P } ( i ) = \{ \sigma \in \mathfrak { I } _ { P } ( x ) \, \colon \ell ( x ) = i, x \in P \}$$

and

$$\varphi _ { P } ( i ) = \{ x \in P \, \colon \ell ( x ) = i \},$$

respectively. Let ( O ⊆ , ) be an atomistic partially ordered set, and

$$\overline { X _ { \mathcal { O } } } = \bigvee _ { \mathcal { O } } \{ T \in A ( \mathcal { O } ) \, \colon T \subseteq X \}$$

for any set X ⊆ 1 O when ∨ O { T ∈ A ( O ) : T ⊆ X } exists. Clearly, if X ∈ O , then X O = X .

Suppose that P ∈ E ( L ) and /lscript ( L ) = m . Then the following algorithm's output is a finite geometric lattice whose proof will be given in the next section.

Algorithm 3.1 Input: Q = ∅ R , = S P , k = 3 , t = 0 and m = ( /lscript L ) . Output: Q .

Step 1 . Q := R and t := k . If there exists X ∈ ϕ Q ( k ) which has a proper subset U satisfying the following three conditions:

- (i1) if V ∈ ϕ Q ( t -1) and Y ⊆ U ∩ V then Y R ⊆ U ;
- (i2) if σ ∈ φ Q ( k -1) then ⋃ σ /notsubseteql U ; and
- (i3) if V ∈ ϕ Q ( k -1) , then U /notsubseteql V ;

then Q := Q∪{ } U . Otherwise, k := k + 1 , and if k ≥ m + 1 then go to Step 5 and if not, go to Step 1.

Step 2 . If /lscript Q ( U ) = k -1 , then k := 3 , R := Q and go to Step 1.

Step 3 . If U has a proper subset W which satisfies the following three conditions:

- (j1) if V ∈ ϕ Q ( t -1) and Y ⊆ W ∩ V then Y R ⊆ W ;
- (j2) if σ ∈ φ Q ( k -2) then ⋃ σ /notsubseteql W ; and
- (j3) if V ∈ ϕ Q ( k -2) then W /notsubseteql V ;

then Q := Q∪{ W } . Otherwise, go to Step 1.

Step 4 . If /lscript Q ( W ) = k -2 , then k := 3 , R := Q and go to Step 1. Otherwise, k := k -1 and go to Step 3.

Step 5 . Stop.

## 4 All the finite geometric lattices

In this section, we shall first prove that the output Q in Algorithm 3.1 is an atomistic lattice, and then verify that L is a cover-preserving sublattice of Q . Finally, we shall show that all the extending cover-preserving geometric lattices of L with the same length can be constructed by Algorithm 3.1.

Below this paper, for convenience, if ( P, ≤ ) is a finite atomistic lattice with n atoms, then we denote A P ( ) = { 1 , · · · , n } , and if ( S ⊆ , ) is a finite atomistic lattice with m atoms, then we denote A ( S ) = {{ } · · · 1 , , { m }} , and observe that

$$U \wedge _ { \mathcal { S } } V = U \cap V$$

for any U, V ∈ S .

Lemma 4.1 Every output Q in Algorithm 3.1 is a finite atomistic lattice.

Proof. Note that inasmuch as Algorithm 3.1 and Lemmas 2.2 and 3.1, we know that every output Q is a finite atomistic partially ordered set and it has the minimum element and the maximum element. Then it suffices to show that the output Q is a ∧ -semilattice. Note that S P is an atomistic lattice by Lemma 3.1. Obviously, the R in Step 3 equals to the R in Step 1. Hence, by Algorithm 3.1, we only need to prove that each partially ordered set R from Steps 2 and 4 returning to Step 1 in Algorithm 3.1 is a ∧ -semilattice.

For convenience, we next denote

$$\mathcal { D } _ { H, G } = \{ W \in \mathcal { R } \, \colon W \subseteq H \cap G \}.$$

One can see that D H,G = D G,H .

The rest of the proof will be completed in three steps.

A. If R is in Step 2, then R = Q∪{ M t -1 } , in which Q is an atomistic lattice and M t -1 is a proper subset of a certain X in ϕ Q ( ) where t M t -1 satisfies the conditions (i1), (i2) and (i3). Let E,F ∈ R . Then there are three cases.

Case 1. If E,F ∈ Q , then as Q is an atomistic lattice, we know that E ∧ Q F = E ∩ F is the maximum of D E,F . Therefore, E ∧ R F = E ∩ F ∈ R .

Case 2. If E ∈ Q and F = M t -1 , then suppose that E ∦ M t -1 . Thus E ∧ R M t -1 = E ∩ M t -1 ∈ R clearly. Now, assume that E ‖ M t -1 . If R ∈ D E,M t -1 then R /subsetnoteql E and R /subsetnoteql M t -1 . We claim that X /notsubseteql E . Otherwise X ⊆ E , which means that M t -1 /subsetnoteql X ⊆ E , contrary to E ‖ M t -1 . We can distinguish two subcases.

Subcase 1. If E /subsetnoteql X , then /lscript Q ( E ) ≤ t -1 since X ∈ ϕ Q ( ). t

Subcase 2. If E ‖ X , then E ∧ Q X = E ∩ X /subsetnoteql X . Thus /lscript Q ( E ∩ X ) ≤ t -1.

From Subcases 1 and 2, we know that there exists an element E ∩ X ∈ Q such that /lscript Q ( E ∩ X ) ≤ t -1 and E ∩ M t -1 ⊆ E ∩ X since M t -1 /subsetnoteql X . Thus

$$E \cap M _ { t - 1 } \subseteq M _ { t - 1 } \cap E \cap X,$$

and there exists an element K ∈ ϕ Q ( t -1) such that E ∩ X ⊆ K , or E ∩ X ∈ A ( Q ) by Algorithm 3.1. Then by (i1) of Algorithm 3.1, we have that ( E ∩ M t -1 ) Q ⊆ M t -1 . Note that ( E ∩ M t -1 ) Q ⊆ E . Therefore,

$$\overline { ( E \cap M _ { t - 1 } ) _ { \mathcal { Q } } } = E \cap M _ { t - 1 } \in \mathcal { D } _ { E, M _ { t - 1 } }.$$

Consequently, E ∧ R M t -1 = E ∩ M t -1 ∈ R , i.e., E ∧ R F ∈ R . Case 3. If E,F ∈ R - Q , then clearly E ∧ R F = E ∩ F ∈ R . In summary, R is a finite ∧ -semilattice.

B. If R is in Step 4 and R = Q∪{ M t -1 , M t -2 } in which M t -2 is a proper subset of M t -1 and it satisfies the conditions (j1), (j2) and (j3). By Algorithm 3.1, we know that M t -2 /subsetnoteql M t -1 /subsetnoteql X . Suppose that E,F ∈ R . There are four cases as follows.

Case i. If E,F ∈ Q , then similar to the proof of Case 1, we have that E ∧ R F = E ∩ F ∈ R .

Case ii. If E ∈ Q and F = M t -1 , then similar to the proof of Case 2, we know that

$$E \wedge _ { \mathcal { R } } M _ { t - 1 } = E \cap M _ { t - 1 } \in \mathcal { R }.$$

Case iii. If E ∈ Q and F = M t -2 , then suppose that E ∦ M t -2 . Thus

$$E \wedge _ { \mathcal { R } } M _ { t - 2 } = E \cap M _ { t - 2 } \in \mathcal { R }.$$

Now, assume that E ‖ M t -2 . Obviously, R /subsetnoteql E and R /subsetnoteql M t -2 for any R ∈ D E,M t -2 , and E ∩ M t -2 /subsetnoteql E . There are two subcases as follows.

/negationslash

Subcase (i). If E ∦ M t -1 , then M t -1 /subsetnoteql E or E /subsetnoteql M t -1 since E = M t -1 . We claim that E /subsetnoteql M t -1 . Otherwise, M t -2 /subsetnoteql M t -1 /subsetnoteql E , contrary to the fact that E ‖ M t -2 . Thus E /subsetnoteql X , and it follows from X ∈ ϕ Q ( ) that t

$$\ell _ { \mathcal { Q } } ( E ) \leq t - 1.$$

Subcase (ii). If E ‖ M t -1 , then similar to the proof of Subcase 2, we know that there exists an element E ∩ X ∈ Q such that

$$M _ { t - 2 } \cap E \subseteq E \cap X \text{ and } \ell _ { \mathcal { Q } } ( E \cap X ) \leq t - 1$$

since M t -2 ∩ E ⊆ M t -1 ∩ E .

Subcases (i) and (ii) mean that there exists an element E ∩ X ∈ Q such that

$$\ell _ { \mathcal { Q } } ( E \cap X ) \leq t - 1 \text{ and } E \cap M _ { t - 2 } \subseteq E \cap X.$$

Hence

$$E \cap M _ { t - 2 } \subseteq M _ { t - 2 } \cap E \cap X,$$

and there exists an element K ∈ ϕ Q ( t -1) such that E ∩ X ⊆ K , or E ∩ X ∈ A ( Q ) by Algorithm 3.1. Then by (j1) of Algorithm 3.1, we have that ( E ∩ M t -2 ) Q ⊆ M t -2 . Note that ( E ∩ M t -2 ) Q ⊆ E . Therefore,

$$\overline { ( E \cap M _ { t - 2 } ) _ { \mathcal { Q } } } = E \cap M _ { t - 2 } \in \mathcal { D } _ { E, M _ { t - 2 } }.$$

.

Consequently, E ∧ R M t -2 = E ∩ M t -2 ∈ R . Case iv. If E,F ∈ R - Q , then, clearly, E ∧ R F = E ∩ F ∈ R In summary, R is a finite ∧ -semilattice.

C. Analogously, if R is in Step 4 and R = Q ∪ { M t -1 , M t -2 , · · · , M t -r } for r ∈ { 3 , · · · , t - } 2 where M t -r is a proper subset of M t -( r -1) and it satisfies the conditions (j1), (j2) and (j3), then we can prove that R is a finite ∧ -semilattice.

To sum up, the output Q in Algorithm 3.1 is a finite atomistic lattice. This completes the proof.

Algorithm 3.1, Definition 2.3 and Lemma 4.1 imply the following lemma.

Lemma 4.2 Let P ∈ E ( L ) , and Q be the output of Algorithm 3.1. Then the following three statements hold.

- (1) /lscript S P ( X ) = /lscript Q ( X ) for any X ∈ S P .
- (2) If σ ∈ I S P ( X ) , then σ ∈ I Q ( X ) for any X ∈ S P .

/negationslash

- (3) If X,Y ∈ ϕ Q ( k ) and X = Y , then ⋃ σ /notsubseteql Y for any σ ∈ I Q ( X ) .

Lemma 4.3 For every output Q in Algorithm 3.1, L ↪ → Q ≺ .

Proof. Note that /lscript ( L ) = /lscript ( P ) since P ∈ E ( L ), and by Lemma 4.2, /lscript ( Q ) = /lscript ( S P ). Thus we have that

$$\ell ( \mathcal { Q } ) = \ell ( L ) \, \sin c { \ } P \cong \mathcal { S } _ { P }.$$

By formula (1) and Algorithm 3.1, there exists a lattice T P L such that T P L ⊆ S P ⊆ Q and L ∼ T = P L ↪ → S ≺ P . Therefore, we only need to prove that T P L ↪ →Q .

First, by Lemma 3.1, S P is a finite atomistic lattice. Then E ∧ T P L F = E ∩ F for any E,F ∈ T P L by (2). On the other hand, from Lemma 4.1, we know that Q is a finite atomistic lattice, which follows that H ∧ Q G = H ∩ G for any H,G ∈ Q . Consequently, T P L ↪ → Q ∧ since T P L ⊆ Q .

Next, we shall prove that T P L ↪ → Q ∨ .

/negationslash

Let M,N ∈ T P L . Set M ∨ T P L N = Z and M ∨ Q N = T . Then M ∨ S P N = Z by (2). Suppose that T = Z , then T ∈ Q - S P . Obviously, T /subsetnoteql Z since T P L ⊆ Q . We claim that M ‖ N . Otherwise, T = Z = M ∪ N , a contradiction. As T P L is a finite semimodular lattice, we know that T P L contains a sublattice lattice as presented in Fig.8 (the required coverings ≺ and ⊆ in the lattice T P L are indicated by one line and double lines in Fig.8, respectively). Furthermore, by formula (1), Fig.8 is also a sublattice of S P and /lscript T P L ( R ) = /lscript S P ( R ) for any R ∈ T P L . Therefore, by Lemma 4.2,

$$\ell _ { \mathcal { Q } } ( R ) = \ell _ { \mathcal { S } _ { P } } ( R ) = \ell _ { \mathcal { T } _ { L } ^ { P } } ( R )$$

for every R ∈ T P L .

Fig.8 A sublattice of T P L .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-102afa1a-8579-42ed-b777-8bb546325b5a.jpg)

Now, set /lscript T P L ( N ) = t . As T P L is a finite semimodular lattice and Fig.8 is a sublattice of T P L , we obviously have that /lscript T P L ( N k ) = t + k and /lscript T P L ( Z ) = t + k +1, which together with formula (3) imply

$$\ell _ { \mathcal { Q } } ( N _ { k } ) = \ell _ { \mathcal { S } _ { P } } ( N _ { k } ) = t + k \text{ and } \ell _ { \mathcal { Q } } ( Z ) = \ell _ { \mathcal { S } _ { P } } ( Z ) = t + k + 1.$$

Let η ∈ I S P ( N ). Then by Definition 2.3 and formula (4), there exists a subset ρ of A S P ( M ) such that η ∪ ρ = π ∈ I S P ( N k ) since Fig.8 is also a sublattice of S P . Hence π ∈ I Q ( N k ) by Lemma 4.2.

/negationslash

In summary, T P L ↪ → Q ∨ . Therefore, L ↪ → Q ≺ . This completes the proof. Notice that

Using formula (4), T /subsetnoteql Z and T ∈ Q - S P , clearly, there is a T 0 ∈ Q - S P such that M ∪ N ⊆ T ⊆ T 0 /subsetnoteql Z and /lscript Q ( T 0 ) = t + k , which follow by Lemma 4.2 that ⋃ σ /notsubseteql T 0 for every σ ∈ I Q ( N k ) since /lscript Q ( N k ) = t + k and T 0 = N k . However, π = η ∪ ρ ⊆ A S P ( M ) ∪ A S P ( N ), and then ⋃ π ⊆ M ∪ N ⊆ T 0 , contrary to π ∈ I Q ( N k ).

the identity map i d is a cover-preserving embedding map from T P L to Q (5)

by the proof of Lemma 4.3

Below, denote

$$\mathfrak { S } = \{ \mathcal { Q } \colon \mathcal { Q } \text{ is an output of Algorithm 3.1} \}$$

and

$$\overline { \mathfrak { S } } = \left \{ \mathcal { Q } \in \mathfrak { S } \, \colon \mathcal { Q } \, \text{ satisfies the condition } ( \mathfrak { M } ) \right \}$$

in which the condition ( M ) is as follows. ( M ): If X ∈ ϕ Q ( k ), then /lscript Q (( X ∪ R ) Q ) = k +1 for any R ∈ A ( Q -) A X ( ).

Lemma 4.4 Every Q ∈ S is a finite geometric lattice.

Proof. By Lemma 4.1, we know that Q is a finite atomistic lattice. Then [ ∅ , M ] for any M ∈ Q is a geometric lattice when /lscript Q ( M ) ≤ 2. Now, suppose that [ ∅ , M ] is a geometric lattice for every M ∈ Q with /lscript Q ( M ) ≤ k . By induction, we shall prove that [ ∅ , M ] is a geometric lattice for every M ∈ Q with /lscript Q ( M ) = k +1.

Assume that [ ∅ , M ] is not a semimodular lattice. Then there exist two elements G,H ∈ [ ∅ , M ] such that G /follows G ∩ H,H /follows G ∩ H but G ∨ H /notfollows G or G ∨ H /notfollows H , say, G ∨ H /notfollows G . Note that G ∨ H ∈ ∅ [ , M ]. We claim that G ∨ H = M . Otherwise, G ∨ H /subsetnoteql M . Hence, /lscript Q ( G ∨ H ) ≤ k . Therefore, [ ∅ , G ∨ H ] is a geometric lattice. This follows that G ∨ H /follows G since G,H,G ∩ H,G ∨ H ∈ [ ∅ , G ∨ H ], a contradiction. Consequently, G ∨ H = M , and which yields that [ ∅ , M ] contains a sublattice as presented in Fig.9 (the required coverings ≺ and ⊆ in the lattice [ ∅ , M ] are indicated by one line and double lines in Fig.9, respectively).

Fig.9 A sublattice of [ ∅ , M ].

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-68f2b357-918a-4b33-8f2b-e9a060972c31.jpg)

Let R ∈ A H ( ) -A G ( ). We claim that R /notsubseteql G m -1 . Otherwise, G m -1 ∩ H /supersetnoteql G ∩ H . Then H ⊇ G m -1 ∩ H /supersetnoteql G ∩ H together with H /follows G ∩ H yields that G m -1 ⊇ H . Thus G ∨ H ⊆ G m -1 , a contradiction to the fact G ∨ H = M . Therefore, R /notsubseteql G m -1 , then R ∈ A ( Q -) A G ( m -1 ). Note that /lscript Q ( G m -1 ) ≤ k -1 by the structure of Fig.9 and /lscript Q ( M ) = k +1. Then by ( M ), we know that

$$\ell _ { \mathcal { Q } } ( \overline { ( G _ { m - 1 } \cup R ) _ { \mathcal { Q } } } ) \leq k.$$

On the other hand, H ⊇ (( G ∩ H ) ∪ R ) Q /supersetnoteql G ∩ H , it follows from H /follows G ∩ H that H = (( G ∩ H ) ∪ R ) Q . Thus ( G m -1 ∪ H ) Q = ( G m -1 ∪ R ) Q , and then /lscript Q (( G m -1 ∪ H ) Q ) ≤ k by formula (6). However, ( G m -1 ∪ H ) Q ⊇ G ∨ H = M and /lscript Q ( M ) = k +1, a contradiction. Therefore, [ ∅ , M ] is a semimodular lattice.

Consequently, [ ∅ , M ] is a finite geometric lattice as Q is a finite atomistic lattice, and the proof of the lemma is complete.

Notice that from Lemmas 4.1, 4.3 and 4.4, we know that every output Q in Algorithm 3.1 with condition ( M ) is a geometric lattice and L is a cover-preserving sublattice of Q .

The following example will illustrate that every output Q in Algorithm 3.1 with condition ( M ) is a geometric lattice and L is a cover-preserving sublattice of Q .

Example 4.1 Consider the lattices L and P ∈ E ( L ) represented in Fig.10, respectively.

❞

❞

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-744d4629-a379-4cbe-aa00-eb23528c22b4.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-59f16b73-d753-48e9-a679-4533de6e0b3d.jpg)

Obviously, T P L and S P satisfy formula (1), respectively.

Input : Q = ∅ R , = S P , k = 3, t = 0 and m = 3.

Output

:

Q

.

Step 1.

Q

:=

R

,

t

:= 3,

U

1

=

{

1 2 4

,

,

}

is a proper subset of

{

1 2 3 4 5

,

,

,

,

}

satisfying satisfying (i1),

- (i1), (i2) and (i3), and Q := Q∪{ U 1 } . Step 2. /lscript Q ( U 1 ) = 2, k := 3 and R := Q (the lattice R as represented in Fig.11). Step 3. Q := R , t := 3, U 2 = { 1 5 , } is a proper subset of { 1 2 3 4 5 , , , , }
- (i2) and (i3), and Q := Q∪{ U 2 } . Step 4. /lscript Q ( U 2 ) = 2, k := 3 and R := Q (the lattice R as represented in Fig.12). Step 5. Q := R , t := 3, U 3 = { 2 5 , } is a proper subset of { 1 2 3 4 5 , , , , } satisfying (i1),
- (i2) and (i3), and Q := Q∪{ U 3 } .

Step 6.

/lscript

Q

(

U

3

) = 2,

k

:= 3 and

R

:=

Q

(the lattice

R

as represented in Fig.13).

Step 7.

Q

:=

R

,

t

:= 3,

U

4

=

{

4 5

,

}

is a proper subset of

{

1 2 3 4 5

,

,

,

,

}

satisfying (i1),

- (i2) and (i3), and Q := Q∪{ U 4 } . Step 8. /lscript Q ( U 4 ) = 2, k := 3 and R := Q (the lattice R as represented in Fig.14).

Step 9. Q := R , t := 3 and { 1 2 3 4 5 , , , , } has no proper subset satisfying (i1), (i2)

and (i3), k = 4 ≥ 4.

Step 10. Stop.

Fig.11 The lattice R .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-0ab5797f-e4de-4235-9b87-cb3829ed5776.jpg)

Fig.12 The lattice R .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-b19df490-1f7a-4b13-8995-74a154fb65aa.jpg)

Fig.13 The lattice R .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-9ac0bafb-c2c5-4ab1-9b26-7123c175eae3.jpg)

Fig.14 The lattice R .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-007e9da4-b726-48b5-a2e7-bed6d12bac90.jpg)

Therefore, the output Q in Algorithm 3.1 is the R as represented in Fig.14. One can check that Q ∈ S , Q is a finite geometric lattice and L ↪ → Q ≺ .

Definition 4.1 Let L 1 and L 2 be two finite atomistic lattices with L 1 ⊆ L 2 . If L 1 satisfies: for any p ∈ L 1 ,

- (e1) A L 1 ( p ) = A L 2 ( p ) ;
- (e2) /lscript L 1 ( p ) = /lscript L 2 ( p ) ; and
- (e3) [0 , p ] L 1 = [0 , p ] L 2 when /lscript L 1 ( p ) ≤ k ,

then we say that L 1 is a k order normal subset lattice of L 2 .

Lemma 4.5 Let ( Q ⊆ , ) be a finite geometric lattice with L ↪ → ≺ Q and /lscript ( L ) = /lscript ( Q ) . Then Q ∈ S .

Proof. Let /lscript ( Q ) = m . As Q is a finite geometric lattice, Q satisfies condition ( M ). Thus we only need to prove that Q is an output of Algorithm 3.1. Since L ↪ → Q ≺ , there exists a lattice T ⊆ Q such that L ∼ T = ↪ → Q ≺ . Hence there exists a lattice P ∈ E ( L ) such that S P = T ∪ A ( Q ). Thus there exists a lattice T P L such that T P L ⊆ S P and L ∼ T = P L ↪ → S ≺ P by formula (1).

Because Q is geometric, the following four statements hold.

- C1. For every M ∈ Q , [ ∅ , M ] Q is a geometric lattice.
- C2. If M,N ∈ Q , then ( M ∩ N ) Q = M ∩ N .

/negationslash

- C3. If M,N ∈ ϕ Q ( k ) and M = N , then M /notsubseteql N and N /notsubseteql M .

/negationslash

C4. If σ ∈ φ Q ( k ), M ∈ ϕ Q ( k ) and ∨ Q σ = M , then σ / ∈ I Q ( M ) and ⋃ σ /notsubseteql M .

The rest of the proof will be completed in three steps.

(I). Let R 1 = S P . Then by Definition 4.1, R 1 is a 2 order normal subset lattice of Q . Suppose that X ∈ R 1 and /lscript R 1 ( X ) = 3. Let U ∈ Q - R 1 , U /subsetnoteql X and /lscript Q ( U ) = 2. If V ∈ ϕ R 1 (2), then ( U ∩ V ) R 1 = ( U ∩ V ) Q by (e3). It follows from C2 that

$$\overline { ( U \cap V ) _ { \mathcal { R } _ { 1 } } } \subseteq U.$$

Obviously, by C4 and (e2) and (e3) in Definition 4.1,

$$\bigcup \sigma \not \subseteq U$$

for any σ ∈ φ R 1 (2). Moreover, by (e2) in Definition 4.1 and C3, we have

$$U \not \subseteq V$$

/negationslash for every V ∈ ϕ R 1 (2) since U = V . Thus, by formulas (7), (8) and (9), we know that U satisfies (i1), (i2) and (i3) in Algorithm 3.1. Therefore, R ∪ { 1 U } is an atomistic lattice by the proof of Lemma 4.1. Clearly, R ∪{ 1 U } is a 2 order normal subset lattice of Q .

Suppose that E ∈ R ∪{ 1 U } and /lscript R ∪{ 1 U } ( E ) = 3. Let U 1 ∈ Q- R ∪{ ( 1 U } ), U 1 /subsetnoteql E and /lscript Q ( U 1 ) = 2. Similar to the proof of the preceding paragraph, we can prove that R ∪{ 1 U }∪{ U 1 } is an atomistic lattice which is a 2 order normal subset lattice of Q since R ∪{ 1 U } is a 2 order normal subset lattice of Q .

Repeating the process as above, we can obtain an atomistic lattice

$$\mathcal { R } _ { 2 } = \mathcal { R } _ { 1 } \cup \bigcup \{ [ \emptyset, M ] _ { \mathcal { Q } } \colon \ell _ { \mathcal { R } _ { 1 } } ( M ) = 3 \}.$$

Obviously,

$$\mathcal { R } _ { 2 } = \mathcal { R } _ { 1 } \cup \bigcup \{ [ \emptyset, M ] _ { \mathcal { Q } } \colon \ell _ { \mathcal { Q } } ( M ) = 3, M \in \mathcal { R } _ { 1 } \}$$

by (e2) in Definition 4.1. Therefore, R 2 is a 3 order normal subset lattice of Q , and for any F ∈ R 2 with /lscript R 2 ( F ) ≤ 3, F has no proper subset N satisfying (i1), (i2) and (i3) in Algorithm 3.1.

(II). Suppose that X ∈ R 2 and /lscript R 2 ( X ) = 4. Let U ∈ Q-R 2 , U /subsetnoteql X and /lscript Q ( U ) = 3. There are two cases as below.

Case 1. If there exists E ∈ ϕ R 2 (2) such that E /subsetnoteql U . Similar to the proof of formulas (7), (8) and (9), we can verify that U satisfies (i1), (i2) and (i3) in Algorithm 3.1. Therefore, R ∪ { 2 U } is an atomistic lattice by the proof of Lemma 4.1. Clearly, R ∪ { 2 U } is a 2 order normal subset lattice of Q . Thus, similar to the proof of (10), we can obtain an atomistic lattice R ∪ ∅ 2 [ , U ] Q that is a 3 order normal subset lattice of Q .

Case 2. If there is no element E ∈ ϕ R 2 (2) such that E /subsetnoteql U , then there exists U 1 ∈ Q - R 2 such that U 1 /subsetnoteql U and /lscript Q ( U 1 ) = 2 since Q is geometric. Thus we have that the following three results.

- (a1) By (e2), (e3), C1 and C2, ( U 1 ∩ V ) R 2 ⊆ U 1 for any V ∈ ϕ R 2 (3);
- (a2) By (e2) and C4, ⋃ σ /notsubseteql U 1 for any σ ∈ φ R 2 (2);
- (a3) By (e2) and C3, U 1 /notsubseteql V for any V ∈ ϕ R 2 (2).

Therefore, U 1 satisfies (j1), (j2) and (j3) in Algorithm 3.1. This follows that R ∪{ 2 U, U 1 } is an atomistic lattice which is a 2 order normal subset lattice of S . Analogous to the proof of Case 1, we can obtain an atomistic lattice R ∪ ∅ 2 [ , U ] Q which is a 3 order normal subset lattice of Q .

From Cases 1 and 2, we always obtain an atomistic lattice R ∪ ∅ 2 [ , U ] Q which is a 3 order normal subset lattice of Q .

Continuing as above, we can obtain an atomistic lattice

$$\mathcal { R } _ { 3 } = \mathcal { R } _ { 2 } \cup \bigcup \{ [ \emptyset, M ] _ { \mathcal { Q } } \colon \ell _ { \mathcal { R } _ { 2 } } ( M ) = 4 \}.$$

Obviously,

$$\mathcal { R } _ { 3 } = \mathcal { R } _ { 2 } \cup \bigcup \{ [ \emptyset, M ] _ { \mathcal { Q } } \colon \ell _ { \mathcal { Q } } ( M ) = 4, M \in \mathcal { R } _ { 2 } \}$$

by (e2) in Definition 4.1. Therefore, R 3 is a 4 order normal subset lattice of Q , and for any G ∈ R 3 with /lscript R 3 ( G ) ≤ 4 there is no element H /subsetnoteql G such that H satisfies (i1), (i2) and (i3) in Algorithm 3.1.

- (III). Repeating the preceding proof, we finally obtain an atomistic lattice

$$\mathcal { R } _ { m - 1 } = \mathcal { R } _ { m - 2 } \cup \bigcup \{ [ \emptyset, M ] _ { \mathcal { Q } } \colon \ell _ { \mathcal { Q } } ( M ) = m, M \in \mathcal { R } _ { m - 2 } \},$$

and for any W ∈ R m -1 with /lscript R m -1 ( W ) ≤ m there is no element Z /subsetnoteql W such that Z satisfies (i1), (i2) and (i3) in Algorithm 3.1. Consequently, by /lscript Q ( M ) = m , we know that [ ∅ , M ] Q = Q = R m -1 , and Q is an output of Algorithm 3.1, completing the proof.

Notable that Lemmas 4.1, 4.3, 4.4 and 4.5 deduce that we can construct all the finite extending cover-preserving geometric lattices of L with the same length by Algorithm 3.1. However, applying the method suggested by G. Cz´ edli and E. T. Schmidt in [4] to the L as depicted in Fig.10, one can only obtain the finite extending cover-preserving geometric lattice as is shown by Fig.15.

Fig.15 The geometric lattice G .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-b4959fb0-0e1e-40d5-b01c-d0c0c2c53d1d.jpg)

## 5 The best geometric lattices

In this section, we shall construct all the best extending cover-preserving geometric lattices of L . Denote S k = {S ∈ S : | A ( S | ) = k } for any integer k &gt; 0. Then we have the following Lemma.

Lemma 5.1 Let K ∈ S k with k &gt; | J L ( ) | . Then there exists an element H ∈ S k -1 such that |H| &lt; |K| .

Proof. Since K ∈ S k , L ↪ → K ≺ by Lemma 4.3. Then there exists a lattice T ⊆ K such that L ∼ T = ↪ → K ≺ . Hence there exists a lattice Q ∈ E ( L ) such that S Q = T ∪ A ( K ). This follows from formula (1) that there exists a lattice T Q L such that T Q L ⊆ S Q and L ∼ T = Q L ↪ → S ≺ Q . By k &gt; | J L ( ) , | we know that there exists an element r ∈ ∆ ( Q L ) such that Q -{ } ∈ r E ( L ). Set P = Q -{ } r and R = { } r . Then L ∼ T = P L ↪ → S ≺ P and

$$\mathcal { T } _ { L } ^ { P } = \{ F - R \, \colon F \in \mathcal { T } _ { L } ^ { Q } \}$$

by Lemma 3.2, and there exists a set σ ∈ I S Q ( X ) such that ⋃ σ ⊆ X -R for any X ∈ T Q L . Hence, as T Q L ⊆ S Q , there exists a set σ ∈ I K ( X ) such that

$$\bigcup \sigma \subseteq X - R$$

for any X ∈ T Q L by Lemma 4.2. Note that K is a finite geometric lattice. Then by Lemma 2.4, we have that

$$\overline { E _ { \mathcal { K } } } = \overline { ( E - R ) _ { \mathcal { K } } } = \bigvee _ { \mathcal { K } } \sigma$$

whenever E ∈ T Q L , σ ∈ I K ( E ) and ⋃ σ ⊆ E -R .

Set

$$\mathcal { H } = \{ W - R \, \colon W \in \mathcal { K }, \overline { ( W - R ) _ { \mathcal { K } } } = \overline { W _ { \mathcal { K } } } \}.$$

Then, by formulas (11), (13) and (14), we know that

$$\mathcal { T } _ { L } ^ { P } \subseteq \mathcal { H }.$$

Now, we shall show that L ↪ → H ≺ and H is a geometric lattice. The proof is made in three steps.

A. H is a finite atomistic lattice.

From (14), it is clear that H is a finite atomistic partially ordered set. Thus, it suffices to show that H is a lattice.

Suppose M,N ∈ H . Obviously,

$$R \not \subseteq M \text{ and } R \not \subseteq N.$$

If M ∦ N , then M ∧ H N = M ∩ N ∈ H . Now, suppose that M ‖ N and denote D M,N = { G ∈ H : G ⊆ M ∩ N } . There are three cases.

Case i. If M,N ∈ K , then M N ∩ ∈ K . Clearly, ( M ∩ N -R ) K = ( M ∩ N ) K = M N ∩ by (16). From (14), M ∩ N ∈ H . Therefore, M ∧ H N = M ∩ N .

Case j. If M ∈ K and N / ∈ K , then, clearly, N ∪ R ∈ K since N ∈ H . Thus M ∩ ( N ∪ R ) ∈ K . By formula (16), M ∩ ( N ∪ R ) = M ∩ N = M ∩ N -R , so that

[ M ∩ ( N ∪ R )] K = ( M ∩ N ) K = ( M ∩ N -R ) K . Hence, M ∩ N ∈ H by (14). Therefore, M ∧ H N = M ∩ N .

Case k. If M,N / ∈ K , then similar to the proof of Case j, we have M ∪ R, N ∪ R ∈ K . Then ( M ∩ N ) ∪ R ∈ K . There are two subcases.

Subcase 1 . If [( ◦ M ∩ N ) ∪ R ] K = ( M ∩ N ) K , then by (14), M ∩ N ∈ H which is the maximum element of D M,N . Thus, M ∧ H N = M ∩ N .

/negationslash

Subcase 2 . If[( ◦ M ∩ N ) ∪ R ] K = ( M ∩ N ) K , then ( M ∩ N ) K /subsetnoteql [( M ∩ N ) ∪ R ] K , and [( M ∩ N ) ∪ R ] K = ( M ∩ N ) ∪ R since ( M ∩ N ) ∪ R ∈ K . Thus

$$M \cap N \subseteq \overline { ( M \cap N ) _ { \mathcal { K } } } \subsetneq \overline { [ ( M \cap N ) \cup R ] _ { \mathcal { K } } } = ( M \cap N ) \cup R,$$

which means that M ∩ N = ( M ∩ N ) K ∈ K . Then, by (16), we know that M ∩ N = ( M ∩ N ) K = [( M ∩ N ) -R ] K . Therefore, M ∩ N ∈ H by (14), it follows that M ∧ H N = M ∩ N .

Subcases 1 ◦ and 2 ◦ imply that M ∧ N = M ∩ N if M,N / ∈ K .

H Therefore, from Cases i, j and k, H is a finite atomistic lattice.

B. H is a finite geometric lattice.

Inasmuch as we possess A it suffices to show that H is a semimodular lattice. Let M,N ∈ H and M,N /follows H M ∩ N . Obviously, M ‖ N . Next, we shall prove that M ∨ H N /follows H M,N . There are three cases as follows.

Case a. If M,N ∈ K , then M ∩ N ∈ K . By formulas (14) and (16), [ ∅ , M ] H = [ ∅ , M ] K and [ ∅ , N ] H = [ ∅ , N ] K . Thus M,N /follows K M N ∩ , which together with K is a geometric lattice yields that M ∨ K N /follows K M,N .

We claim that

$$\overline { ( M \vee \kappa \, N ) \kappa } = \overline { ( M \vee \kappa \, N - R ) \kappa }.$$

Otherwise, ( M ∨ K N -R ) K /subsetnoteql ( M ∨ K N ) K . It is clear that M /subsetnoteql M N ∪ ⊆ ( M ∨ K N -R ) K by (16). Note that ( M ∨ K N ) K = M ∨ K N since M ∨ K N ∈ K . Thus

$$M \subsetneq \overline { ( M \vee _ { \mathcal { K } } N - R ) _ { \mathcal { K } } } \subsetneq \overline { ( M \vee _ { \mathcal { K } } N ) _ { \mathcal { K } } } = M \vee _ { \mathcal { K } } N,$$

contrary to the fact that M ∨ K N /follows K M . Therefore, ( M ∨ K N ) K = ( M ∨ K N -R ) K , and then by (14), M ∨ K N -R ∈ H . Hence, the condition M ∨ K N /follows K M,N deduces that

$$M \vee _ { \mathcal { K } } N - R = M \vee _ { \mathcal { H } } N \succ _ { \mathcal { H } } M, N.$$

Case b. If M,N / ∈ K , then M ∪ R, N ∪ R, ( M ∩ N ) ∪ R ∈ K since M,N,M ∩ N ∈ H .

Thus

$$M \cup R = \overline { ( M \cup R ) _ { \mathcal { K } } } = \overline { M _ { \mathcal { K } } }, N \cup R = \overline { ( N \cup R ) _ { \mathcal { K } } } = \overline { N _ { \mathcal { K } } }$$

$$( M \cap N ) \cup R = \overline { [ ( M \cap N ) \cup R ] _ { \mathcal { K } } } = \overline { ( M \cap N ) _ { \mathcal { K } } }$$

and

by (14).

On the other hand, we claim that M ∪ R /follows K ( M ∩ N ) ∪ R . Otherwise, there exists an atom I ⊆ M -N such that M R ∪ /supersetnoteql [( M ∩ N ) ∪ R ∪ I ] K /supersetnoteql ( M N ∩ ) ∪ R . Then by formula (18), [( M ∩ N ) ∪ R ∪ I ] K = [( M ∩ N ) ∪ I ] K , which means that [( M ∩ N ) ∪ I ] K -R ∈ H . Thus M /supersetnoteql [( M ∩ N ) ∪ I ] K -R /supersetnoteql M ∩ N , contrary to the fact that M /follows H M ∩ N . Therefore,

$$M \cup R \succ _ { \mathcal { K } } ( M \cap N ) \cup R.$$

Similarly, we have N ∪ R /follows K ( M ∩ N ) ∪ R . Thus ( M ∪ R ) ∨ K ( N ∪ R ) /follows K M ∪ R, N ∪ R , and which means that

$$\overline { ( M \cup N \cup R ) _ { \mathcal { K } } } = ( M \cup R ) \vee _ { \mathcal { K } } ( N \cup R ) \succ _ { \mathcal { K } } M \cup R, N \cup R.$$

We claim that [( M ∪ N ∪ R ) K K ] = [( M ∪ N ∪ R ) K -R ] K . Otherwise,

$$\overline { ( M \cup N \cup R ) \kappa } \supsetneq [ \overline { ( M \cup N \cup R ) \kappa } - R ] \kappa \supseteq \overline { ( M \cup N ) \kappa }$$

since [( M ∪ N ∪ R ) K K ] = ( M ∪ N ∪ R ) K and ( M ∪ N ∪ R ) K -R ⊇ M ∪ N . However, ( M ∪ N ) K ⊇ M K = M ∪ R by (17). Hence ( M ∪ N ) K = ( M ∪ N ∪ R ) K , a contradiction. Therefore, [( M ∪ N ∪ R ) K K ] = [( M ∪ N ∪ R ) K -R ] K . This follows that ( M ∪ N ∪ R ) K -R ∈ H by (14). Further, by formula (20),

$$\overline { ( M \cup N \cup R ) _ { \mathcal { K } } } - R = \overline { ( M \cup N ) _ { \mathcal { K } } } - R = M \vee _ { \mathcal { H } } N \succ _ { \mathcal { H } } M, N.$$

Case c. If M / ∈ K and N ∈ K , or M ∈ K and N / ∈ K , say, M / ∈ K and N ∈ K , then M ∪ R, N, M ∩ N ∈ K since M,N,M ∩ N ∈ H . Hence,

$$M \cup R = \overline { ( M \cup R ) _ { \mathcal { K } } } = \overline { M _ { \mathcal { K } } }$$

by (14).

Similar to the proof of formula (19), we have that ( M ∪ R ) /follows K M ∩ N . On the other hand, similar to the proof of Case a, we know that N /follows K M ∩ N . Thus ( M ∪ R ) ∨ K N /follows K M ∪ R, N , and which means that

$$\overline { ( M \cup N \cup R ) _ { \mathcal { K } } } = ( M \cup R ) \vee _ { \mathcal { K } } N \succ _ { \mathcal { K } } M \cup R, N.$$

Analogous to the proof of Case b, we know that

$$\overline { ( M \cup N \cup R ) _ { \mathcal { K } } } - R = \overline { ( M \cup N ) _ { \mathcal { K } } } - R = M \vee _ { \mathcal { H } } N \succ _ { \mathcal { H } } M, N$$

by formulas (14), (21) and (22).

In summary, H is a finite geometric lattice.

$$\mathbb { C }. \, \mathcal { T } _ { L } ^ { P } \hookrightarrow \prec \mathcal { H }.$$

Let M,N ∈ T P L . Then there are two elements E,F ∈ T Q L ⊆ S Q such that M = F -R and N = E -R by (11). Thus by L ∼ T = P L ∼ T = Q L and (11),

$$M \vee _ { \mathcal { T } _ { L } ^ { P } } N = ( F \vee _ { \mathcal { T } _ { L } ^ { Q } } E ) - R.$$

As F, E ∈ T Q L , we have that

$$F \vee _ { \mathcal { K } } E = \overline { ( M \cup N ) _ { \mathcal { K } } } = [ \overline { ( M \cup N ) _ { \mathcal { K } } } - R ] _ { \mathcal { K } }$$

by formula (12) and (13). Hence, by formulas (14),

$$M \vee _ { \mathcal { H } } N = \overline { ( M \cup N ) _ { \mathcal { K } } } - R = F \vee _ { \mathcal { K } } E - R.$$

Clearly, by formula (5), we know that

$$F \vee _ { \mathcal { T } _ { L } ^ { Q } } E = F \vee _ { \mathcal { K } } E,$$

which together with formulas (23) and (24) clearly leads to M ∨ H N = M ∨ T P L N . Therefore, T P L ↪ → H ∨ . On the other hand, by formula (11), we know that M ∧ T P L N = M ∩ N for any M,N ∈ T P L . Thus T P L ↪ → H ∧ by the proof of A. Hence, T P L ↪ →H .

Obviously, L ∼ T = P L ∼ T = Q L together with (14) means that /lscript ( T P L ) = /lscript ( H ). Therefore, T P L ↪ → H ≺ since T P L ↪ →H , completing the proof of C.

Finally, from B, C and Lemma 4.5, we know that H ∈ S k -1 and |H| &lt; |K| . This completes the proof.

Let G be a finite geometric lattice. It is clear that if L ↪ → ≺ G , then there exists a sublattice [ x, y ] of G with /lscript ([ x, y ]) = /lscript ( L ) such that L ↪ → ≺ [ x, y ]. Clearly, [ x, y ] is also a geometric lattice. Therefore, by Lemmas 4.1, 4.3, 4.4, 4.5 and 5.1, we have the following theorem.

Theorem 5.1 Every best extending cover-preserving geometric lattice of L is the best one in S | J L ( ) | .

Example 5.1 Consider the lattice L in Example 4.1 again. If U = { 1 2 4 5 , , , } in Step 1 of Algorithm 3.1. Then Q = S P ∪{ U } is the output lattice of Algorithm 3.1 (the lattice Q as represented in Fig.16).

Fig.16 The lattice Q .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00749v2-figure-3941d27d-ceaf-449a-b062-633480799214.jpg)

Obviously, Q ∈ S 5 . Further, we know that Q is the unique best extending coverpreserving geometric lattice of L in the sense of isomorphism.

## 6 Conclusions

In this paper, we proposed an algorithm to calculate all the best extending coverpreserving geometric lattice G of a given semimodular lattice L and proved that | A G ( ) | = | J L ( ) | and /lscript ( G ) = /lscript ( L ). It is worth pointing out that every different U (resp. W ) in Algorithm 3.1 leads to a different output, and the computational complexity of Algorithm 3.1 is likely to grow rapidly as | J L ( ) | and /lscript ( L ) grow.

## Data availability statements

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

## References

- [1] G. Birkhoff, Lattice Theory, vol.XXV, 3rd ed., American Mathematical Society Colloquium Publications, Providence, RI, 1973.
- [2] J. R. B¨ uchi, Representation of complete lattices by sets, Portugaliae mathematica 11 (1952) 151-167.

- [3] P. Crawley, R. P. Dilworth, Algebraic Theory of Lattices, Prentice Hall, Englewood Cliffs, NJ, 1973.
- [4] G. Cz´ edli, E. T. Schmidt, A cover-preserving embedding of semimodular lattices into geometric lattices, Advances in Mathematics 225 (2010) 2455-2463.
- [5] G. Gr¨ atzer, E. W. Kiss, A construction of semimordular lattices, Order 2 (1986) 351-365.
- [6] G. Gr¨ atzer, F. Wehrung, Lattice Theory: Special Topics and Applications, Birkh¨ser a Verlag, Basel, 2014.
- [7] Peng He, Xue-ping Wang, A characterization of a semimodular lattice, Studia Logica 106 (2018) 691-698.
- [8] P. Pudl´ ak, J. T¨ uma, Every finite lattice can be embedded in a partition lattice, Algebra Universalis 10 (1980) 74-95.
- [9] M. Stern, Semimodular lattice: theory and applications, Cambridge University Press, 1999.
Peng He Xue-ping Wang
The best extending cover-preserving geometric lattices of semimodular lattices
In 2010, G\'{a}bor Cz\'{e}dli and E. Tam\'{a}s Schmidt mentioned that the
best cover-preserving embedding of a given semimodular lattice is not known yet
[A cover-preserving embedding of semimodular lattices into geometric lattices,
Advances in Mathematics 225 (2010) 2455-2463]. That is to say: What are the
geometric lattices $G$ such that a given finite semimodular lattice $L$ has a
cover-preserving embedding into $G$ with the smallest $|G|$? In this paper, we
propose an algorithm to calculate all the best extending cover-preserving
geometric lattices $G$ of a given semimodular lattice $L$ and prove that the
length and the number of atoms of every best extending cover-preserving
geometric lattice $G$ equal the length of $L$ and the number of non-zero
join-irreducible elements of $L$, respectively. Therefore, we comprehend the
best cover-preserving embedding of a given semimodular lattice.