This article treats four optimization problems on posets and applies the results to Formal Concept Analysis. The cover-, packing-, isolation- and blocking problem are investigated. Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). Published in Francisco J. Valverde-Albacete, Martin Trnecka (Eds.): Proceedings of the 15th International Conference on Concept Lattices and Their Applications, CLA 2020, pp. 185{196, 2020.
R∈R
In [
Rec(K), I = [ R} .
This optimization problem on formal contexts can be translated to the order
2-dimension of the concept lattice of the complementary context (see [
I, ∀ (R ∈ Rec(K)) : #(I ∩ R) ≤ 1} .
It always holds that ri(K) ≤ rc(K) and in case of equality there are
consequences for the tensor product of complete lattices (see [
Rec(K), ∀ (R1, R2 ∈ R ), R1 ̸= R2 : R1 ∩ R2 = ∅} ,
I, ∀ (R ∈ Rec(K)) ∃ ((g, m) ∈ I ) : (g, m) ∈ R} .
Similar, to the cover and isolation number, it holds that rp(K) ≤ rb(K).
This paper treats the above defined optimization problems on formal contexts. Therefore, Section 2 provides necessary definitions from formal concept analysis. Section 3 analyses the optimization problems and their mutual relationships. This is done in a more general setting based on posets. This abstraction is the main content of this paper in it’s own right. Concrete examples from Formal Concept Analysis will be presented along the way. The last section provides a conclusion. 2
In this section, we will provide the facts from formal concept analysis that we
will use in the sequel. All results can be found in [
A formal context is a triple K = (G, M, I), where the incidence I ⊆ G × M is a binary relation. For A ⊆ G and B ⊆ M , we define two derivation operators: AI := { m ∈ M | ∀ (a ∈ A) : (a, m) ∈ I} = \ { a} I , a∈ A BI := { g ∈ G| ∀ (b ∈ B) : (g, b) ∈ I} = \ { b} I .
b∈ B
If AI = B and BI = A, the pair (A, B) is called a formal concept and for non empty A and B the cartesian product A × B is a maximal rectangle of K. We denote the set of all maximal rectangles by Rec(K). The set of all formal concepts of K is denoted by B(K) and defines the concept lattice B(K), via the order (A1, B1) ≤ (A2, B2) :⇒⇐ A1 ⊆ A2. The complementary context is defined as Kc = (G, M, Ic) := (G, M, (G × M ) − I). Furthermore, two special formal concepts of importance are the object concepts γ (g) := ({ g} II , { g} I ) and attribute concepts µ (m) = ({ m} I , { m} II ).
The order 2-dimension of a concept lattice, dim2(B(K)), is the smallest n such that an order embedding, that is an order preserving and reflecting map, from B(K) to the powerset lattice 2X := (2X , ⊆ ) of an n-element set X exists.
A Ferrers relation is a relation F ⊆ G × M such that (g, m), (h, n) ∈ F implies (g, n) ∈ F or (h, m) ∈ F . This is equivalent to B(G, M, F ) being a chain. The length l of F is defined as l(F ) = | B(G, M, F )| − 1. For a context K its Ferrers 2-dimension, fdim2(K), is the smallest number of Ferrers relations Ft, t ∈ T with l(Ft) < 2, so that I = Tt∈ T Ft.
The above defined dimensions are equal and are related to the rectangle cover number via the complementary context, that is:
rc(K) = fdim2(Kc) = dim2(B(Kc)).
For two contexts K1 = (G1, M1, I1) and K2 = (G2, M2, I2), we use notation
from [
(g, m) ∈ I1 and (h, n) ∈ I2.
Let P := (P, ≤ ) be a finite partially ordered set , i.e, the relation ≤ is reflexive, antisymmetric and transitive. For any R ⊆ X × Y , the relation Rop is defined as Rop := { (y, x) | (x, y) ∈ R} . With that, the dual of P is defined as:
Pop = (P, ≥ ) := (P, ≤ op).
For p ∈ P , we define the principal ideal (p] := { x ∈ P | x ≤ p} as well as the principal filter [p) := { x ∈ P | p ≤ x} .
Finally, a remark about notation. We will express “there exists at most one” with the quantifier ∃ ≤ 1. For symmetry reasons, we will denote “there exists at least one” with the quantifier ∃ ≥ 1. 3.1
Basic Definitions We define four relations CovP, IsolP, BlockP, PackP ⊆ 2P × 2P : (A, B) ∈ CovP :⇒⇐ ∀ (A, B) ∈ IsolP :⇒⇐ ∀ (A, B) ∈ BlockP :⇒⇐ ∀ (A, B) ∈ PackP :⇒⇐ ∀ (a ∈ A) ∃ ≥ 1(b ∈ B) : a ≤ b, (b ∈ B) ∃ ≤ 1(a ∈ A) : a ≤ b, (b ∈ B) ∃ ≥ 1(a ∈ A) : a ≤ b, (a ∈ A) ∃ ≤ 1(b ∈ B) : a ≤ b.
covers A, or that A is covered by B. Relation IsolP is expressed as A is isolated w.r.t. B.
blocks B, or that B is blocked by A. Relation PackP is expressed as B is packed w.r.t. A.
Again, the terminology of a packing is well known. The less well established
term blocking is for example used in geometry (see [
Via a "twofold dual" the relations can be transformed into each other. Proposition 1. It holds that: 1. IsolP = (PackPop )op and PackP = (IsolPop )op, 2. CovP = (BlockPop )op and BlockP = (CovPop )op.
Proof.
(A, B) ∈ IsolP ⇔ ∀
(a ∈ A) ∃ ≤ 1(b ∈ B) : b ≥ a ⇔ (B, A) ∈ PackPop .
The other equations can be shown similarly.
covP(A, B) := min{ #B0 | B0 ⊆ B : (A, B0) ∈ CovP} .
We call a subset B0 ⊆ B, such that (A, B0) ∈ CovP and #B0 = covP(A, B), a minimal cover of A.
Definition 4. For (A, B) ∈ BlockP, the blocking number of (A, B) is defined as blockP(A, B) := min{ #A0 | A0 ⊆ A : (A0, B) ∈ BlockP} .
We call a subset A0 ⊆ A, such that (A0, B) ∈ BlockP and #A0 = blockP(A, B), a minimal blocking set.
Definition 5. The isolation number and the packing number of (A, B) are defined as:
isolP(A, B) := max{ #A0 | A0 ⊆ A : (A0, B) ∈ IsolP} , packP(A, B) := max{ #B0 | B0 ⊆ B : (A, B0) ∈ PackP} .
We call A0 ⊆ A, with (A0, B) ∈ IsolP and #A0 = isolP(A, B), a maximal isolated set w.r.t. B, and B0 ⊆ B, with (A, B0) ∈ PackP and #B0 = packP(A, B), a maximal packing w.r.t. A.
Note that, contrary to the cover- and blocking number, the isolation- and packing number can be defined without any condition on (A, B). For example, to ifnd a minimal cover, we have to claim that B covers A. Otherwise there couldn’t be a solution to the cover problem. Since it always holds that (∅ , B) ∈ IsolP and (A, ∅ ) ∈ PackP, a valid isolation- and packing number always exists. Example 1. Let K = (G, M, I) be a formal context. If we choose P = 2G× M , A = { (g, m)} | (g, m) ∈ I} = I1 and B = Rec(K), we can express the four optimization problems from Section 1 in the abstract poset framework.
rc(K) = covP(A, B), ri(K) = isolP(A, B), rp(K) = packP(A, B), rb(K) = blockP(A, B).
Proposition 2. Let (A, B) ∈ CovP. It holds that isolP(A, B) ≤ covP(A, B). Proof. Let A0 be a maximal isolated set w.r.t. B, that is A0 is a maximal subset of A such that ∀ (b ∈ B) ∃ ≤ 1(a ∈ A0) : a ≤ b. Assuming that B0 is a minimal cover of A, with #B0 < #A0, there exists a1, a2 ∈ A0, with a1 ̸= a2, a1 ≤ b and a2 ≤ b for some b ∈ B0. This contradicts A0 being isolated w.r.t. B. ⊔⊓ Proposition 3. Let (A, B) ∈ BlockP. It holds that packP(A, B) ≤ blockP(A, B). Proof. Let packP(A, B) > blockP(A, B). From Proposition 1 , it follows that isolPop (B, A) > covPop (B, A), which is a contradiction to Proposition 2 . ⊔⊓ 3.2
Behaviour under Order Preserving/Reversing Maps In this subsection, we will explore the behaviour of the four optimization problems under poset mappings from P to Q. Especially, we are interested in maps with the following properties.
Definition 6. Let A, B ⊆ P. A map φ : P → Q: – preserves order between A and B :⇔ ∀ – reverses order between A and B :⇔ ∀ – reflects order between A and B :⇔ ∀ – deflects order between A and B :⇔ ∀ (a ∈ A, b ∈ B) : a ≤ b ⇒ φ (a) ≤ φ (b), (a ∈ A, b ∈ B) : a ≤ b ⇒ φ (b) ≤ φ (a), (a ∈ A, b ∈ B) : a ≤ b ⇐ φ (a) ≤ φ (b), (a ∈ A, b ∈ B) : a ≤ b ⇐ φ (b) ≤ φ (a).
By means of such maps, it is possible to relate the four relations to each other.
order reversing, between A and B. It holds that:
(A, B) ∈ CovP ⇒ (φ [A], φ [B]) ∈ CovQ and (ψ [B], ψ [A]) ∈ BlockQ .
Similarly, this statement holds if we swap Cov and Block.
Proof. Let (A, B) ∈ CovP. The statement, for all a˜ ∈ φ [A], there exists at least one ˜b ∈ φ [B] with a˜ ≤ ˜b, is true, since there exists a ∈ A and b ∈ B such that φ (a) = a˜ and φ (b) = ˜b. Hence, a˜ = φ (a) ≤ φ (b) = ˜b.
Considering ψ as an order preserving map from P to Qop, it follows that (ψ [A], ψ [B]) ∈ CovQop . Proposition 1 implies that (ψ [B], ψ [A]) ∈ BlockQ. ⊔⊓
order deflecting, between A and B. It holds that:
(A, B) ∈ IsolP ⇒ (φ [A], φ [B]) ∈ IsolQ and (ψ [B], ψ [A]) ∈ PackQ .
Similarly, this statement holds if we swap Isol and Pack.
Proof. Let (A, B) ∈ IsolP. The statement, for all ˜b ∈ φ [B], there exists at most one a˜ ∈ φ [A] with a˜ ≤ ˜b, is true, since φ reflects order. There can not be any “new edges created by φ ” betweenφ [A] and φ [B].
Considering ψ as an order reflecting map from P to Qop, it follows that (ψ [A], ψ [B]) ∈ IsolQop . Proposition 1 implies that (ψ [B], ψ [A]) ∈ PackQ. ⊔⊓ Combining Proposition 4 and 5, we get:
(A, B) ∈ CovP ⇔ (φ [A], φ [B]) ∈ CovQ and (ψ [B], ψ [A]) ∈ BlockQ, (A, B) ∈ IsolP ⇔ (φ [A], φ [B]) ∈ IsolQ and (ψ [B], ψ [A]) ∈ PackQ .
Similarly, this statement holds if we swap Cov and Block, or, Isol and Pack. Proof. The proof either follows or is analogous to the ones of Proposition 4 and 5. Exemplary, we treat (φ [A], φ [B]) ∈ CovQ ⇒ (A, B) ∈ CovP.
It has to hold that for all a ∈ A there is at least one b ∈ B with a ≤ b. To conclude this from (φ [A], φ [B]) ∈ CovQ, the map φ has to be order reflecting between A and B. ⊔⊓
Finally, the next theorem describes the behaviour of the four optimization problems under certain poset maps.
covP(A, B) = covQ(φ [A], φ [B]) = blockQ(ψ [B], ψ [A]). Generally, it holds that:
isolP(A, B) = isolQ(φ [A], φ [B]) = packQ(ψ [B], ψ [A]).
as well as isol and pack.
Proof. We prove that covP(A, B) = covQ(φ [A], φ [B]). The other equations can be shown analogously.
Let B0 ⊆ B be a minimal cover of A. Since it holds that (φ [A], φ [B0]) ∈ CovQ (Proposition 6), it follows that covQ(φ [A], φ [B]) ≤ covP(A, B). Conversely, let B˜0 ⊆ φ [B] be a minimal cover of φ [A]. There exists a subset B0 ⊆ B such that φ [B0] = B˜0 and #B0 = #B˜0. It holds that (A, B0) ∈ CovP (Proposition 6) and hence that covP(A, B) ≤ covQ(φ [A], φ [B]). ⊔⊓
The first example of a poset map that we will consider is an order reversing involution (_)∗ : P → P. That is for all p ∈ P it holds that p∗ = p. Such a map is necessarily a bijection. We will denote the image of X ⊆ P under (_)∗ by X∗ . Theorem 2. Let (_)∗ : P → It holds that:
1. (A, B) ∈ CovP ⇒ covP(A, B) = blockP(B∗ , A∗ ), 2. isolP(A, B) = packP(B∗ , A∗ ).
Proof. Let a ∈ A and b ∈ B. If a∗ ≤ b∗ it follows that b = b∗ ≤ a∗ = a. Hence, (_)∗ is order deflecting (and reversing by definition) between A and B. That means we can apply Theorem 1 . ⊔⊓ Example 2. Let K = (G, M, I) be a formal context. The complement (_)c, defined in Section 2, is an involution on P = 2G× M . With A = I1 , B = Rec(K) and Theorem 2, it follows that the Ferrers 2-dimension can be interpreted as a blocking problem. That is, find the minimal number of maximal rectangle complements (these are 2-step Ferrers relations), such that every coatom { (g, m)} c contains at least one. Since the intersection of all coatoms is equal to Ic, the intersection of this minimal number of rectangle complements must be too.
rep⇂X : P → 2X , p 7→ (p] ∩ X and rep↾X : P → 2X , p 7→ [p) ∩ X.
1. (A, B) ∈ CovP ⇒ covP(A, B) = cov2P (rep⇂A[A], rep⇂A[B]), 2. isolP(A, B) = isol2P (rep⇂A[A], rep⇂A[B]).
Similar equations hold if we replace cov with block (and Cov with Block), as well as isol with pack.
Proof. The requirement (A, B) ∈ BlockP is there to assure that for all b ∈ B there is at least one a ∈ A such that a ≤ b. Otherwise there could exist b ∈ B, such that rep⇂A(b) = (b] ∩ A = ∅ . If we exclude this case, we can show that the map rep⇂A preserves and reflects order between A and B. Hence, Theorem 1 applies. For a ∈ A and b ∈ B, we have that: rep⇂A(a) = (a] ∩ A = { x | x ∈ A ∧ x ≤ a} , rep⇂A(b) = (b] ∩ A = { x | x ∈ A ∧ x ≤ b} .
If a ≤ b, then (a] ⊆ (b] and consequently (a] ∩ A ⊆ (b] ∩ A. If conversely (a] ∩ A ⊆ (b] ∩ A, then a must be an element of (b] which implies that a ≤ b. ⊔⊓ Example 3. We consider K = (G, M, I) and put P = 2G× M , A = I1 and B = Rec(K). Since every maximal rectangle contains at least one { (g, m)} ∈ A it holds that (A, B) ∈ BlockP.
The efect of applying rep⇂A to A and B is that we “add one more layer of curly brackets.” A maximal rectangle R = { (g1, m1), . . . , (gk, mk)} will be mapped to { (g1, m1)} , . . . , { (gk, mk)} and every { (g, m)} ∈ A to { (g, m)} . Obviously, the four optimization problems will not be afected by this transformation.
1. covP(A, B) = block2P (rep↾B[B], rep↾B[A]), 2. isolP(A, B) = pack2P (rep↾B[B], rep↾B[A]).
as well as isol and pack.
Proof. Similar to the proof of Theorem 3. One has to show that rep↾B reverses and deflects order, and can apply Theorem 1 . ⊔⊓ Example 4. Let K = (G, M, I) be a formal context. Like in Example 3, we put P = 2G× M , A = I1 and B = Rec(K). Obviously, (A, B) ∈ CovP. For every pair (g, m) ∈ I, we define the set of all rectangles containing (g, m) as Rec(g, m) := { R | R ∈ Rec(K), (g, m) ∈ R} . The image of A and B under rep↾B is then given as: rep↾B[A] = { Rec(g, m) | (g, m) ∈ I} , rep↾B[B] = { R} | R ∈ Rec(K)} .
Instead of looking on the optimization problems w.r.t. these two sets, we are going to reinterpret them. Every C × D ∈ Rec(K), can be replaced with a formal concept (C, D). This gives us almost B(K), but possibly without (∅ , M ) and (G, ∅ ). Since it holds that (g, m) ∈ C ×
D ⇒ ⇐
(C, D) ∈ [γ (g), µ (m)], the set of all maximal rectangles containing (g, m) can be interpreted as the interval [γ (g), µ (m)] in the concept lattice. This point of view lifts the four optimization problems on formal contexts to the concept lattice B(K) or more precisely to 2B(K). Especially, by means of Theorem 4, this provides a meaningfully interpretation to the rectangle isolation- and rectangle blocking number. ri(K): Find the largest number of disjoint intervals [γ (g), µ (m)] (packing problem). rb(K): Find the smallest number of intervals [γ (g), µ (m)] that cover all formal concepts (C, D) with C, D ̸= ∅ (cover problem).
maximal number of disjoint intervals [γ (g), µ (m)] from B(K) provides a lower bound for the order 2-dimension of B(Kc).
Next, we combine Theorem 3 and 4.
1. The diagram from Figure 4 commutes. 2. Defining φ := 2(_)∗ ◦ rep↾B, we get covP(A, B) = block2B∗ (φ [A], φ [B]). 3. Defining ψ := 2(_)∗ ◦ rep⇂A, we get covP(A, B) = cov2A∗ (ψ [B], ψ [A]). 4. Similar equations hold if we swap cov and block. 5. Similar equations hold for isol and pack. Proof. 1 . We prove commutativity of the right diagram. Commutativity of the left one can be shown analogously. For p ∈ P , there are two possible images: Example 5. Again, we consider K = (G, M, I) and put P = 2G× M , A = I1 and B = Rec(K). Looking at the diagram from Figure 4, we see that Example 2 took us to the lower center, Example 3 to the upper left corner and Example 4 to the upper right corner. Hence, only the lower corners are left to explore. The diagram from Figure 3 can help to construct the necessary images from A and B under the respective maps. We will only sketch it and begin with the lower right corner from the diagram in Figure 4: { (g, m)} 7→ { (g, m)} c 7→ {
c c R | R ⊆ {
(g, m)} c} , R 7→
c R 7→ {
Rc} .
Hence, for example the rectangle cover problem translates to the blocking problem of finding the minimal number of 2-step Ferrers relations, such that every collection of 2-step Ferrers relations representing an atom { (g, m)} contains at least one of them.
The lower left corner from the diagram in Figure 4 translates to: { (g, m)} 7→ { (g, m)} c 7→ {
(g, m)} c} , R 7→
c R 7→ { (g, m)} c | R ⊆ { c (g, m)} c} .
Hence the rectangle cover problem translates to the cover problem of finding the minimal number of collections of coatoms representing one rectangle, such that every coatom is covered.
It seems that these two points of view don’t provide new insights to the four optimization problems on formal contexts.
Behaviour under Products The direct product of two posets P and Q is defined on the Cartesian product P × Q, together with the product order (a, b) ≤ (c, d) :⇒⇐ (a ≤ c) ∧ (b ≤ d).
l ≤ covP× Q(A × C, B × D) ≤ u, u = covP(A, B) covQ(C, D), l = max( isolP(A, B) covQ(C, D), covP(A, B) isolQ(C, D)).
Similar equations hold if we replace Cov by Block, cov by block and isol by pack.
Proof. Since (A, B) ∈ CovP and (C, D) ∈ CovQ, it follows from the definition of the direct product that ∀ ((a, c) ∈ A × C) ∃ ≥ 1((b, d) ∈ B × D) : (a, c) ≤ (b, d). Hence (A × C, B × D) ∈ CovP× Q. For the upper bound, let B0 be a minimal cover of A, and D0 a minimal cover of C. It follows that, (A × C, B0 × D0) ∈ CovP× Q.
To prove the lower bound, let T be a minimal cover of A × C and A0 a maximal isolated set w.r.t. B. For every a ∈ A0, we define Ta := { (b, d) | (b, d) ∈ T and a ≤ b} . From the definition of an isolated set, it follows that for diferent a, a˜ ∈ A0 the sets Ta and Ta˜ are disjoint. Furthermore, since π 2[Ta] covers C for all a ∈ A0, it holds that #Ta ≥ covQ(C, D). This leads to: #T ≥ #( [+ Ta) ≥ #A0 covQ(C, D) = isolP(A, B) covQ(C, D).
a∈ A0 The second part of the lower bound can be shown similarly.
Example 6. For two formal contexts K1 and K2 it was shown in [
Now, this result is a consequence of Theorem 6.
Corollary 1. Let (A, B) ∈ CovP and (C, D) ∈ CovQ. If covP(A, B) = isolP(A, B) or covQ(C, D) = isolQ(C, D), then the cover number is multiplicative with respect to the direct product:
covP× Q(A × C, B × D) = covP(A, B) covQ(C, D),
Example 7. Let K1 and K2 be formal contexts. It was shown in [
In this paper, we analysed the cover-, isolation, packing- and blocking problem on posets. Especially, we focused on mutual relationships between these problems and showed that they can be transformed into each other via special poset maps. Finally, we presented a result about the cover number of the direct product of posets. This led to a suficient criterion for the multiplicativity of the cover number w.r.t. the direct product.
With regard to Formal Concept Analysis, this abstract framework generalized previously obtained results about the rectangle cover number of the cardinal product of formal contexts. Furthermore, it was shown that the Ferrers 2-dimension can be seen as a blocking problem and we showed a method to interpret the four optimization problems on formal contexts w.r.t. the concept lattice.
Further research should be done on how to interpret the rectangle packing, isolation and blocking problem on formal contexts. Additionally, through this abstract framework, it might be possible to transfer methods, ideas or results, from other areas of mathematics where these four optimization problems have been treated, to Formal Concept Analysis.