A unique type of subcontexts is always present in formal contexts with many concepts: the contranominal scales. We make this precise by giving an upper bound for the number of minimal generators (and thereby for the number of concepts) of contexts without contranominal scales larger than a given size. Extremal contexts are constructed which meet this bound exactly. They are completely classified.
1 Technische Universita¨t Dresden 2 V.N. Karazin Kharkiv National University
For a set S, a context of the form (S, S, 6=) will be called a contranominal scale.
We will denote by Nc(k) the contranominal scale with k objects (and k
attributes), that is, the context ([k], [k], 6=), where [k] := {1, 2, . . . , k}. The
expression K1 ≤ K denotes that K1 is a subcontext of K. The symbol ∼= expresses
the existence of an order-isomorphism whenever two ordered sets are involved
or, alternatively, the existence of a context isomorphism in the case of formal
contexts. For a context K to be Nc(k)-free means that there does not exist a
subcontext K1 ≤ K with K1 =∼ Nc(k). The boolean lattice with k atoms, that is,
B(Nc(k)), will be denoted by B(k). Similarly, we say that a lattice L is B(k)-free
whenever B(k) does not (order-)embed into L. Using Proposition 32 from [
m n o p q g h × i × × j × k × × × × × × × × o g n h m i
We denote by J (L) and M (L), respectively, the set of completely joinirreducible and meet-irreducible elements of a lattice L. The least and greatest elements of a lattice L will be denoted, respectively, by 0L and 1L. The symbol ≺ will designate the covering relation between elements, that is, x ≺ y if x < y and for every z ∈ L, x < z ≤ y ⇒ z = y. The length of a finite lattice is the number of elements in a maximum chain minus one. An atom is an element covering 0L, while a coatom is an element covered by 1L. Whenever two elements x, y ∈ L are incomparable, we will write x||y. We denote by A(L) the set of atoms of a lattice L. For an element l ∈ L, we shall write ↓ l := {x ∈ L | x ≤ l} as well as ↑ l := {x ∈ L | x ≥ l}. Moreover, for l ∈ L we denote by Al the set A(L) ∩ ↓ l and, similarly, by Jl the set J (L)∩ ↓ l. A complete lattice L is called atomistic if x = W Ax holds for every x ∈ L. In this case, A(L) = J (L).
Proposition 1. Let K be a context such that B(k) embeds into B(K). Then Nc(k) ≤ K.
Proof. Let (A1, B1), . . . , (Ak, Bk) be the atoms of B(k) in B(K). Similarly, denote its coatoms by (C1, D1), . . . , (Ck, Dk) in such a way that (Ai, Bi) ≤ (Cj , Dj ) ⇔ i 6= j for each i, j. Note that the sets Ai, as well as the sets Di, are non-empty. Let i ∈ [k]. Since (Ai, Bi) (Ci, Di), we may take an object/attribute pair gi ∈ Ai, mi ∈ Di with gi I mi. For every chosen object gi ∈ Ai, one has that giImj for every j ∈ [k] with j 6= i, because of (Ai, Bi) ≤ (Cj , Dj ), which implies Bi ⊇ Dj . Consequently, k distinct objects gi (as well as k distinct attributes mi) were chosen. Combining both relations results in giImj ⇔ i 6= j for each i ∈ [k], that is, the objects and attributes gi, mi form a contranominal scale in K. Definition 1. Let (G, M, I) be a formal context. A set S ⊆ G is said to be a minimal generator (of the extent S00) if T 00 6= S00 for every proper subset T ( S. The set of all minimal generators of a context K will be denoted by MinGen(K).
Observation: In contexts with finitely many objects, every extent has at least one minimal generator. Clearly, two different extents cannot share one same minimal generator. Thus, the upper bound |B(K)| ≤ |MinGen(K)| holds for contexts with finite object sets.
The problem of computing exactly the number of concepts does not admit
a polynomial-time algorithm, unless P=NP. This was shown by Kuznetsov [
Our investigations were inspired by a result of Prisner, who gave the first upper
bound regarding contranominal-scale free contexts. The original version is in
graph theoretic language. Reformulated it reads as follows:
Theorem 1 (Prisner [
In this section we will show an improvement of Theorem 1. For that, we will relate minimal generators with contranominal scales. The first step towards this is the equivalence shown in Proposition 2. Note that, since derivation operators are antitone, the 6= symbol may be substituted by ).
Proposition 2. Let (G, M, I) be a formal context. A set S ⊆ G is a minimal generator if and only if for every g ∈ S, it holds that (S \ {g})0 6= S0. Proof. We will show the two equivalent contrapositions. If (S \ {g})0 = S0, then, of course, (S \ {g})00 = S00, and S is not a minimal generator. For the converse, suppose that S is not a minimal generator, and take a proper subset T of S with T 00 = S00. Note that T 00 = S00 implies T 0 = S0. Let g ∈ S \ T . On one hand, (S \ {g}) ⊆ S implies (S \ {g})0 ⊇ S0. On the other hand, (S \ {g}) ⊇ T implies (S \ {g})0 ⊆ T 0 = S0. Combining both yields (S \ {g})0 = S0.
The next proposition relates minimal generators and contranominal scales. Lemma 1. Let K = (G, M, I) be a context and A ⊆ G. There exists a contranominal scale K1 ≤ K having A as its object set if and only if A is a minimal generator. In particular, if G is finite:
mA⊆aGx{|A| : A is a minimal generator} = max{k ∈ N : Nc(k) ≤ K}. Proof. Suppose that A is a minimal generator and let g ∈ A. By Proposition 2, one has that (A \ {g})0 ) A0. Hence, there exists an attribute m with g I m and hIm for every h ∈ A \ {g}. Clearly, two different objects g1, g2 ∈ A cannot give rise to the same attribute m, since the two pairs of conditions gi I m and hIm for every h ∈ A\{gi} cannot be satisfied simultaneously (i = 1, 2). Thus, there exists an injection ι : A → M with g I ι(g), hIι(g) for each g ∈ A and each h ∈ A \ {g}. By setting N = ι(A), one has that (A, N, I ∩ (A × N )) is a contranominal scale. For the converse, let K1 = (S, S, 6=) ≤ K be a contranominal scale and let g ∈ S. Clearly, g ∈/ S0. Moreover, g ∈ (S \ {g})0. This amounts to (S \ {g})0 ) S0 for each g ∈ S. By Proposition 2, the set S is a minimal generator.
A consequence of Lemma 1 is the following, which is an improvement of the order of k! · |M |k/k of Prisner’s bound.
Theorem 2. Let K = (G, M, I) be a Nc(k)-free context with finite G. Then: k−1 |B(K)| ≤ |MinGen(K)| ≤ X i=0 |G| . i In particular, if k ≤ | G2| : Proof. Lemma 1 guarantees that K does not have any minimal generator of cardinality greater or equal to k. The sum above is the number of subsets of G having cardinality at most k − 1.
Definition 2. We denote by f (n, k) the upper bound in Theorem 2: |G|k−1 |B(K)| ≤ k · (k − 1)! . f (n, k) := kX−1 n
i i=0 .
The upper bound in Theorem 2 for f (n, k) gets worse as k gets close to | G2| .
Tighter upper bounds for the sum of binomial coefficients may be found in [
The following property of f (n, k) is needed for the next two sections. Proposition 3. The function f (n, k) satisfies the following identity: f (n, k) = f (n − 1, k − 1) + f (n − 1, k).
Proof. This follows from a standard binomial identity: f (n − 1, k) + f (n − 1, k − 1) = Pik=−01 n −i1 + Pjk=−02 n−j1 = 1 + Pik=−11 ni−−11 + Pjk=−11 n−j1 = 1 + Pik=−11 ni = f (n, k).
Consider a finite lattice L. It is well known that every element x ∈ L is the supremum of some subset of J (L): for example, x = W Jx. We call such a subset a representation of x through join-irreducible elements (for brevity, we may say a representation through irreducibles of x or even only a representation of x). A representation S ⊆ J (L) of x is called irredundant if W(S \ {y}) 6= x for every y ∈ S. Of course, every x ∈ L has an irredundant representation, but it does not need to be unique. Note that irredundant representations are precisely minimal generators when one takes the standard context of L, (J (L), M (L), ≤). Indeed, in that formal context, the closure of object sets corresponds to the supremum of join-irreducible elements of L. For an element x ∈ L, there may exist elements in Jx which belong to every representation of x: the so-called extremal points. An element z ∈ Jx is an extremal point of x if there exists a lower neighbor y of x such that Jy = Jx \ {z}. Every representation of x must contain every extremal point z of x since, in this case, the supremum W(Jx \ {z}) is strictly smaller than x (and is actually covered by x).
In Section 5 we shall construct finite lattices for which every element has
exactly one irredundant representation. It turns out that, in the finite case, these
lattices are precisely the meet-distributive lattices. This is implied by Theorem
44 of [
Proposition 4. Let L be a finite lattice. The following assertions are equivalent: i) L is meet-distributive. ii) Every element x ∈ L is the supremum of its extremal points. iii) For every x, y ∈ L with x ≺ y, it holds that |Jy \ Jx| = 1.
Proof. The equivalence between i) and ii) may be found in Theorem 44 of [
The next lemma will be useful in Section 5, when we shall change the perspective from lattices to contexts.
Lemma 2. Let L be a finite lattice. If L is B(k)-free, then every element has a representation through join-irreducibles of size at most k − 1. The converse holds if L is meet-distributive.
Proof. Let K = (J (L), M (L), ≤) be the standard context of L. We identify the elements of L with the extents of K via x 7→ Jx. Suppose that L is B(k)-free. Then, K is Nc(k)-free. Let A be an arbitrary extent of K and S a minimal generator of A. Then, by Lemma 1, it follows that |S| ≤ k − 1. Since A = S00 = W S, we have the desired representation. Now, suppose that |Jy \ Jx| = 1 holds for every x, y ∈ L with x ≺ y (cf. Proposition 4). To prove the converse, we suppose that B(k) embeds into L and our goal is to show that some x ∈ L does not have any representation with fewer than k elements of J (L). Now, since B(k) embeds into L, Proposition 1 implies that Nc(k) is a subcontext of K. Applying Lemma 1, we have that there exists a minimal generator S ⊆ J (L) with |S| = k. Equivalently, S is an irredundant representation of the element S00 of L. By Proposition 4, S is the unique irredundant representation of S00. Therefore, S00 cannot be expressed as the supremum of fewer than k join-irreducible elements. 5
In this section, we will consider only finite lattices. Our objective is to construct lattices which prove that the bound in Theorem 2 is sharp.
Definition 3. For positive integers n and k, we call a lattice (n,k)-extremal if it has at most n join-irreducible elements, is B(k)-free, and has exactly f (n, k) elements.
It is clear that every (n, 1)-extremal lattice is trivial, i.e., the lattice with one element. To construct (n, k)-extremal lattices with larger k, we will use an operation which we call doubling.
Definition 4. Let L be an .ordered se.t and K ⊆ L. The doubling o.f K in L is defined to be L[K] = L ∪ K, where K is a disjoint copy of K, i.e., K ∩ L = ∅. The order in (L[K], ≤0) is defined as follows:
. . . . . . ≤0 = ≤ ∪ {(x, y) ∈ L × K | x ≤ y} ∪ {(x, y) ∈ K × K | x ≤ y}. .
We will employ the notation. x to denote the image und. er doubling of an
element x ∈ K. No.te that x ≺ x for every x ∈ K, and that x is the only upper
neighbor of x in K. When L is a set family C ⊆ P(G), then the diagram of
L[K] can be easily depicted: the doubling C[D] (with D ⊆ C) corresponds to
the set family C ∪ {D ∪ {g} | D ∈ D}, where g ∈/ G is a new element. Figure 2
illustrates three doubling operations. The first one is the doubling of the chain
{∅, {2}, {1, 2}} inside the closure system C1 = P([
C1 1234 1 123 2
C3
2 234 3
123 12 23 234 3
3 1 12
1234 123
2
C2 2
C4 12 23 34 23 24 1
Since we are interested in constructing lattices, it is vital to guarantee that the doubling operation produces a lattice. By a meet-subsemilattice of a lattice L is meant a subset K of L, endowed with the inherited order, such that x ∧ y ∈ K holds for every x, y ∈ K. It is called topped if 1L ∈ K.
Proposition 5. If K is a topped meet-subsemilattice of a lattice L, then L[K] is a lattice.
Proof. Let x, y ∈ L[K]. If both x and y belong to L, then clearly x ∧ y and x ∨ y belong to L ⊆ L[K]. Suppose that only one among x and y, say x, belongs to .
L. Th.en y = z with z ∈. K. We have that x ∧ y = x ∧ z ∈ L ⊆ L[K] because of x 0K and y = z ∨ 0K . For the supremum, set S = {w ∈ K | w ≥ x, w ≥ z} and u = V S. Note that the fact that K is topped causes S 6= ∅. Since K is a meet-subsemilattice, we have that u ∈ K. It is clear that u is the least upper . bound of x and z whic.h belongs to K. Therefore, u is the least upper bound o.f . x and y, because of 0K u and y = z ∨ 0K . The rema.ining c.ase is x, y ∈ K for which, clearly x ∧ y exists. Moreover, writing x = t, y = z with t, z ∈ K a.nd setting S = {w ∈ K | w ≥ t, w ≥ z} as well as u = V S make clear that u = x ∨ y.
When extrinsically considered, topped meet-subsemilattices are lattices. This is compatible with t.he proof of Proposition 5, where the s.upremum a.nd infimum of two elements in K may be easily verified to belong to K: that is, K is actually a sublattice of L[K].
A suborder K of an ordered set L is called cover-preserving if x ≺K y implies x ≺L y for every x, y ∈ K. This property plays a key role by preserving meetdistributivity under a doubling operation: Proposition 6. Let L be a meet-distributive lattice and let K be a cover-preserving, topped meet-subsemilattice of L. Then, L[K] is a meet-distributive lattice. Proof.. The fact that L[K] is a lattice comes from Proposition 5. Every element . x ∈ K has on.e lower neighbor in K, namely, x. Thus, the total number of lower neighbors of.x is one only if x does not cover any element in K, that is, x = 0K . Therefore, 0K is the only join-irreducible of L[K] which is not a join-irreducible of L. Let x, y ∈ L[K] with x ≺L[K] y. We use J(0·) to denote our J -notation in L[K] and J(·) in L. If x, y ∈ L, then clearly Jy0 = Jy and J x0 = Jx, .which . results in |Jy0 \ J x0| = |Jy \ Jx| = 1. If x, y ∈/ L, then x = z and y = w with z, w ∈ K and z ≺K w. From the fact that K is cover-preserving, we conclude that z ≺L w. Because. L is meet-distributive, it follows that |Jw \ Jz| = 1. Clearly . one has J x0 = Jz ∪ {0K } and Jy0 = Jw ∪ {0K }, which yields |Jy0 \ J x0| = 1. For the remaining case, one has necessarily x ∈ L an.d y ∈/ L. In these conditions, x ≺ y . results in y = x and, therefore, Jy0 = J x0 ∪ {0K }, implying |Jy0 \ J x0| = 1.
Proposition 7 is the first assertion about extremal meet-subsemilattices. We note that the set of join-irreducible elements of a meet-subsemilattice K of a lattice L is not the same as the set J (L) ∩ K. Therefore, what is meant by an (n, k)-extremal meet-subsemilattice of L is precisely the following: a lattice K which is (n, k)-extremal and a meet-subsemilattice of L as well.
Observe that chains with n + 1 elements are precisely the (n, 2)-extremal lattices. Proposition 7 illustrates, in particular, that an n + 1 element chain may be seen as the result of a doubling operation on an n element chain, provided that the doubling operation is performed with respect to the trivial topped meetsubsemilattice ↑ 1, which is (n, 1)-extremal.
Proposition 7. Let L be an (n − 1, k)-extremal lattice with n, k ≥ 2. Suppose that K is a topped, (n − 1, k − 1)-extremal meet-subsemilattice. If L[K] is B(k)free, then it is an (n, k)-extremal lattice. Proof. Proposition 5 guarantees that L[K] is inde.ed a lattice. As in the proof of Proposition 6, we have that J (L[K]) = J (L) ∪ {0K } and in particular, L[K] has at most n join-irreducible elements. The claim that L[K] has f (n, k) elements follows from Proposition 3.
It is clear now how (n, 2)-extremal lattices can be obtained by doubling a trivial meet-subsemilattice of an (n − 1, 2)-extremal lattice. The succeeding propositions and lemmas aim particularly towards a generalization of this operation: the doubling of topped, (n − 1, k − 1)-extremal meet-subsemilattices inside (n − 1, k)-extremal lattices, yielding (n, k)-extremal lattices for k ≥ 3. Proposition 8. Suppose that L is an (n, k)-extremal lattice. Then, for every S, T ⊆ J (L) with |S|, |T | ≤ k − 1:
_ S = _ T ⇒ S = T.
Moreover, if k ≥ 2 then |J (L)| = n.
Proof. We may suppose k ≥ 2 since the assertion holds trivially for k = 1. Lemma 2 guarantees that every element x of L has a representation of size at most k − 1. Therefore L = {W S | S ⊆ J (L), |S| ≤ k − 1}. Because of k ≥ 2 and the fact that | | = f (n, k) is also the number of subsets of [n] having at
L most k − 1 elements, one has |J (L)| ≥ n. In fact equality must hold, because L has at most n join-irreducible elements. As a consequence of |J (L)| = n and | | = f (n, k), we have that no two sets S, T ⊆ J (L) with S 6= T may lead to the L same supremum W S = W T .
Chains are the only extremal lattices which are not atomistic, as a consequence of the next lemma.
Lemma 3. Suppose that L is an (n, k)-extremal lattice with k ≥ 3. Then L is atomistic and meet-distributive. In particular, the length of L equals the number of its atoms and there exists an atom which is an extremal point of 1L. Proof. If L were not atomistic, there would exist two comparable join-irreducible elements, say, x, y with x < y. But then x ∨ y = y, which contradicts Proposition 8. Suppose that L is not meet-distributive and take x, y ∈ L with x ≺ y such that Ay \ Ax has at least two elements. Clearly x 6= 0L and, therefore, Ax 6= ∅. Let u, v ∈ Ay \ Ax be any two distinct elements. From u ∈/ Ax follows that x < x ∨ u ≤ y which, in turn, implies x ∨ u = y. Similarly, v ∈/ Ax implies x < x ∨ v ≤ y which, in turn, implies x ∨ v = y. Let a ∈ Ax. Now, a ≤ x and x||u imply a ∨ u = x ∨ u = y, as well as a ≤ x and x||v imply a ∨ v = x ∨ v = y. We obtain a ∨ u = a ∨ v, contradicting Proposition 8. Choosing a maximal chain x0 ≺ x1 ≺ . . . ≺ xl in L and noticing that the sizes of the sets Axi grow by exactly one element make the two remaining claims clear.
Lemma 4 shows that non-trivial, extremal meet-subsemilattices are always cover-preserving and topped. These two properties will be useful to assure that a doubling L[K] is a meet-distributive lattice. Lemma 4. Let L be an (n, k)-extremal lattice with k ≥ 3 and suppose that K is an (n, k − 1)-extremal subsemilattice of L. Then, K is cover-preserving and topped. If k ≥ 4, then K and L are atomistic with A(K) = A(L).
Proof. In case that k = 3 then K is B(2)-free, that is, K is a chain. By Lemma 3, K must be a maximal chain in order to have Pi1=0 ni = n + 1 elements. Hence, 1K = 1L. The maximality of K guarantees that K is cover-preserving. Now, suppose that k ≥ 4. Again by Lemma 3, we have that both K and L are atomistic. Since K has n atoms, 0K must be covered by n elements in L. But this is possible only if 0L = 0K , because L also has n atoms. This forces A(K) = A(L) as well as 1L ∈ K, because 1L is the only element that upper bounds each a ∈ A(K). To prove that K is cover-preserving, we apply Lemma 3 twice, obtaining |Ay \ Ax| = 1 for every x, y ∈ K with x ≺K y as well as |Ay \ Ax| = 1 for every x, y ∈ L with x ≺L y. Both conditions hold simultaneously only if the implication x ≺K y ⇒ x ≺L y holds, i.e., if K is cover-preserving.
A complete meet-embedding is a meet-embedding which preserves arbitrary meets, including V ∅. As a consequence, the greatest element of one lattice gets mapped to the greatest element of the other. Images of complete meetembeddings are topped meet-subsemilattices. This notion is required for the following simple fact, which aids us in the construction of sequences of (n, k)extremal lattices with fixed n and growing k. In Proposition 9, the symbol K[J ] (for instance) means actually the doubling of the image of J under the corresponding embedding.
Proposition 9. Suppose that J , K and L are lattices with complete meet-embeddings E1 : J → K and E2 : K → L. Then, there exists a complete meet-embedding from K[J ] into L[K].
Proof. The fact that K[J ] and L[K] are latt.ices com.es from Proposition 5. Of course, there is an induced embedding from J into K, but for which we will use the same.symbol E1. The mapping E3 : K[J ] → L[K] defined by E3(x) = E1(x) for x ∈ J and E3(x) = E2(x) for x ∈ K may be checked as being a complete meet-embedding.
As mentioned after Proposition 7, we will make use of an operation which doubles an extremal meet-subsemilattice of an extremal lattice. The next theorem shows that the lattice produced by this operation is indeed extremal. Theorem 3. Let L be an (n − 1, k)-extremal lattice with n ≥ 2 and k ≥ 3 and suppose that K is an (n − 1, k − 1)-extremal meet-subsemilattice of L. Then, L[K] is an (n, k)-extremal lattice.
Proof. Lemma 3 guarantees that L is atomistic and meet-distributive. Moreover, Lemma 4 guarantees that K is cover-preserving and topped, so that, in particular, L[K] is a meet-distributive lattice, as a consequence of Proposition 6. To prove that L[K] is (n, k)-extremal it is sufficient to show that L[K] is B(k)-free, because of Proposition 7. We will do so by proving that every element of L[K] has a representation through join-irreducibles of size at most k − 1. This indeed suffices because L[K] is meet-distributive, so that Lemma 2 may be applied.
.
Observe that J (L[K]) = A(L) ∪ 0K , since L is atomistic.
Suppose that k = 3. In this case K is a chain, and a maximal one because of Lemma 4. Let x ∈ L[K]. If x ∈ L, then Lemma 2 implies that x = W S for some S ⊆ A(L), |S| ≤ 2 and the same representation may be used in L[K]. If x ∈/ L, . . then x = y = y ∨ 0K for some y ∈ K. If y ∈ A(L), we are.done. Otherwise, take z, w ∈ A(L) such that z ∨ w = y and thus x = z ∨ w ∨ 0K . Exactly one among z and .w belong. to K. Without.loss of ge.nerality, let it be z. Then, it is clear that 0K ≺.z ∨ 0K and that z ∨ 0K .< w ∨ 0K ,.since there exists only one element covering 0K . Hence, x = z ∨ w ∨ 0K = w ∨ 0K .
Suppose that k ≥ 4. As noted after Proposition 5 one has that K is, by itself, a lattice. Moreover, Lemma 4 guarantees that K is atomistic with A(L) = A(K). Let x ∈ L[K]. If x ∈ L then, in L, x = W S for some S ⊆ A(L) ⊆ J (L[K]) with |S| ≤ k − 1, because of Lemma 2 and the fact that L is B(k)-free. Of co.urse, S . . is also a representation of x in L[K]. If x ∈/ L, then x = y for some y ∈ K. Since K is B(k − 1)-free, it follows that, in K, y = W S for some S ⊆ A(K) ⊆ J (L[K]) with |S| ≤ k −.2, once again as a consequence of Lemma 2. Clearly, in L[K], . . one has y. = W S = 0K ∨ W S, where the last equality follows from the fact that . . z = z ∨ 0K for every z ∈ S. Thus, we have a representation of y = x through no more than k − 1 join-irreducible elements of L[K].
Corollary 1 describes how (n, k)-extremal lattices can be non-deterministically constructed. In particular, the upper bound present in Theorem 2 is the best possible.
Corollary 1. For every n and k, there exists at least one (n, k)-extremal lattice. Proof. Define a partial function Φ satisfying Φ : N∗ × N∗ → L (n, k) 7→ ([n], ⊆), if k = 1. ({∅, {1}}, ⊆), if k ≥ 2, n = 1.
Φ(n − 1, k)[E (Φ(n − 1, k − 1))], if n, k ≥ 2 and there exists a complete meet-embedding E : Φ(n − 1, k − 1) → Φ(n − 1, k). where L is the class of all lattices. We prove by induction on n that Φ(n, k) is a total function. The cases n = 1 and n = 2 are trivial. Let n ∈ N with n ≥ 3 and suppose that Φ(n − 1, k) is defined for every k ∈ N∗. Let k ∈ N, k ≥ 2. By the induction hypothesis, the values Φ(n − 1, k) and Φ(n − 1, k − 1) are defined. If k = 2, then Φ(n − 1, k − 1) is a trivial lattice and the existence of a complete meet-embedding into Φ(n − 1, k) is clear and, thereby, Φ(n, k) is defined. We therefore assume k ≥ 3. By the definition of Φ, one has that Φ(n − 1, k) = Φ(n − 2, k)[E (Φ(n−2, k−1))] and that Φ(n−1, k−1) = Φ(n−2, k−1)[F (Φ(n−2, k−2))] for some pair of complete meet-embeddings E and F . Applying Proposition 9 with Φ(n − 2, k − 2), Φ(n − 2, k − 1) and Φ(n − 2, k) results in the existence of a complete meet-embedding G : Φ(n − 1, k − 1) → Φ(n − 1, k), which yields that Φ(n, k) is defined. Since k is arbitrary, every Φ(n, k) is defined. The (n, k)extremality of each lattice can be proved by induction on n as well and by invoking Theorem 3.
Figure 3 depicts the diagrams of nine (n, k)-extremal lattices which are constructible by Corollary 1. It is true that, in general, (n, k)-extremal lattices are not unique up to isomorphism: note that the (3, 3) and (4, 3)-extremal lattices in Figure 3 are also present in Figure 2 as the lattices C2 and C3. The lattice C4, depicted in that same figure, is a (4, 3)-extremal lattice which is not isomorphic to C3. We shall, however, show in the next section that every extremal lattice arises from the construction described in Corollary 1. 6
In the last section, we constructed lattices whose sizes are exactly the upper bound present in Theorem 2. In this section, we will show that every lattice meeting those requirements must be obtained from our construction. Lemma 5. Let L be an atomistic lattice, a an atom and c a coatom with Ac = a . Then, the mapping x 7−→E c ∧ x is a complete meet-embedding of ↑ a A(L) \ { } into ↓ c such that E (x) ≺ x for every x ∈ ↑ a.
Proof. The fact that E preserves non-empty meets is clear, since c is a fixed element. Also, 1L is mapped to c = 1↓c, so that E preserves arbitrary meets. Note that
AE(x) = Ac∧x = Ax ∩ Ac = Ax \ {a}.
Hence, E (x) ≺ x as well as E (x) ∨ a = x. The latter implies injectivity.
The next theorem shows that every extremal lattice is constructible by the process described in Corollary 1, and can be seen as a converse of that result. Theorem 4. Let L be an (n, k)-extremal lattice with k ≥ 3. Then, L = J ∪˙ K where J is an (n − 1, k)-extremal lattice and K is an (n − 1, k − 1)-extremal lattice. Moreover, there exists a complete meet-embedding E : K → J such that E (x) ≺ x for every x ∈ K. In particular, L ∼= J [E (K)].
Proof. From Lemma 3, one has that L is atomistic and we may take an atom a which is an extremal point of 1L, that is, A(L) \ {a} = Ac with c being a coatom of L. Consider the lattices J =↓ c and K =↑ a. Observe that L = J ∪˙ K and let E : K → J be a complete meet-embedding provided by Lemma 5. Clearly, J has n − 1 atoms and is B(k)-free, therefore, |J | ≤ f (n − 1, k). Moreover, K must be B(k − 1)-free: indeed, if there existed B ∼= B(k − 1) inside K, then Fig. 3: Diagrams of (n, k)-extremal lattices with 2 ≤ n, k ≤ 4. Elements shaded in black represent the doubled (n − 1, k − 1)-extremal lattice.
B ∪ E (B) would be a boolean lattice with k atoms inside J , which is impossible. The lattice K has at most n − 1 atoms, and consequently |K| ≤ f (n − 1, k − 1), since the function n 7→ Pik=−01 ni is monotonic increasing. Now, we have that |J | + |K| = | | = f (n, k) = f (n − 1, k) + f (n − 1, k − 1), where the last equality
L follows from Proposition 3. Since |J | ≤ f (n−1, k) and |K| ≤ f (n−1, k −1), those two inequalities must hold with equality. Therefore, J and K are, respectively, (n − 1, k) and (n − 1, k − 1)-extremal. 7
We showed an upper bound for the number of minimal generators of a context
which is sharp. Extremal lattices were constructed and also characterized. The
rˆole played by contranominal scales in formal contexts may be seen as analogous
as that of cliques in simple graphs, when one considers extremality with respect
to the number of edges. The Sauer-Shelah Lemma [
We want to deeply thank Bernhard Ganter for the invaluable feedback and fruitful discussions.