Congrunce lattices of rectangular lattices 1

Abstract

Let D be a finite distributive lattice with n join-irreducible elements. It is well-known that D can be represented as the congruence lattice of a rectangular lattice L which is a special planer semimodular lattice. In this paper, we shall give a better upper bound for the size of L by a function of n, improving a 2009 result of G. Grätzer and E. Knapp.

Keywords

Distributive lattice Congruence lattice

1 Introduction

A classical result of R. P. Dilworth states that a finite distributive lattice D can be represented as the congruence lattice of a finite lattice L. There are many papers strengthening this result by requiring that the lattice L representing D have special properties. The lattice L constructed by Dilworth is atomistic. A sectionally complemented lattice L is constructed in G. Grätzer and E. T. Schmidt [12], while a planar lattice is constructed in G. Grätzer and H. Lakser [8].

For every result representing a finite distributive lattice D with n join-irreducible elements as the congruence lattice of a finite lattice L in some class K of lattices, the natural question arises: How small can we make L as a function of n and K ?

For the first result, K is the class of all lattices, that is, there is no restriction on L. The first proof of this representation theorem constructs a lattice of size O (2²ⁿ), see G. Grätzer and E. T. Schmidt [12]. The size O (2²ⁿ) was improved to O (n³) by G. Grätzer and H. Lakser [7] and to O (n²) by G. Grätzer, H. Lakser and E. T. Schmidt [9]. Finally, it was proved in G. Grätzer, I. Rival, and N. Zaguia [11] that O (n²) is best possible.

G. Grätzer, H. Lakser and E. T. Schmidt [10] stated that for a class of semimodular lattices, they can construct a lattice of size O (n³) =3n³ + 2n² - 7n + 4. In fact, they proved that this size can be achieved with a finite planar semimodular lattice L. This result was improved by G. Grätzer and E. Knapp in [4, 5]. They constructed L as a rectangular lattice and improved the size to $\frac{2}{3} n^{3} + 2 n^{2} + \frac{4}{3} n + 1$ . G. Grätzer and E. Knapp [6] proved the converse for rectangular lattices: O (n³) is the best possible.

Let P be a partially ordered set with n elements. We say that O = {p₁, ⋯ , p_n} is an ascending order of P, if p_i < _Pp_j implies that i < j (In [5], G. Grätzer and E. Knapp used the terminology of a finite order instead of an ascending order). Let △ (P) be the sets of all ascending orders of P. Clearly, | △ (P) |≥1. Particularly, | △ (P) |=1 if and only if P is a chain. Thus, a partially ordered set has more than one ascending order generally. For example, both O₁ = {a, b, d, c} and O₂ = {c, a, b, d} are the ascending orders of Fig. 1.

Fig. 1

A partially ordered set P.

In [5], G. Grätzer and E. Knapp showed that there exists a rectangular lattice L such that Con_JL ≅ P for any finite partially ordered set P with

$\begin{matrix} | L | = 2 [(n + 1) (m_{n} + 1) + n (m_{n - 1} + 1) \\ + \dots + 2 (m_{1} + 1)] + 1 \end{matrix}$ (1) when O = {p₁, p₂, ⋯ , p_n} is an ascending order of P, where m_i is the number of elements covered by p_i in P. Using formula (5), G. Grätzer and E. Knapp proved the following three results (see also [2, 13]):

Theorem 1.1. Let D be a finite distributive lattice with n join-irreducible elements. Then D can be represented as the congruence lattice of a rectangular lattice L satisfying $| L | \leq \frac{2}{3} n^{3} + 2 n^{2} + \frac{4}{3} n + 1$ .

Theorem 1.2. Let D be a finite distributive lattice with n join-irreducible elements. Then D can be represented as the congruence lattice of a planar semimodular lattice L of $| L | \leq \frac{1}{3} n^{3} + 2 n^{2} + \frac{5}{3} n + 1$ .

Theorem 1.3. Let P be a finite partially ordered set of n elements. Then P can be represented as the partially ordered set of join-irreducible congruences of a rectangular lattice L of $| L | \leq \frac{2}{3} n^{3} + 2 n^{2} + \frac{4}{3} n + 1$ .

G. Grätzer [5, 13] raised an interesting open problem: how much smaller one can make the coefficients of n³ in both Theorems 1.1 and 1.2 ? In this paper, we shall give a response to the problem. For convenience, we denote N_P (O) = |L| in formula (5).

Unless otherwise stated, we use the standard terminology and the notation of [13].

2 Finite partially ordered sets

In this section, we shall introduce some definitions and primary results of a finite partially ordered set.

Definition 2.1. Let P be a finite partially ordered set. Then we denote that $S_{P} = {l \subseteq P : l is a maximal chain} .$ We define max{|l| : l ∈ S_P} is the rank of P, in symbols r (P). Again, we set that $T_{P} = {l \in S_{P} : | l | = r (P)} .$

It is easy to see that $\begin{matrix} | {a : 0_{l_{1}} \leq_{P} a \leq_{P} q and a \in l_{1}} | \\ = | {a : 0_{l_{2}} \leq_{P} a \leq_{P} q and a \in l_{2}} | \end{matrix}$ for l₁, l₂ ∈ T_P with q ∈ l₁ ∩ l₂.

Definition 2.2. Let P be a finite partially ordered set and q ∈ P. We denote that $r (q) = {\begin{matrix} | {a : 0_{l} \leq_{P} a \leq_{P} q and a \in l} |, & if q \in l \in T_{P}, \\ 0, & otherwise . \end{matrix}$ We say that r (q) is the rank of q.

Further, we define $X_{i}^{P} = {p \in P : r (p) = i}$ for any 0 ≤ i ≤ r (P).

Obviously, the following properties are established by Definitions 2.1 and 2.2.

T_P≠ ∅ and r (P) ≥1,

$X_{i}^{P} \cap X_{j}^{P} = \emptyset$ for any i ≠ j,

$⋃_{i = 0}^{r (P)} X_{i}^{P} = P$ .

For example, Fig. 2 is a partially ordered set. First, it is easy to see that r (P) =4 and l : a₁ ≺ _Pa₄ ≺_Pa₇ ≺ _Pa₉ is an element of T_P. Secondly, we know that $X_{1}^{P} = {a_{1}}, X_{2}^{P} = {a_{4}}, X_{3}^{P} = {a_{7}},$ $X_{4}^{P} = {a_{9}}$ and $X_{0}^{P} = {a_{2}, a_{3}, a_{5}, a_{6}, a_{8}}$ . Finally, we can verify that (1), (2) and (3) are satisfied.

Fig. 2

A finite partially ordered set P.

Definition 2.3. We say that a finite partially ordered set P is closed, if for any $p \in X_{0}^{P}$ , the following two conditions are satisfied.

If p is a maximal element of P, then for any $q \in X_{r (P)}^{P}$ , there exists an element u < _Pp such that u ≺ _Pq.

If p is a minimal element of P, then for any $q \in X_{1}^{P}$ , there exists an element v > _Pp such that v ≻ _Pq.

Obviously, every finite lattice and the partially ordered set $\bar{S}$ in Fig. 3 are closed partially ordered sets. However the partially ordered sets in both Figs. 1 and 2 are not closed.

Fig. 3

Two partially ordered sets S and $\bar{S}$ .

Lemma 2.1. Let P be a finite partially ordered set. Then:

(a) In the case of r (P) =1, $\bar{P} = P$ is a closed partially ordered set.

(b) In the case of r (P) =2, we connect p to q for any $p \in X_{0}^{P}, q \in X_{2}^{P}$ such that p ≺ q. This way, we obtain a new diagram $\bar{P}$ which is a closed partially ordered set.

(c) In the case of r (P) ≥3, if $p \in X_{0}^{P}$ , p is a maximal element of P and $q \in X_{r (P)}^{P}$ satisfying q ⊁ _Ph for any h < _Pp, then we connect p to q such that p ≺ q. This way, we obtain a new diagram $\hat{P}$ which is a partially ordered set. Further, if $u \in X_{0}^{\hat{P}}$ , u is a minimal element of $\hat{P}$ and $v \in X_{1}^{\hat{P}}$ satisfying $v ⊀_{\hat{P}} f$ for any $f >_{\hat{P}} u$ , then we connect v to u such that v ≺ u. This way, we obtain a new diagram $\bar{P}$ which is a closed partially ordered set.

Proof. (a) follows from Definition 2.3. From the construction of $\bar{P}$ of (b), it follows that $\bar{P}$ is a partially ordered set and $X_{0}^{\bar{P}} = \emptyset$ . Thus $\bar{P}$ is a closed partially ordered set by Definition 2.3. It remains, therefore, to show (c).

First, we claim that $\hat{P}$ is a partially ordered set. Assume that $\hat{P}$ is not a partially ordered set. Then there exist three elements x₁, x₂ and x₃ in $\hat{P}$ such that $x_{1} ≻_{\hat{P}} x_{2} >_{\hat{P}} x_{3}$ and $x_{1} ≻_{\hat{P}} x_{3}$ . From the construction of $\hat{P}$ , we conclude that $x_{1} \in X_{r (P)}^{P}$ , x₁ ≻ _Px₃, x₂ > _Px₃ and x₁ ⊁ _Px₂ since P is a partially ordered set. From this it follows that $x_{1} ⊁_{\hat{P}} x_{2}$ by the construction of $\hat{P}$ , a contradiction. Hence, $\hat{P}$ is a partially ordered set. Similarly, we can prove that $\bar{P}$ is a partially ordered set. By Definition 2.3 and the construction of $\bar{P}$ , it is clear that $\bar{P}$ is a closed partially ordered set.□

In Fig. 3, it is clear that the closed partially ordered set $\bar{S}$ is obtained from the partially ordered set S by Lemma 2.1.

Lemma 2.2. Let P be a finite partially ordered set, and let $\bar{P}$ be obtained by Lemma 2.1. If $O \in △ (\bar{P})$ then O ∈ △ (P) and $N_{\bar{P}} (O) \geq N_{P} (O)$ .

Proof. Assume that $O \in △ (\bar{P})$ but O ∉ △ (P). Let O = {p₁, ⋯ , p_n}. Then we observe that there exist two integers i, j with i < j such that p_i > _Pp_j. It follows that $p_{i} >_{\bar{P}} p_{j}$ by Lemma 2.1, and which implies that $O \notin △ (\bar{P})$ , an impossibility. Therefore, O ∈ △ (P).

Set $\bar{m_{i}}$ and m_i be the numbers of elements covered by p_i in $\bar{P}$ and P, respectively. It is clear that $\bar{m_{i}} \geq m_{i}$ from Lemma 2.1. Thus $N_{\bar{P}} (O) \geq N_{P} (O)$ by formula (5).□

3 Layered partially ordered sets

In this section, we shall discuss a class of closed finite partially ordered sets which are called layered partially ordered sets.

Definition 3.1. Let P be a finite closed partially ordered set. We say that P is layered if P satisfies the following four conditions:

(A) If $p, q \notin X_{0}^{P}$ , then p ≻ _Pq implies $q \in X_{j}^{P}$ and $p \in X_{j + 1}^{P}$ for an exact integer 1 ≤ j ≤ r (P) -1.

(B) For $p \in X_{0}^{P}$ , p is a maximal element of $X_{0}^{P}$ if and only if p has upper covers in $P - X_{0}^{P}$ . Further, there exists an exact integer 1 ≤ i ≤ r (P) such that $q \in X_{i}^{P}$ for any q ≻ _Pp.

(C) For $p \in X_{0}^{P}$ , p is a minimal element of $X_{0}^{P}$ if and only if p has lower covers in $P - X_{0}^{P}$ . Further, there exists an exact integer 1 ≤ i ≤ r (P) such that $q \in X_{i}^{P}$ for any p ≻ _Pq.

(D) Each element $p \in X_{0}^{P}$ is a doubly-irreducible (i.e., p is both join-irreducible and meet-irreducible) element in $X_{0}^{P}$ .

A finite graded partially ordered set is layered and all finite semimodular lattices are also layered. It is easy to see that the partially ordered set $\bar{S}$ in Fig. 3 is not layered.

Definition 3.2. Let P be a finite layered partially ordered set. For any r (P) ≥ i ≥ 2, if $p \in X_{i}^{P}$ and $q \in X_{i - 1}^{P}$ imply p ≻ _Pq, then we say that P is a complete layered partially ordered set.

It is clear that the partially ordered set K_{n₁,n₂,⋯,n_m} is an example of complete layered partially ordered set (the concept of K_{n₁,n₂,⋯,n_m} is from [1]). Figure 4 is K_2,2,2.

Fig. 4

K_2,2,2.

Lemma 3.1. Let P be a finite layered partially ordered set. For any r (P) ≥ i ≥ 2, if $p \in X_{i}^{P}$ and $q \in X_{i - 1}^{P}$ satisfy p ⊁ _Pq, then we connect p to q such that p ≻ q. This way, we obtain a new diagram P^c which is a complete layered partially ordered set.

Proof. For the purpose of this proof, we first need to show that P^c is a partially ordered set. Suppose that P^c is not a partially ordered set. Then there exist three elements p₁, p₂ and p₃ in P^c such that $p_{1} >_{P^{c}} p_{2}, p_{1} ≻_{P^{c}} p_{3} and p_{2} >_{P^{c}} p_{3} .$ (2)

If ${p_{1}, p_{2}, p_{3}} \subseteq X_{0}^{P}$ , then inasmuch as the construction of P^c, the formula (11) implies that p₁ > _Pp₂, p₁ ≻ _Pp₃ and p₂ > _Pp₃ which mean that P is not a partially ordered set, a contradiction.

If ${p_{1}, p_{2}, p_{3}} \subseteq P - X_{0}^{P}$ , then we assume that $p_{j} \in X_{t_{j}}^{P}$ and j ∈ {1, 2, 3}. Then from formula (11) and the construction of P^c, we have t₁ > t₂ > t₃. However, by the construction of P^c, the condition p₁ ≻ _{P
^c}p₃ yields that t₁ = t₃ + 1 clearly, which is contrary to the fact that t₁ > t₂ > t₃.

If ${p_{1}, p_{2}} \subseteq X_{0}^{P}$ and $p_{3} \notin X_{0}^{P}$ , then the formula (11) implies that p₁ > _Pp₂ and p₁ ≻ _Pp₃. Thus, by (C) of Definition 3.1, we know that p₁ is a minimal element of $X_{0}^{P}$ , contrary to the fact that p₁ > _Pp₂ and $p_{2} \in X_{0}^{P}$ .

If ${p_{2}, p_{3}} \subseteq X_{0}^{P}$ and $p_{1} \notin X_{0}^{P}$ , then the formula (11) implies that p₂ > _Pp₃ and p₁ ≻ _Pp₃. Then by (B) of Definition 3.1, we have that p₃ is a maximal element of $X_{0}^{P}$ , contrary to the fact that p₂ > _Pp₃ and $p_{2} \in X_{0}^{P}$ .

If ${p_{1}, p_{3}} \subseteq X_{0}^{P}$ and $p_{2} \notin X_{0}^{P}$ , then the formula (11) implies that p₁ ≻ _Pp₃. Further, from formula (11), there exists an element $p_{2}^{'} \in P$ such that $p_{1} ≻_{P^{c}} p_{2}^{'} \geq_{P^{c}} p_{2}$ and which implies that $p_{1} ≻_{P} p_{2}^{'}$ . Thus, by (D) of Definition 3.1, we have $p_{2}^{'} \notin X_{0}^{P}$ , which means that p₁ is a minimal element of $X_{0}^{P}$ , contrary to p₁ > _Pp₃ and $p_{3} \in X_{0}^{P}$ .

Therefore, in what follows, we suppose that there exists exactly one element of {p₁, p₂, p₃} which belongs to $X_{0}^{P}$ . There are three cases to consider.

Case 1. If $p_{1} \in X_{0}^{P}$ , then by formula (11) and the construction of P^c we have p₁ ≻ _Pp₃, which implies that p₁ is a minimal elements of $X_{0}^{P}$ . From formula (11), there exists an element u ∈ P such that p₁ ≻ _{P
^c}u ≥ _{P
^c}p₂ and which implies that p₁ ≻ _Pu. Clearly, $u \notin X_{0}^{P}$ since p₁ is a minimal elements of $X_{0}^{P}$ . Then by (C) of Definition 3.1, there exists an integer j such that $u \in X_{j}^{P}$ and $p_{3} \in X_{j}^{P}$ . However, u ≥ _{P
^c}p₂ > _{P
^c}p₃, a contradiction.

Case 2. If $p_{2} \in X_{0}^{P}$ , then by the construction of P^c, p₁ ≻ _{P
^c}p₃ implies that there exists an integer k ∈ {1, ⋯ , r (P) -1} such that $p_{1} \in X_{k + 1}^{P}$ and $p_{3} \in X_{k}^{P}$ , i.e., r (p₁) = r (p₃) +1. Further, formula (11) yields that there exist two elements q ∈ P and r ∈ P such that p₁ ≻ _{P
^c}q ≥ _{P
^c}p₂ ≥ _{P
^c}r ≻ _{P
^c}p₃. We claim that $q \in X_{0}^{P}$ . Indeed, if $q \notin X_{0}^{P}$ then $q \in X_{k}^{P}$ , contrary to q > _{P
^c}p₃. Similarly, we can prove that $r \in X_{0}^{P}$ . Thus p₁ ≻ _{P
^c}q and r ≻ _{P
^c}p₃ will deduce that p₁ ≻ _Pq and r ≻ _Pp₃. On the other hand, by the construction of P^c, $q \in X_{0}^{P}$ , $p_{2} \in X_{0}^{P}$ and $r \in X_{0}^{P}$ will imply that q ≥ _Pp₂ ≥ _Pr since q ≥ _{P
^c}p₂ ≥ _{P
^c}r. Thus p₁ ≻ _Pq ≥ _Pp₂ ≥ _Pr ≻ _Pp₃, contrary to r (p₁) = r (p₃) +1.

Case 3. If $p_{3} \in X_{0}^{P}$ , then p₁ ≻ _Pp₃ by formula (11). Thus p₃ is a maximal element of $X_{0}^{P}$ by (B) of Definition 3.1. It is clear that there exists an element v ∈ P such that p₂ ≥ _{P
^c}v ≻ _{P
^c}p₃ by formula (11). Then v ≻ _Pp₃, and which means that $v \notin X_{0}^{P}$ . Thus by (B) of Definition 3.1., there exists an integer i such that $v \in X_{i}^{P}$ and $p_{1} \in X_{i}^{P}$ . However, p₁ > _{P
^c}p₂ ≥ _{P
^c}v, a contradiction.

Therefore, by Cases 1, 2 and 3, P^c is a partially ordered set, which together with the construction of P^c and Definition 3.1. deduce that P^c is a completed layered partially ordered set.□

Obviously, the completed layered partially ordered set in Fig. 4 is obtained from the following layered partially ordered set in Fig. 5 by Lemma 3.1.

Fig. 5

A finite layered partially ordered set.

Let P be a finite layered partially ordered set, and let P^c be obtained by Lemma 3.1. Then we observe that $X_{i}^{P} = X_{i}^{P^{c}} and r (P) = r (P^{c})$ (3) by the construction of P^c, and similar to the proof of Lemma 2.2 we have the following lemma by formula (5).

Lemma 3.2. Let P be a finite partially ordered set, and let P^c be obtained by Lemma 3.1. If O ∈ △ (P^c), then O ∈ △ (P) and N_{P
^c} (O) ≥ N_P (O).

Let P and Q be two disjoint partially ordered sets. For the elements x, y ∈ T = P ∪ Q, define x ≤ _Ty if one of the following conditions holds:

x, y ∈ P and x ≤ _Py;

x, y ∈ Q and x ≤ _Qy;

x ∈ P and y ∈ Q.

Then (T, ≤ _T) is a partially ordered set (see [3]). We write (T, ≤ _T) = P + Q. It is easy to see that if P = K_{m₁,⋯,m_k}, Q = K_{n₁,⋯,n_r} and P∩ Q = ∅, then P + Q = K_{m₁,⋯,m_k,n₁,⋯,n_r}.

Now, let P = (P, ≤ _P) be a finite partially ordered set. Suppose that S = (S, ≤ _S) and R = (R, ≤ _R) are two disjoint partially ordered sets, and both S and R are subsets of P. For the elements p, q ∈ T = S ∪ R, define p ≺ _Tq if one of the following conditions holds:

p, q ∈ S and p ≺ _Sq;

p, q ∈ R and p ≺ _Rq;

p ∈ S and q ∈ R, p ≺ _Pq;

p ∈ R and q ∈ S, p ≺ _Pq.

We write (T, ≺ _T) = S ⊎ _PR, and say that S ⊎ _PR is the join-sum of S and R restricted to P. Then we have the following lemma.

Lemma 3.3. Let P be a complete layered partially ordered set with r (P) ≥3, and let $Q = (X_{0}^{P}, \leq_{P})$ , $R = (⋃_{i = 4}^{i = r (P)} X_{i}^{P}, \leq_{P})$ and S = K_m,n satisfying $X_{1}^{S} = X_{1}^{P}$ and $X_{2}^{S} = X_{2}^{P} ⋃ X_{3}^{P}$ . Then T = Q ⊎ _P (S + R) is a layered partially ordered set and r (T) = r (P) -1.

Proof. By the hypotheses of Lemma 3.3 and the definition of S + R, we have that P = S ∪ R ∪ Q and U = S + R is a complete layered partially ordered set. Moreover, r (U) = r (P) -1, $U = P - X_{0}^{P}$ and $X_{0}^{U} = \emptyset$ . On the other hand, by the construction of U, we know that $X_{1}^{U} = X_{1}^{S}, X_{2}^{U} = X_{2}^{S} and X_{i}^{U} = X_{i - 2}^{R} = X_{i + 1}^{P}$ (4) for any r (P) -1 ≥ i ≥ 3.

Now, let a, b ∈ P. Then by the definition of T = Q ⊎ _PU, there are three cases as below:

Case (i). If a, b ∈ U and a > _Tb then a > _Ub, especially, the condition a ≻ _Tb yields that $a ≻_{U} b .$ (5) Further, a > _Ub implies that $a >_{P} b$ (6) by the definition of U = S + R and the constructions of S and R.

Case (ii). If a, b ∈ Q and a > _Tb then we observe that a > _Pb, moreover, a ≻ _Tb will yield that $a ≻_{P} b .$ (7)

Case (iii). If a ∈ Q, b ∈ U or a ∈ U, b ∈ Q, then we know that a > _Tb means a > _Pb, especially, the condition a ≻ _Tb means $a ≻_{P} b$ (8) from the definition of T = Q ⊎ _PU.

Therefore, from formulas (5) to (8) we have $if a, b \in P and a \geq_{T} b then a \geq_{P} b .$ (9)

The rest of the proof is made in three steps as follows.

Step 1. T is a partially ordered set.

Assume that T is not a partially ordered set, then there exist three elements p, q, r ∈ T such that $p >_{T} q, p ≻_{T} r and q >_{T} r .$ (10) Clearly, formulas (9) and (10) imply that $p >_{P} q >_{P} r .$ (11) Thus we observe that p ⊁ _Pr since P is a partially ordered set.

We next claim that {p, q, r} ⊊U and {p, q, r} ⊊Q. If {p, q, r} ⊆ U then p > _uq, p ≻ _ur and q > _ur by formulas (5) and (10), which are contrary to that U is a partially ordered set. Similarly, from formulas (7) and (10) we have that {p, q, r} ⊊Q. Therefore, there are six types, as follows. Using formulas (5) to (10), we have that

Type 1. If p, q ∈ Q and r ∈ U then p ≻ _Pr.

Type 2. If q, r ∈ Q and p ∈ U then p ≻ _Pr.

Type 3. If p, r ∈ Q and q ∈ U then p ≻ _Pr.

Type 4. If p, q ∈ U and r ∈ Q then p ≻ _Pr.

Type 5. If q, r ∈ U and p ∈ Q then p ≻ _Pr.

Clearly, every type as above is in opposition to formula (11).

Type 6. If p, r ∈ U and q ∈ Q, then p ≻ _Ur and p > _Pr by formulas (5), (6) and (10). Since p ⊁ _Pr, by the construction of U, it is easy to see that there exists an element $y \in X_{3}^{P}$ such that p ≻ _Py ≻ _Pr which together with formula (11) follows that $q = y \in X_{3}^{P}$ , contrary to the fact that $q \in X_{0}^{P} = Q$ .

Therefore, T is a partially ordered set.

Step 2. T is closed.

By the definition of T = Q ⊎ _PU and the construction of U, we observe that T is a closed partially ordered set since T is a partially ordered set and P is closed.

Step 3. T is layered.

From Steps 1 and 2, T is a closed partially ordered set. Thus, in order to prove that T is layered, it suffices to show that (A), (B), (C) and (D) of Definition 3.1. are satisfied. The proof is made in three cases, as follows.

Case 1. We shall prove that the condition (D) holds.

By the definition of T = Q ⊎ _PU, the condition r (U) = r (P) -1 means that r (T) = r (U) since $X_{0}^{P} = Q$ . Then we have that $X_{0}^{T} \subseteq X_{0}^{P} = Q$ . Thus, from formulas (7) and (8), we know that the condition (D) is true. Further, by the construction of T and formula (4), we have that $X_{1}^{T} = X_{1}^{P}, X_{2}^{T} \supseteq X_{2}^{P} \cup X_{3}^{P} and X_{i}^{T} \supseteq X_{i + 1}^{P}$ (12) for any r (T) ≥ i ≥ 3.

Case 2. We shall show that the condition (B) holds. Dually, we can prove that the condition (C) is true.

Suppose that p is a maximal element of $X_{0}^{T}$ . Then $p \in X_{0}^{P} = Q$ because of $X_{0}^{T} \subseteq X_{0}^{P} = Q$ .

If p is a maximal element of $X_{0}^{P}$ then there exists an element $r \in P - X_{0}^{P} = U$ such that r ≻ _Pp since P is a layered partially ordered set. Then from the definition of T = Q ⊎ _PU, we must have that r ≻ _Tp since r ∈ U and p ∈ Q. Let q ≻ _Tp. Then by formulas (7) and (8), we have that q ≻ _Pp because of p ∈ Q. It follows that q ≻ _Pp for any q ≻ _Tp, which will deduce that there exists an integer j such that $q \in X_{j}^{P}$ for any q ≻ _Tp since P is a layered partially ordered set and p is a maximal element of $X_{0}^{P}$ . We conclude that there exists an integer k such that $q \in X_{k}^{T}$ for any q ≻ _Tp by formula (12).

If p is not a maximal element of $X_{0}^{P}$ , then p has only one cover q in P since P is a layered partially ordered set and $p \in X_{0}^{P}$ . Clearly, $q \in X_{i}^{T}$ for a certain integer i since p is maximal element of $X_{0}^{T}$ . Now, we claim that p has only one cover q in T. Otherwise, suppose that there are at least two different elements q₁, q₂ ∈ T such that q₁ ≻ _Tp and q₂ ≻ _Tp. By formulas (7) and (8), it follows that q₁ ≻ _Pp and q₂ ≻ _Pp because of p ∈ Q, an impossibility. We conclude that p has only one cover q in T, and then $q \in X_{i}^{T}$ for any q ≻ _Tp.

Therefore, if p is a maximal element of $X_{0}^{T}$ then there exists an element $q \in X_{j_{0}}^{T}$ such that q ≻ _Tp, and $r \in X_{j_{0}}^{T}$ for any r ≻ _Tp.

Conversely, we shall show that if p has covers in $T - X_{0}^{T}$ then p is a maximal element of $X_{0}^{T}$ .

Let $p \in X_{0}^{T}$ . Using formulas (7) and (8), if there exists an element $q \in T - X_{0}^{T}$ such that q ≻ _Tp then q ≻ _Pp. In what follows, we shall prove that p is not a maximal element of $X_{0}^{T}$ will lead to a contradiction. In fact, if p is not a maximal element of $X_{0}^{T}$ , then there exists an element $r \in X_{0}^{T}$ such that r ≻ _Tp. Note that both p and r belong to Q since $X_{0}^{T} \subseteq X_{0}^{P} = Q$ . Thus r ≻ _Pp by formula (7). If $q \notin X_{0}^{P}$ , then p is a maximal element of $X_{0}^{P}$ since q ≻ _Pp and P is a layered partially ordered set, contrary to the fact that r ≻ _Pp and $r \in X_{0}^{P}$ . Hence, $q \in X_{0}^{P}$ , which together with r ≻ _Pp, q ≻ _Pp and $r \in X_{0}^{P}$ deduces that P is not a layered partially ordered set, a contradiction. Therefore, p is a maximal element of $X_{0}^{T}$ .

Consequently, the condition (B) holds.

Case 3. We shall prove that the condition (A) is true.

Suppose that $p, q \notin X_{0}^{T}$ , and p ≻ _Tq. Then $p \in X_{j}^{T}$ , $q \in X_{i}^{T}$ and j > i where i ≠ 0. If $p, q \in P - X_{0}^{P}$ then p, q ∈ U since $Q = X_{0}^{P}$ , P = S ∪ R ∪ Q and U = S + R. Using formula (5), we know that p ≻ _Uq, and which together with formulas (4) and (12) yields that j - i = 1 since U = S + R is a complete layered partially ordered set.

In what follows, we shall prove that either $p \notin P - X_{0}^{P}$ or $q \notin P - X_{0}^{P}$ still implies j - i = 1. Assume that j - i ≠ 1, then j - i ≥ 2. Distinguishing three situations, we have:

(i₁) If $p, q \in X_{0}^{P}$ , then p, q ∈ Q. From this it follows that p ≻ _Tq will yield p ≻ _Pq by formula (7). On the other hand, the condition j - i ≥ 2 implies that there exists an element $p_{1} \in X_{i + 1}^{T}$ such that p₁ ≻ _Tq by formula (7), this implies that p₁ ≻ _Pq since q ∈ Q. Clearly p₁ ≠ p which together with p ≻ _Pq, p₁ ≻ _Pq and $p, q \in X_{0}^{P}$ deduces that $p_{1} \notin X_{0}^{P}$ since P is a layered partially ordered set. Hence q is a maximal element of $X_{0}^{P}$ , contrary to $p \in X_{0}^{P}$ and p ≻ _Pq.

(i₂) If $q \in X_{0}^{P} = Q$ and $p \notin X_{0}^{P}$ . Then p ≻ _Tq yields that p ≻ _Pq by formula (8). Thus, q is a maximal element of $X_{0}^{P}$ . By the proof of (i₁), we know that there exists an element $p_{1} \in X_{i + 1}^{T}$ such that p₁ ≻ _Tq and p₁ ≻ _Pq. It follows that $p_{1} \notin X_{0}^{P}$ , and this implies that there exists an integer k such that $p, p_{1} \in X_{k}^{P}$ since P is a layered partially ordered set. By formula (12), there exists an integer k₁ such that $p, p_{1} \in X_{k_{1}}^{T}$ , contrary to $p \in X_{j}^{T}$ , $p_{1} \in X_{i + 1}^{T}$ and j - i ≥ 2.

(i₃) If $p \in X_{0}^{P} = Q$ and $q \notin X_{0}^{P}$ , then p ≻ _Tq and p ∈ Q yield that p ≻ _Pq by formula (8). Thus p is a minimal element of $X_{0}^{P}$ since P is a layered partially ordered set. On the other hand, from j - i ≥ 2, there exists an element $p_{1} \in X_{j - 1}^{T}$ such that p ≻ _Tp₁, this implies that p ≻ _Pp₁ by formula (8). Thus, from P is a layered partially ordered set, there exists an integer t such that $p_{1}, q \in X_{t}^{P}$ , which together with formula (12) deduces that $p_{1}, q \in X_{t_{1}}^{T}$ for a certain t₁ ∈ {1, ⋯ , r (T)}, a contradiction.

Therefore, the condition (A) is satisfied.

From Cases 1,2 and 3, we conclude that T is a layered partially ordered set.□

In Fig. 6, we know that the layered partially ordered set M₃ is obtained from the complete layered partially ordered set P by Lemma 3.3, and it is easy to see that r (M₃) = r (P) -1 = 3.

Fig. 6

Two partially ordered sets P and M₃.

For convenience, we denote by $m_{q}^{P} = | {u \in P : u ≺_{P} q} |$ . Then, from formulas (5)–(8) in the proof of Lemma 3.3, one can check that $m_{q}^{T} \geq m_{q}^{P} for any q \in P - S,$ (13) and if $| X_{1}^{P} | \geq | X_{2}^{P} |$ then $m_{q}^{T} \geq m_{q}^{P} for any q \in P .$ (14)

Lemma 3.4. Let P be a complete layered partially ordered set with r (P) ≥3, and let $Q = (X_{0}^{P}, \leq_{P})$ , $R = (⋃_{i = 3}^{i = r (P)} X_{i}^{P}, \leq_{P})$ and S = K_m,n satisfying $X_{1}^{S} = X_{2}^{P}$ and $X_{2}^{S} = X_{1}^{P}$ . Then T = Q ⊎ _P (S + R) is a layered partially ordered set and r (T) = r (P).

Proof. Let U = S + R. Then $U = P - X_{0}^{P} = P - Q$ , and by the construction of U, one can observe that U is a complete layered partially ordered set with r (U) = r (P) and $X_{0}^{U} = \emptyset$ . Further, by the hypotheses of Lemma 3.4, we have that $X_{1}^{U} = X_{2}^{S}, X_{2}^{U} = X_{1}^{S} and X_{i}^{U} = X_{i - 2}^{R} = X_{i}^{P}$ (15) for any r (P) ≥ i ≥ 3.

Now, suppose a, b ∈ P. Then similar to the proof of Lemma 3.3, we can distinguish three cases:

Case I. If a, b ∈ U and a ≻ _Tb then $a ≻_{U} b,$ (16) further, if a, b ∈ S and a > _Ub then $a <_{P} b,$ (17) and if a ∈ R, b ∈ S and a > _Ub then $a >_{P} b .$ (18)

Case II. If a, b ∈ Q and a ≻ _Tb then $a ≻_{P} b .$ (19)

Case III. If a ∈ Q, b ∈ U or a ∈ U, b ∈ Q, then a ≻ _Tb means $a ≻_{P} b .$ (20)

The rest of the proof is made in two steps as follows.

Step (a). T is a partially ordered set.

Assume that T is not a partially ordered set, then there exist three elements p, q, r ∈ T such that $p >_{T} q, p ≻_{T} r and q >_{T} r .$ (21)

If {p, q, r} ⊆ U then p > _Uq, p ≻ _Ur and q > _Ur by formulas (16) and (21), contrary to the fact that U is a partially ordered set. Thus, {p, q, r} ⊊U. From formulas (19) and (21), it follows that {p, q, r} ⊊Q similarly. Therefore, there are six types, as follows.

Type (a). If p, q ∈ Q and r ∈ U then p > _Pq > _Pr and p ≻ _Pr by formulas (19), (20) and (21), a contradiction.

Type (b). If q, r ∈ Q and p ∈ U, then similar to the proof of Type (a), one can deduce a contradiction.

Type (c). If p, r ∈ Q and q ∈ U, then similar to the proof of Type (a), one can deduce a contradiction.

Type (d). If p, q ∈ U and r ∈ Q then p ≻ _Pr and q > _Pr from formulas (20) and (21). Moreover, from formula (20) and p > _Tq in formula (21) we have that p > _Uq, and which yields that p and q are comparable in P by the construction of U. Clearly, if p > _Pq then p > _Pq > _Pr, contrary to the fact that p ≻ _Pr. Thus we must have that q > _Pp ≻ _Pr which together with p > _Uq deduces that $p \in X_{1}^{P}$ by formula (15). Thus p ⊁ _P r, an impossibility.

Type (e). If q, r ∈ U and p ∈ Q, then similar to the proof of Type(d), one will obtain a contradiction.

Type (f). If p, r ∈ U and q ∈ Q, then p ≻ _Ur and p > _Pq > _Pr from formulas (16), (20) and (21). Since p ≻ _Pr will deduce a contradiction, we have p ⊁ _P r. Thus, by the construction of U, it is easy to see that there exists an element $y \in X_{2}^{P}$ such that p ≻ _Py ≻ _Pr. Then $q = y \in X_{2}^{P}$ , and this contradicts the fact that $q \in X_{0}^{P} = Q$ .

Therefore, T is a partially ordered set.

Step (b). T is layered.

Arguing as Step 2 in the proof of Lemma 3.3, one can prove that T is a closed partially ordered set. Thus it suffices to show that (A), (B), (C) and (D) of Definition 3.1 hold.

By the definition of T = Q ⊎ _PU, the condition r (U) = r (P) means that r (T) = r (U) since $X_{0}^{P} = Q$ . Then we have that $X_{0}^{T} \subseteq X_{0}^{P} = Q$ . Further, by formula (15), we have that $X_{1}^{T} = X_{2}^{P}, X_{2}^{T} = X_{1}^{P} and X_{i}^{T} \supseteq X_{i}^{P}$ (22) for any r (T) ≥ i ≥ 3.

Similar to Cases 1, 2 and 3 in the proof of Lemma 3.3, we can prove that (A), (B), (C) and (D) of Definition 3.1 are satisfied.

Consequently, T is a layered partially ordered set.□

Obviously, the layered partially ordered set M₃ in Fig. 6 is obtained from the following complete layered partially ordered set P in Fig. 7 by Lemma 3.4 and r (M₃) = r (P).

Fig. 7

A finite complete layered partially ordered set P.

Notice that, from formulas (16)-(20) in the proof of Lemma 3.4, one can check that $m_{q}^{T} \geq m_{q}^{P} for any q \in P - ⋃_{i = 1}^{i = 3} X_{i}^{P} .$ (23)

4 The upper bound theorem

Let T = K_{n₁,⋯,n_m}. By formula (5), we know that for any two ascending orders O₁, O₂ ∈ △ (T), N_T (O₁) = N_T (O₂). Thus, for convenience, let N (T) = N_T (O) for any O ∈ △ (T) below.

Theorem 4.1. Let P be a layered partially ordered set with n elements. If n ≥ 2, then there exist an ascending order O ∈ △ (P) and a partially ordered set T = K_u,v with u + v = n such that N (T) ≥ N_P (O).

Proof. (I) In the case of r (P) =1. Suppose that O ∈ △ (P) with O = {p₁, p₂, ⋯ , p_n}. Then, by formula (5), $N_{P} (O) = 2 [(n + 1) + n + \dots + 2] + 1 = n^{2} + 3 n + 1 .$ Let T = K_n-1,1. Using formula (5), we have $N (T) = 2 [(n + 1) n + n + \dots + 2] + 1 = 3 n^{2} + 3 n - 1 .$ Thus N (T) - N_P (O) =2 (n² - 1) ≥0 for any n ≥ 2, i.e., N (T) ≥ N_P (O).

(II) In the case of r (P) =2. Let T = P^c. We have that $X_{0}^{P} = \emptyset$ since P is a layered partially ordered set. Thus T = P^c = K_u,v and u + v = n by formula (3). Set O ∈ △ (P^c). Then O ∈ △ (P) and N (T) = N_{P
^c} (O) ≥ N_P (O) by Lemma 3.2.

(III) In the case of r (P) =3. We know that $X_{0}^{P} = \emptyset$ since P is a layered partially ordered set. Observe that $X_{i}^{P^{c}} = X_{i}^{P}$ for any i ∈ {0, 1, 2, 3} by formula (3). Thus P^c = K_{t₁,t₂,t₃} with $t_{i} = | X_{i}^{P^{c}} |$ for any i ∈ {1, 2, 3}, and this deduces that t₁ + t₂ + t₃ = n.

Let O ∈ △ (P^c). Then from Lemma 3.2, we know that O ∈ △ (P) and N_P (O) ≤ N_{P
^c} (O) = N (P^c). Further, using formula (5), we have that $\begin{matrix} N (P^{c}) & = & 2 [(n + 1) (t_{2} + 1) + \dots + (t_{1} + t_{2} + 2) (t_{2} + 1)] \\ + & 2 [(t_{1} + t_{2} + 1) (t_{1} + 1) + \dots + (t_{1} + 2) (t_{1} + 1)] \\ + & 2 [(t_{1} + 1) + \dots + 2] + 1 . \end{matrix}$ We distinguish two cases as below.

Case 1. If t₁ ≥ t₂, then let T = K_{t₁,t₂+t₃}. Using formula (5), we know that $\begin{matrix} N (T) = 2 [(n + 1) (t_{1} + 1) + \dots + (t_{1} + 2) (t_{1} + 1)] \\ + 2 [(t_{1} + 1) + \dots + 2] + 1 . \end{matrix}$ Then $\begin{matrix} N (T) - N (P^{c}) = 2 (t_{1} - t_{2}) [(n + 1) + \dots \\ + (t_{1} + t_{2} + 2)] \geq 0 \end{matrix}$ since t₁ ≥ t₂. At the same time, N (T) - N_P (O) ≥ N (T) - N (P^c) since N (P^c) ≥ N_P (O). Thus N (T) - N_P (O) ≥0, i.e., N (T) ≥ N_P (O).

Case 2. If t₂ ≥ t₁, then let T = K_{t₂,t₁+t₃}. Using formula (5), we know that $\begin{matrix} N (T) = 2 [(n + 1) (t_{2} + 1) + \dots + (t_{2} + 2) (t_{2} + 1)] \\ + 2 [(t_{2} + 1) + \dots + 2] + 1 . \end{matrix}$ Then $N (T) - N (P^{c}) = t_{2}^{2} t_{1} - t_{2}^{2} t_{2} = t_{1} t_{2} (t_{2} - t_{1}) \geq 0$ since t₂ ≥ t₁. Therefore, N (T) - N_P (O) ≥0 since N (P^c) ≥ N_P (O), i.e., N (T) ≥ N_P (O).

(IV) In the case of r (P) = k > 3. By Lemma 3.1, it is clear that P^c is a complete layered partially ordered set. By formula (3), we have that r (P^c) = r (P) = k. Let $X_{1}^{P^{c}} = {p_{1}, \dots, p_{t_{1}}}$ , $X_{2}^{P^{c}} = {p_{t_{1} + 1}, \dots, p_{t_{1} + t_{2}}}$ and $X_{3}^{P^{c}} = {p_{t_{1} + t_{2} + 1}, \dots, p_{t_{1} + t_{2} + t_{3}}}$ . There are two cases as follows.

Case (i). If t₁ ≥ t₂, then set $Q_{1} = (X_{0}^{P^{c}}, \leq_{P^{c}})$ , $R_{1} = (⋃_{i = 4}^{i = r (P^{c})} X_{i}^{P^{c}}, \leq_{P^{c}})$ and S₁ = K_m,n with $X_{1}^{S_{1}} = X_{1}^{P^{c}}$ and $X_{2}^{S_{1}} = X_{2}^{P^{c}} ⋃ X_{3}^{P^{c}}$ . Moreover, let T₁ = Q₁ ⊎ _{P
^c} (S₁ + R₁). Then T₁ is a layered partially ordered set by Lemma 3.3, and consequently $T_{1}^{c}$ is a complete layered partially ordered set by Lemma 3.1. Using formulas (3) and (12), we have that $X_{1}^{T_{1}^{c}} = X_{1}^{P^{c}}$ and $X_{2}^{T_{1}^{c}} \supseteq X_{2}^{P^{c}} \cup X_{3}^{P^{c}}$ . Then, without loss of generality, we assume that $X_{2}^{T_{1}^{c}} = {p_{t_{1} + 1}, \dots, p_{t_{1} + t_{2} + t_{3}}, \dots, p_{t_{1} + t_{2} + t_{3} + m_{1}}}$ and $X_{3}^{T_{1}^{c}} = {p_{t_{1} + t_{2} + t_{3} + m_{1} + 1}, \dots, p_{t_{1} + t_{2} + t_{3} + m_{1} + m_{2}}}$ where m₁ ≥ 0 and m₂ ≥ 1. Clearly,

$\begin{matrix} {p_{1}, \dots, p_{t_{1} + t_{2} + t_{3} + m_{1} + m_{2}}} is an ascending order \\ of (⋃_{i = 1}^{i = 3} X_{i}^{T_{1}^{c}}, \leq_{T_{1}^{c}}) . \end{matrix}$ (24)

Next, let $Γ = {p_{t_{1} + t_{2} + t_{3} + m_{1} + m_{2} + 1}, \dots, p_{n}}$ be an ascending order of $(T_{1}^{c} - ⋃_{i = 1}^{i = 3} X_{i}^{T_{1}^{c}}, \leq_{T_{1}^{c}})$ . Then we claim that $O_{1} = {p_{1}, \dots, p_{n}} \in △ (T_{1}^{c})$ . Otherwise, there exists an element q ∈ Γ such that $q ≺_{T_{1}^{c}} p_{i}$ for some i with 1 ≤ i ≤ t₁ + t₂ + t₃ + m₁ + m₂ by formula (24). Then $p_{i} \notin X_{1}^{T_{1}^{c}}$ obviously. As $p_{i} \in X_{2}^{T_{1}^{c}}$ and $q ≺_{T_{1}^{c}} p_{i}$ , we have that $q \in X_{1}^{T_{1}^{c}}$ , an impossibility. Thus $p_{i} \in X_{3}^{T_{1}^{c}}$ . Hence, there must exist an element $r \in X_{1}^{T_{1}^{c}}$ such that $q ≻_{T_{1}^{c}} r$ since $T_{1}^{c}$ is a layered partially ordered set. We conclude that $q \in X_{2}^{T_{1}^{c}}$ , a contradiction. Therefore, $O_{1} = {p_{1}, \dots, p_{n}} \in △ (T_{1}^{c})$ .

Clearly, O₁ ∈ △ (T₁) by Lemma 3.2. Further, from formulas (5) to (8), we conclude that O₁ ∈ △ (P^c). Thus, by formulas (1) and (13), we have that $\begin{matrix} N_{T_{1}} (O_{1}) - N_{P^{c}} (O_{1}) \geq 2 (t_{1} - t_{2}) [(t_{1} + t_{2} + t_{3} + 1) \\ + \dots + (t_{1} + t_{2} + 2)] \geq 0 \end{matrix}$ since t₁ ≥ t₂. At the same time, $N_{T_{1}^{c}} (O_{1}) \geq N_{T_{1}} (O_{1})$ by Lemma 3.2. Therefore, we have that $N_{T_{1}^{c}} (O_{1}) - N_{P^{c}} (O_{1}) \geq 0$ i.e., $N_{T_{1}^{c}} (O_{1}) \geq N_{P^{c}} (O_{1}) .$ (25) Moreover, by Lemma 3.3, we know that $r (T_{1}^{c}) = r (T_{1}) = r (P^{c}) - 1 = k - 1$ .

Case (ii). If t₁ ≤ t₂, then set $X = (X_{0}^{P^{c}}, \leq_{P^{c}})$ , $Y = (⋃_{i = 3}^{i = r (P^{c})} X_{i}^{P^{c}}, \leq_{P^{c}})$ and Z = K_r,s with $X_{1}^{Z} = X_{2}^{P^{c}}$ and $X_{2}^{Z} = X_{1}^{P^{c}}$ . Let W = X ⊎ _{P
^c} (Z + Y). Then by Lemma 3.4, W is a layered partially ordered set, and which together with Lemma 3.1 implies that W^c is a complete partially ordered set. Using formulas (3) and (22), we obtain that $X_{1}^{W^{c}} = X_{2}^{P^{c}}$ , $X_{2}^{W^{c}} = X_{1}^{P^{c}}$ and $X_{3}^{W^{c}} \supseteq X_{3}^{P^{c}}$ . Then, without loss of generality, we assume that $\begin{matrix} X_{3}^{W^{c}} = {p_{t_{1} + t_{2} + 1}, \dots, p_{t_{1} + t_{2} + t_{3}}, p_{t_{1} + t_{2} + t_{3} + 1}, \\ \dots, p_{t_{1} + t_{2} + t_{3} + k_{0}}} with k_{0} \geq 0 . \end{matrix}$

Set $Q_{1} = (X_{0}^{W^{c}}, \leq_{W^{c}}), R_{1} = (⋃_{i = 4}^{i = r (W^{c})} X_{i}^{W^{c}}, \leq_{W^{c}})$ and S₁ = K_m,n with $X_{1}^{S_{1}} = X_{1}^{W^{c}}$ and $X_{2}^{S_{1}} = X_{2}^{W^{c}} ⋃ X_{3}^{W^{c}}$ . Let T₁ = Q₁ ⊎ _{W
^c} (S₁ + R₁). Then by the proof of Case (i), we know that $X_{1}^{T_{1}^{c}} = X_{1}^{W^{c}}$ and $X_{2}^{T_{1}^{c}} \supseteq X_{2}^{W^{c}} \cup X_{3}^{W^{c}}$ . Now, without loss of generality, we assume that $X_{2}^{T_{1}^{c}} = {p_{1}, \dots, p_{t_{1}}, p_{t_{1} + t_{2} + 1}, \dots, p_{t_{1} + t_{2} + t_{3} + k_{0} + m_{1}}}$ and $X_{3}^{T_{1}^{c}} = {p_{t_{1} + t_{2} + t_{3} + k_{0} + m_{1} + 1}, \dots, p_{t_{1} + t_{2} + t_{3} + k_{0} + m_{1} + m_{2}}}$ where m₁ ≥ 0 and m₂ ≥ 1. It is easy to see that $\begin{matrix} Λ = {p_{t_{1} + 1}, \dots, p_{t_{1} + t_{2}}, p_{1}, \dots, p_{t_{1}}, p_{t_{1} + t_{2} + 1}, \dots, \\ p_{t_{1} + t_{2} + t_{3} + k_{0} + m_{1} + m_{2}}} \end{matrix}$ is an ascending order of $(⋃_{i = 1}^{i = 3} X_{i}^{T_{1}^{c}}, \leq_{T_{1}^{c}})$ . Now, let ${p_{t_{1} + t_{2} + t_{3} + k_{0} + m_{1} + m_{2} + 1}, \dots, p_{n}}$ be an ascending order of $(T_{1}^{c} - ⋃_{i = 1}^{i = 3} X_{i}^{T_{1}^{c}}, \leq_{T_{1}^{c}})$ . Then similar to the proof of Case (i), we can prove that $O_{1} = {p_{t_{1} + 1}, \dots, p_{t_{1} + t_{2}}, p_{1}, \dots, p_{t_{1}}, p_{t_{1} + t_{2} + 1}, \dots, p_{n}}$ belongs to $△ (T_{1}^{c})$ , △ (T₁), △ (W^c) and △ (W), respectively. Let O₀ = {p₁, ⋯ , p_n}. Then, from formulas (16) to (20), we conclude that O₀ ∈ △ (P^c). Therefore, by Lemma 3.2, we have $N_{T_{1}^{c}} (O_{1}) \geq N_{T_{1}} (O_{1}) .$ (26) Again, by formulas (14) and (23), we have that $m_{q}^{P^{c}} \leq m_{q}^{T_{1}}$ for any $q \in P^{c} - ⋃_{i = 1}^{i = 3} X_{i}^{P^{c}}$ . Thus, from formula (5) we have that $N_{T_{1}} (O_{1}) - N_{P^{c}} (O_{0}) \geq t_{2}^{2} t_{1} - t_{2}^{2} t_{2} = t_{1} t_{2} (t_{2} - t_{1}) \geq 0$ since t₂ ≥ t₁, which together with formula (26) means that $N_{T_{1}^{c}} (O_{1}) - N_{P^{c}} (O_{0}) \geq 0$ i.e., $N_{T_{1}^{c}} (O_{1}) \geq N_{P^{c}} (O_{0}) .$ (27) Moreover, by Lemmas 3.3 and 3.4, we know that $r (T_{1}^{c}) = r (T_{1}) = r (P^{c}) - 1 = k - 1$ .

Cases (i) and (ii) tell us that in the case of r (P) = k > 3, we always can construct a set of complete layered partially ordered sets $K = {T_{0}^{c} = P^{c}, T_{1}^{c}, \dots, T_{k - 3}^{c}} with r (T_{i}) = k - i,$ and a set of ascending orders $O = {O_{0}, O_{1}, \dots, O_{k - 3}}$ satisfying $O_{i} \in △ (T_{i}^{c})$ and $N_{T_{i}^{c}} (O_{i}) \geq N_{T_{i - 1}^{c}} (O_{i - 1})$ (Note that the case that O_i = O_i-1 may occur, i ≥ 1, for instance, in formula (25)). Therefore $N_{T_{k - 3}^{c}} (O_{k - 3}) \geq N_{P^{c}} (O_{0})$ . By Lemma 3.2, the condition O₀ ∈ △ (P^c) implies that O₀ ∈ △ (P) and N_{P
^c} (O₀) ≥ N_P (O₀). Thus, $N_{T_{k - 3}^{c}} (O_{k - 3}) \geq N_{P} (O_{0})$ . Further, by the proof of (III), there exists a partially ordered set T = K_u,v with u + v = n such that $N (T) \geq N_{T_{k - 3}^{c}} (O_{k - 3})$ since $r (T_{k - 3}^{c}) = 3$ and $T_{k - 3}^{c}$ is a layered partially ordered set. Hence, N (T) ≥ N_P (O₀).

Finally, from (I), (II), (III) and (IV), we conclude that there exists an ascending order O ∈ △ (P) and a partially ordered set T = K_u,v with u + v = n such that N (T) ≥ N_P (O).□

The following example illustrates Theorem 4.1.

Let us consider the layered partially ordered set P in Fig. 7 again. We know that O = {p, b, c, a, d} ∈ ▵ (P), and then N_P (O) =83 by formula (5). On the other hand, we know that N (T) =101 ≥ 83 = N_P (O) by formula (5) when T = K_2,3.

5 The O (n³) bound

In this section, we shall give a positive response to the open problem raised by G. Grätzer in [2, 5].

Theorem 5.1. Let D be a finite distributive lattice with n join-irreducible elements and let P = (Con_JD, ≤ _D). If the $\bar{P}$ obtained by Lemma 2.1 is a layered partially ordered set, then D can be represented as the congruence lattice of a rectangular lattice L satisfying $| L | \leq \frac{2}{9} \sqrt{3} n^{3} + (3 \sqrt{3} - 2) n^{2} + (\frac{26 \sqrt{3}}{9} - 2) n + \frac{17 \sqrt{3}}{3} - 7 .$

Proof. Suppose n ≥ 2. Then by Theorem 4.1, there exists a partially ordered set T = K_k,t with k + t = n and an ascending order $O \in △ (\bar{P})$ such that $N (T) \geq N_{\bar{P}} (O)$ . Thus by Lemma 2.2 we have that O ∈ △ (P), and $N_{\bar{P}} (O) \geq N_{P} (O)$ which implies that N (T) ≥ N_P (O).

Using formula (5), we have $\begin{matrix} N (T) = 2 [(n + 1) (n - t + 1) + n (n - t + 1) \\ + \dots + (n - t + 2) (n - t + 1)] \\ + 2 [(n - t + 1) + \dots + 2] + 1 \\ = (nt - t^{2} + t) (2 n - t + 3) + (n - t) \\ (n - t + 3) + 1 = t^{3} - (3 n + 3) t^{2} \\ + (3 n + 2 n^{2}) t + n^{2} + 3 n + 1 = S (t) . \end{matrix}$ Then $\frac{d S (t)}{d t} = 3 t^{2} - 6 nt - 6 t + 3 n + 2 n^{2}$ . Clearly, $t_{0} = n + 1 - \frac{\sqrt{12 n^{2} + 36 n + 36}}{6}$ is a solution of $\frac{d S (t)}{d t} = 0$ . Further, we know that S (t) ≤ S (t₀) for any t ∈ {1, ⋯ , n}. Let $m = \frac{\sqrt{12 n^{2} + 36 n + 36}}{6}$ . Then $m \in [\frac{\sqrt{3}}{3} (n + 1), \frac{\sqrt{3}}{3} (n + 2)]$ . Suppose that $m_{1} = \frac{\sqrt{3}}{3} (n + 1)$ and $m_{2} = \frac{\sqrt{3}}{3} (n + 2)$ . Then $\begin{matrix} S (t_{0}) \leq [n + 1 - m_{1}]^{3} - (3 n + 3) \\ [n + 1 - m_{2}]^{2} + (3 n + 2 n^{2}) (n + 1 - m_{1}) \\ + n^{2} + 3 n + 1 = [2 - \frac{10}{9} \sqrt{3} - 3 (\frac{4}{3} - \frac{2}{3} \sqrt{3}) \\ + 2 (1 - \frac{\sqrt{3}}{3})] n^{3} + r (n) = \frac{2}{9} \sqrt{3} n^{3} + r (n) \end{matrix}$ in which $r (n) = (3 \sqrt{3} - 2) n^{2} + (\frac{26 \sqrt{3}}{9} - 2) n + \frac{17 \sqrt{3}}{3} - 7$ .

Therefore, $N_{P} (O) \leq N (T) \leq S (t_{0}) \leq \frac{2}{9} \sqrt{3} n^{3} + r (n)$ when n ≥ 2.

On the other hand, if n = 1 then N_P (O) =5. In this case we can verify that $N_{P} (O) \leq \frac{2}{9} \sqrt{3} n^{3} + r (n)$ .

Finally, we have $N_{P} (O) \leq \frac{2}{9} \sqrt{3} n^{3} + (3 \sqrt{3} - 2) n^{2} + (\frac{26 \sqrt{3}}{9} - 2) n + \frac{17 \sqrt{3}}{3} - 7$ , i.e., $| L | \leq \frac{2}{9} \sqrt{3} n^{3} + (3 \sqrt{3} - 2) n^{2} + (\frac{26 \sqrt{3}}{9} - 2) n + \frac{17 \sqrt{3}}{3} - 7$ .□

Now, we shall give an example to illustrate Theorem 5.1.

Example 5.1. Let D be a finite distributive lattice in Fig. 8. Then P = (Con_JD, ≤ _D) is the partially order set in Fig. 9.

Fig. 8

A distributive lattice D.

Fig. 9

The partially order set P = (Con_JD, ≤ _D).

Obviously, both the finite lattice D in Fig. 8 and the partially order set P in Fig. 9 satisfy the conditions of Theorem 5.1. Then we obtain a rectangular lattice L in Fig. 10 which satisfies ConL ≅ D and $| L | = 35 \leq \frac{2}{9} \sqrt{3} n^{3} + (3 \sqrt{3} - 2) n^{2} + (\frac{26 \sqrt{3}}{9} - 2) n + \frac{17 \sqrt{3}}{3} - 7$ with n = 3.

Fig. 10

A rectangular lattice L.

Lemma 5.1. Let P be a finite partially ordered set and H (P) be the diagram of P. If |P|=2n, then there are at most n² segments which connect the circles in H (P).

Proof. In order to prove Lemma 5.1, we first need to check the following result A.

A. If a space T have 2n points, and there are n² + 1 segments which connect these points in T, then there exists at lest one triangle in T.

This is trivial when n = 1, so we proceed by induction on n for n ≥ 2.

It is easy to see that A holds for n = 2. Assuming that A holds for n = k.

Consider n = k + 1. From the hypotheses of A, there are 2k + 2 points and (k + 1) ² + 1 segments in T. Let l be one of the segments and a, b be the endpoints of l. If there exists one point c of the other 2k points which connects both a and b, then a, b, c form a triangle. Otherwise, there are at most 2k + 1 segments which connect a or b. Thus, there are at least (k + 1) ² + 1 - (2k + 1) = k² + 1 segments among the other 2k points. By induction assumption, there exists at least one triangle in T, completing the proof of A.

Since H (P) is the diagram of P, there is no triangle in H (P). Therefore, by A, if |p|=2n, then there are at most n² segments which connect the circles in H (P).□

Similar to Lemma 5.1, we can verify the following lemma.

Lemma 5.2. Let P be a finite partially ordered set and H (P) be the diagram of P. If |P|=2n + 1, then there are at most n² + n segments which connect the circles in H (P).

Then we get the following improved version of Theorem 1.1:

Theorem 5.2. Let D be a finite distributive lattice with n join-irreducible elements. Then D can be represented as the congruence lattice of a rectangular lattice L satisfying |L| ≤ f (n) where $f (n) = {\begin{matrix} \frac{7}{12} n^{3} + \frac{7}{4} n^{2} + \frac{13}{6} n + 1, & n = 2 k, \\ \frac{7}{12} n^{3} + \frac{3}{2} n^{2} + \frac{17}{12} n + \frac{3}{2}, & n = 2 k + 1 . \end{matrix}$

Proof. Let P = (Con_JD, ≤ _D). Then |P| = n. Suppose that O = {p₁, p₂, ⋯ , p_n} ∈ △ (P). Then by formula (5), there exists a rectangular lattice L such that P ≅ Con_JL, in which L satisfies

$\begin{matrix} N_{P} (O) = | L | = 2 [(n + 1) (m_{n} + 1) + n (m_{n - 1} + 1) \\ + \dots + 2 (m_{1} + 1)] + 1 \end{matrix}$ (28) where m_i is the number of lower covers of p_i in P. Clearly, $0 \leq m_{i} \leq i - 1 .$ (29)

If n = 2k, then by Lemma 5.1 $\sum_{i = 1}^{i = n} m_{i} \leq k^{2}$ . We note that $\sum_{t = k}^{t = 2 k - 1} t = \frac{3}{2} k^{2} - \frac{k}{2} \geq k^{2}$ for any positive integer k. Therefore, using formulas (28) and (29), we have that $\begin{matrix} N_{P} (O) \leq 2 [(2 k + 1) (2 k) + 2 k (2 k - 1) + \dots + \\ (k + 2) (k + 1) + (k + 1) + k + \dots + 2] + 1, \end{matrix}$ i.e., $\begin{matrix} N_{P} (O) \leq 2 [(2 k)^{2} + (2 k - 1)^{2} + \dots + (k + 1)^{2}] \\ + 2 [2 k + (2 k - 1) + \dots + 2] + 2 k + 3 \\ = \frac{14}{3} k^{3} + 7 k^{2} + \frac{13}{3} k + 1 \\ = \frac{7}{12} n^{3} + \frac{7}{4} n^{2} + \frac{13}{6} n + 1 . \end{matrix}$

If n = 2k + 1, then by Lemma 5.2 $\sum_{i = 1}^{i = n} m_{i} \leq k^{2} + k$ . Again, $\sum_{t = k + 1}^{t = 2 k} t = \frac{3}{2} k^{2} + \frac{1}{2} k \geq k^{2} + k$ for any positive integer k. Therefore, using formulas (28) and (29), we have that $\begin{matrix} N_{P} (O) \leq 2 [(2 k + 2) (2 k + 1) + (2 k + 1) (2 k) + \dots + \\ (k + 3) (k + 2) + (k + 2) + (k + 1) + \dots + 2] + 1, \end{matrix}$ i.e., $\begin{matrix} N_{P} (O) \leq 2 [(2 k + 1)^{2} + (2 k)^{2} + \dots + (k + 2)^{2}] \\ + 2 [(2 k + 1) + 2 k + \dots + 2] + 2 k + 5 \\ = \frac{14}{3} k^{3} + 13 k^{2} + \frac{37}{3} k + 5 \\ = \frac{7}{12} n^{3} + \frac{3}{2} n^{2} + \frac{17}{12} n + \frac{3}{2} . \end{matrix}$

Consequently, |L| ≤ f (n).□

Next, we shall present an example to illustrate Theorem 5.2 as follows.

Example 5.2. Let us discuss the distributive lattice D in Fig. 8 again. We can check that ConL ≅ D and |L|=35 ≤ f (3) when L is the lattice in Fig. 10.

In [5], G. Grätzer and E. knapp presented that there is a planar semimodular lattice L such that Con_JL ≅ P for any finite partially ordered set P with $| L | = \sum_{k = 1}^{k = n} ({km}_{k} + 2 k + 2 m_{k} + 2) + 1$ (30) when O = {p₁, p₂, ⋯ , p_n} ∈ △ (P), where m_i is the number of lower covers of p_i in P. So, similar to the proof of Theorem 5.2, we get the following improved version of Theorem 1.2:

Theorem 5.3. Let D be a finite distributive lattice with n join-irreducible elements. Then D can be represented as the congruence lattice of a planar semimodular lattice L satisfying |L| ≤ g (n) with $g (n) = {\begin{matrix} \frac{7}{24} n^{3} + \frac{7}{4} n^{2} + \frac{7}{3} n + 1, & n = 2 k, \\ \frac{7}{24} n^{3} + \frac{13}{8} n^{2} + \frac{41}{24} n + \frac{11}{8}, & n = 2 k + 1 . \end{matrix}$

6 Conclusions

It is worth to be pointed out that both f (n) in Theorem 5.2 and g (n) in Theorem 5.3 are very rough. Thus, we have a question: how close can one brings the coefficient of n³ in f (n) to $\frac{2}{9} \sqrt{3}$ and the coefficient of n³ in g (n) to $\frac{\sqrt{3}}{9}$ ? On the other hand, let D be a finite distributive lattice whose order of join-irreducible elements is a balanced bipartite order on n elements. In 2010, G. Grätzer [6] proved that D can be represented as the congruence lattice of a rectangular lattice L with $| L | \geq \frac{n^{3}}{3456}$ . Therefore, we have another question: how close can one brings the constant $\frac{1}{3456}$ to $\frac{2}{9} \sqrt{3}$ ?

In the future, we shall study the characterizations of the congruence lattices of rectangular lattices, and then answer the two open problems as mentioned above.

References

Earnshaw

B.A.

, Combinatorial aspects of partially ordered sets (Lecture notes), http://users.math.msu.edu/users/earnshaw/research/poset.pdf, (2005).

Grätzer

, A short proof of the congruence representation theorem for semimodular lattice, Algebra Universalis 71 (2014), 65–68.

Grätzer

, Lattice theory: foundation, Birkhäuser, Basel, 2011.

Grätzer

and Knapp

, Notes on planar semimodular lattices. II. Congruences, Acta Sci Math (Szeged) 74 (2008), 37–47.

Grätzer

and Knapp

, Notes on planar semimodular lattices. III. Rectangular lattices, Acta Sci Math (Szeged) 75 (2009), 29–48.

Grätzer

and Knapp

, Notes on planar semimodular lattices. IV. The size of a minimal congruence lattices representation with rectangular lattices, Acta Sci Math (Szeged) 76 (2010), 3–26.

Grätzer

and Lakser

, Homomorphisms of distributive lattices as restrictions of congrunces, Canad J Math 38 (1986), 1122–1134.

Grätzer

and Lakser

, Congruence lattices of planar lattices, Acta Math Sci Hungar 60 (1992), 251–268.

Grätzer

, Lakser

and Schmidt

E.T.

, Congruence lattices of small planar lattices, Proc Amer Math Soc 123 (1995), 2619–2623.

10.

Grätzer

, Lakser

and Schmidt

E.T.

, Congruence lattices of finite semimodular lattices, Canad Math Bull 41 (1998), 290–297.

11.

Grätzer

, Rival

and Zaguia

, Small representations of finite distributive lattices as congruence lattices, Proc Amer Math Soc 123 (1998), 1959–1961. Correction: 126 (1998) 2509-2510.

12.

Grätzer

and Schmidt

E.T.

, On congruence lattices of lattices, Acta Math Sci Hungar 13 (1962), 179–185.

13.

Grätzer

and Wehrung

, Lattice theory: special topics and applications, Birkhäuser, Basel, 2014.