=Paper=
{{Paper
|id=Vol-1466/paper06
|storemode=property
|title=Why Concept Lattices Are Large - Extremal Theory for the Number of Minimal Generators and Formal Concepts
|pdfUrl=https://ceur-ws.org/Vol-1466/paper06.pdf
|volume=Vol-1466
|authors=Alexandre Albano, Bogdan Chornomaz
|dblpUrl=https://dblp.org/rec/conf/cla/AlbanoC15
}}
==Why Concept Lattices Are Large - Extremal Theory for the Number of Minimal Generators and Formal Concepts==
https://ceur-ws.org/Vol-1466/paper06.pdf
Why concept lattices are large
Extremal theory for the number of
minimal generators and formal concepts
Alexandre Albano1 and Bogdan Chornomaz2
1
Technische Universität Dresden
2
V.N. Karazin Kharkiv National University
Abstract. 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 contranom-
inal scales larger than a given size. Extremal contexts are constructed
which meet this bound exactly. They are completely classified.
1 Introduction
The primitive data model of Formal Concept Analysis is that of a formal context,
which is unfolded into a concept lattice for further analysis. It is well known that
concept lattices may be exponentially larger than the contexts which gave rise
to them. An obvious example is the boolean lattice B(k), having 2k elements,
the standard context of which is the k × k contranominal scale Nc (k). This is not
the only example of contexts having large associated concept lattices: indeed, the
lattice of any subcontext is embeddable in the lattice of the whole context [4],
which means that contexts having large contranominal scales as subcontexts
necessarily have large concept lattices as well. Those considerations induce one
natural question, namely, whether there are other reasons for a concept lattice
to be large. As it will be shown in this paper, the answer is no.
The structure of the paper is as follows. Our starting point is a known up-
per bound for the number of concepts, which we improve using the language of
minimal generators. Then, we show that our result is the best possible by con-
structing lattices which attain exactly the improved upper bound. These lattices,
i.e., the extremal lattices, are characterized.
2 Fundamentals
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 at-
tributes), that is, the context ([k], [k], 6=), where [k] := {1, 2, . . . , k}. The expres-
sion 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
c paper author(s), 2015. Published in Sadok Ben Yahia, Jan Konecny (Eds.): CLA
2015, pp. 73–86, ISBN 978–2–9544948–0–7, Blaise Pascal University, LIMOS
laboratory, Clermont-Ferrand, 2015. Copying permitted only for private and
academic purposes.
74 Alexandre Albano and Bogdan Chornomaz
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,
c
B(N (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 [4]
one has that K is Nc (k)-free whenever B(K) is B(k)-free. The converse is also
true and is, in fact, the content of our first proposition. An example of a context
which has Nc (3) as a subcontext along with its concept lattice is depicted in
Figure 1. One may observe that the context is Nc (4)-free, since its lattice has
ten concepts (and would have at least sixteen otherwise).
m n o p q
g ××
h × ×× o n m
i ×× ×
j × ××
k ×
g h i
Fig. 1: A context K with Nc (3) ≤ K and its concept lattice. The object and attribute
concepts belonging to the B(3) suborder are indicated on the diagram.
We denote by J(L) and M (L), respectively, the set of completely join-
irreducible 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,W similarly, by Jl the set J(L)∩ ↓ l. A complete lattice L is called atomistic if
x = 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, de-
note 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
Why concept lattices are large 75
gi Imj 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 gi Imj ⇔ 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 S 00 ) if T 00 6= S 00 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 [5]:
more precisely, this counting problem is #P-complete. However, there are results
which establish upper bounds for the number of concepts: see for example [1–3,
6, 7].
3 The upper bound
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 [6]). Let K = (G, M, I) be a Nc (k)-free context. Then,
|B(K)| ≤ (|G||M |)k−1 + 1.
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= S 0 .
Proof. We will show the two equivalent contrapositions. If (S \ {g})0 = S 0 , then,
of course, (S \ {g})00 = S 00 , 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 = S 00 . Note that T 00 = S 00 implies T 0 = S 0 . Let g ∈ S \ T . On one hand,
(S \ {g}) ⊆ S implies (S \ {g})0 ⊇ S 0 . On the other hand, (S \ {g}) ⊇ T implies
(S \ {g})0 ⊆ T 0 = S 0 . Combining both yields (S \ {g})0 = S 0 .
The next proposition relates minimal generators and contranominal scales.
76 Alexandre Albano and Bogdan Chornomaz
Lemma 1. Let K = (G, M, I) be a context and A ⊆ G. There exists a contra-
nominal scale K1 ≤ K having A as its object set if and only if A is a minimal
generator. In particular, if G is finite:
max{|A| : A is a minimal generator} = max{k ∈ N : Nc (k) ≤ K}.
A⊆G
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 ∈/ S 0 . Moreover, g ∈ (S \ {g})0 . This amounts to (S \ {g})0 ) S 0 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:
X
k−1
|G|
|B(K)| ≤ |MinGen(K)| ≤ .
i=0
i
In particular, if k ≤ |G|
2 :
|G|k−1
|B(K)| ≤ k · .
(k − 1)!
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:
X
k−1
n
f (n, k) := .
i=0
i
The upper bound in Theorem 2 for f (n, k) gets worse as k gets close to |G|
2 .
Tighter upper bounds for the sum of binomial coefficients may be found in [9].
4 Sharpness: preparatory results
The following property of f (n, k) is needed for the next two sections.
Why concept lattices are large 77
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 −
Pk−1 n−1 Pk−2 n−1 Pk−1 Pk−1 n−1
1, k − 1) = i=0 i + j=0 j = 1 + i=1 n−1 i−1 + j=1 j =
Pk−1 n
1 + i=1 i = f (n, k).
Consider a finite lattice L. It is well known that W every element x ∈ L is the
supremum of some subset of J(L): for example, x = 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 W a representation of x). A
representation S ⊆ J(L) of x is called irredundant if (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 W x must contain every
extremal point z of x since, in this case, the supremum (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 ex-
actly 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 [4], which actually gives information about the unique irredundant repre-
sentation as well: a finite lattice L is meet-distributive if and only if for every
x ∈ L the set Ex of all extremal points of x is a representation of x (and Ex is,
therefore, the unique irredundant representation of x, since every representation
of x must contain Ex ). Proposition 4 provides a characteristic property for the
finite case which will be used in our constructions.
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 [4].
Let x ∈ L and define Ex = {z ∈ Jx | z is an extremal point of x}. We now show
that ii) implies iii). Let y ∈ L with y < x. This implies Jy ( Jx . TheWset Jy
does not contain Ex , because this would force y ≥ W x. Therefore, y = Jy is
upper bounded by some element in the set U = { (Jx \ {z}) | z ∈ Ex } (note
that x ∈/ U ). Hence, every lower neighbor of x has a representation of the W
form
(Jx \ {z}) with z ∈ Ex . Now we show that iii) implies ii). Define y = Ex
and suppose by contradiction that y < x. Then, there exists an element z such
78 Alexandre Albano and Bogdan Chornomaz
that y ≤ z ≺ x and Jz ⊇ Ex . But then, z ≺ x implies Jx \ Jz = {w} for some
w ∈ J(L), which means that w is an extremal point of x. This contradicts the
fact that Ex contains all extremal points of x.
The next lemma will be useful in Section 5, when we shall change the per-
spective 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
W of A. Then, by Lemma 1, it follows that |S| ≤ k − 1. Since A = S 00 =
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 S 00 of L. By
Proposition 4, S is the unique irredundant representation of S 00 . Therefore, S 00
cannot be expressed as the supremum of fewer than k join-irreducible elements.
5 Sharpness: construction of extremal lattices
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 set and K ⊆ L. The doubling of 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}.
Why concept lattices are large 79
.
We will employ the notation x to denote the image under doubling of an
. .
element x ∈ K. Note 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([2]), resulting in C2 . The (a
fortiori ) closure systems C3 and C4 are obtained by doubling, respectively, the
chains {∅, {3}, {2, 3}, {1, 2, 3}} and {∅, {2}, {2, 3}, {1, 2, 3}} inside C2 .
123
12 12 23
1 2 1 2 3
C1 C2
1234 1234
123 234 123 234
12 23 34 12 23 24
1 2 3 4 1 2 3 4
C3 C4
Fig. 2: Doubling chains inside closure systems
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. Then y = z with z ∈ K. We have that x ∧ y = x ∧ z ∈ L ⊆ L[K] because of
. .
x 0K and
V y = z ∨ 0K . For the supremum, set S = {w ∈ K | w ≥ x, w ≥ z}
and u = 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
80 Alexandre Albano and Bogdan Chornomaz
.
bound of x and z which belongs to K. Therefore, u is the least upper bound of
. . .
x and y, because of 0K u and y = z ∨ 0K . The remaining case is x, y ∈ K
. .
for which, clearly x ∧ y exists. Moreover, writing x = t, yV= z with t, z ∈ K
and setting S = {w ∈ K | w ≥ t, w ≥ z} as well as u = S make clear that
.
u = x ∨ y.
When extrinsically considered, topped meet-subsemilattices are lattices. This
is compatible with the proof of Proposition 5, where the supremum and 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 meet-
distributivity 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 one 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
0
of L. Let x, y ∈ L[K] with x ≺L[K] y. We use J(·) to denote our J-notation
in L[K] and J(·) in L. If x, y ∈ L, then clearly Jy = Jy and Jx0 = Jx , which
0
results in |Jy0 \ Jx0 | = |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 Jx0 = Jz ∪ {0K } and Jy0 = Jw ∪ {0K }, which yields |Jy0 \ Jx0 | = 1. For the
remaining case, one has necessarily x ∈ L and y ∈
. . / L. In these conditions, x ≺ y
results in y = x and, therefore, Jy0 = Jx0 ∪ {0K }, implying |Jy0 \ Jx0 | = 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 meet-
subsemilattice ↑ 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.
Why concept lattices are large 81
Proof. Proposition 5 guarantees that L[K] is indeed 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 opera-
tion: 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 W element x of L has a representation of size at
most k − 1. Therefore L = { S | S ⊆ J(L), |S| ≤ k − 1}. Because of k ≥ 2
and the fact that |L| = f (n, k) is also the number of subsets of [n] having at
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
|L| = f (n, k), we W W no two sets S, T ⊆ J(L) with S 6= T may lead to the
have that
same supremum S = T .
Chains are the only extremal lattices which are not atomistic, as a conse-
quence 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 Proposi-
tion 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.
82 Alexandre Albano and Bogdan Chornomaz
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,
P1
K must be a maximal chain in order to have i=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 atom-
istic. 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, ob-
taining |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
V is a meet-embedding which preserves arbitrary
meets, including ∅. As a consequence, the greatest element of one lattice
gets mapped to the greatest element of the other. Images of complete meet-
embeddings 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 corre-
sponding 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 lattices comes 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 theo-
rem 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 partic-
ular, 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,
Why concept lattices are large 83
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 W because of
Lemma 4. Let x ∈ L[K]. If x ∈ L, then Lemma 2 implies that x = 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 generality, 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 guaranteesWthat K is atomistic with A(L) = A(K).
Let x ∈ L[K]. If x ∈ L then, in L, x = 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 course, S
is also a representation of x in L[K]. If x ∈
. . .
/ L,Wthen x = y for some y ∈ K. Since
K is B(k − 1)-free, it follows that, in K, y = 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],
. W. . W
one has y = S = 0K ∨ 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], ⊆), if k = 1.
({∅, {1}}, ⊆), if k ≥ 2, n = 1. ,
(n, k) 7→ Φ(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 −
84 Alexandre Albano and Bogdan Chornomaz
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 con-
structible 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 Characterization of extremal lattices
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 =
E
A(L) \ {a}. Then, the mapping x 7− → c ∧ x is a complete meet-embedding of ↑ a
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
Why concept lattices are large 85
k=2
k=3
k=4
n=2 n=3 n=4
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),
Pk−1
since the function n 7→ i=0 ni is monotonic increasing. Now, we have that
|J| + |K| = |L| = f (n, k) = f (n − 1, k) + f (n − 1, k − 1), where the last equality
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 Conclusion and related work
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ôle played by contranominal scales in formal contexts may be seen as analogous
86 Alexandre Albano and Bogdan Chornomaz
as that of cliques in simple graphs, when one considers extremality with respect
to the number of edges. The Sauer-Shelah Lemma [8] provides an upper bound
which is similar to that of Theorem 2. This is not a coincidence, because it can
be shown, not without some effort, that the condition of a concept lattice being
B(k)-free is equivalent to the family of its extents not shattering a set of size
k. As for the sharpness of the bound (which we prove in Section 5), in our case
it is non-trivial, whereas the sharpness for the result of Sauer and Shelah is
immediate.
8 Acknowledgements
We want to deeply thank Bernhard Ganter for the invaluable feedback and fruit-
ful discussions.
References
1. Alexandre Albano. Upper bound for the number of concepts of contranominal-scale
free contexts. In Formal Concept Analysis - 12th International Conference, ICFCA
2014, Cluj-Napoca, Romania, June 10-13, 2014. Proceedings, pages 44–53, 2014.
2. Alexandre Albano and Alair Pereira do Lago. A convexity upper bound for the
number of maximal bicliques of a bipartite graph. Discrete Applied Mathematics,
165(0):12 – 24, 2014. 10th Cologne/Twente Workshop on Graphs and Combinatorial
Optimization (CTW 2011).
3. David Eppstein. Arboricity and bipartite subgraph listing algorithms. Information
Processing Letters, 51(4):207–211, 1994.
4. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foun-
dations. Springer, Berlin-Heidelberg, 1999.
5. Sergei O. Kuznetsov. On computing the size of a lattice and related decision prob-
lems. Order, 18(4):313–321, 2001.
6. Erich Prisner. Bicliques in graphs I: bounds on their number. Combinatorica,
20(1):109–117, 2000.
7. Dieter Schütt. Abschätzungen für die Anzahl der Begriffe von Kontexten. Master’s
thesis, TH Darmstadt, 1987.
8. Saharon Shelah. A combinatorial problem; stability and order for models and the-
ories in infinitary languages. Pacific J. Math., 41(1):247–261, 1972.
9. Thomas Worsch. Lower and upper bounds for (sums of) binomial coefficients, 1994.