=Paper=
{{Paper
|id=Vol-2668/paper14
|storemode=property
|title=Optimization Problems on Posets
|pdfUrl=https://ceur-ws.org/Vol-2668/paper14.pdf
|volume=Vol-2668
|authors=Christian Jäkel,Stefan E. Schmidt
|dblpUrl=https://dblp.org/rec/conf/cla/JakelS20
}}
==Optimization Problems on Posets==
https://ceur-ws.org/Vol-2668/paper14.pdf
Optimization Problems on Posets
Christian Jäkel1 and Stefan E. Schmidt2
Technische Universität Dresden, 01062, Dresden, Germany
1
ChristianJaekel(at)gmx-topmail.de
2
midt1(at)msn.com
Abstract. 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.
Keywords: formal concept analysis, poset, order dimension, cover problem,
packing problem, isolated set, blocking set, cardinal product.
1 Introduction
In [6] the rectangle cover number was introduced as the minimal number of
maximal rectangles which are necessary to cover the incidence relation of a
formal context. The formal definition is:
[
rc(K) := min{#R | R ⊆ Rec(K), I = R}.
R∈R
This optimization problem on formal contexts can be translated to the order
2-dimension of the concept lattice of the complementary context (see [5]). As a
lower bound for the rectangle cover number, the rectangle isolation number was
introduced in [6] as the maximal number of elements from I, such that every
maximal rectangle contains at most one of them:
ri(K) := max{#I | I ⊆ I, ∀(R ∈ Rec(K)) : #(I ∩ R) ≤ 1}.
It always holds that ri(K) ≤ rc(K) and in case of equality there are conse-
quences for the tensor product of complete lattices (see [6]). After investigating
these optimization problems for a while, two seemingly similar problems come
up. These are the maximal number of disjoint rectangles that fit into I, denoted
as the rectangle packing number, and the minimal number of elements from I
such that there is at least one of them contained in every maximal rectangle,
denoted as the rectangle blocking number. Formally:
rp(K) := max{#R | R ⊆ Rec(K), ∀(R1 , R2 ∈ R), R1 ̸= R2 : R1 ∩ R2 = ∅},
rb(K) := min{#I | I ⊆ I, ∀(R ∈ Rec(K)) ∃((g, m) ∈ I) : (g, m) ∈ R}.
Similar, to the cover and isolation number, it holds that rp(K) ≤ rb(K).
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.
186 Christian Jäkel and Stefan E. Schmidt
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 relation-
ships. 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 Basics of Formal Concept Analysis
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 [5].
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, I c ) := (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), isTthe smallest number of Ferrers relations Ft ,
t ∈ T with l(Ft ) < 2, so that I = t∈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
ˆ K2 := (G1 × G2 , M1 × M2 , I1 ×
from [4] and define the cardinal product K1 × ˆ I2 ),
ˆ I2 :⇐⇒ (g, m) ∈ I1 and (h, n) ∈ I2 .
((g, h), (m, n)) ∈ I1 ×
Optimization Problems on Posets 187
3 The Four Optimization Problems on Posets
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 ∈ A) ∃≥1 (b ∈ B) : a ≤ b,
(A, B) ∈ IsolP :⇐⇒ ∀(b ∈ B) ∃≤1 (a ∈ A) : a ≤ b,
(A, B) ∈ BlockP :⇐⇒ ∀(b ∈ B) ∃≥1 (a ∈ A) : a ≤ b,
(A, B) ∈ PackP :⇐⇒ ∀(a ∈ A) ∃≤1 (b ∈ B) : a ≤ b.
Definition 1. Let A, B ⊆ P . In case that (A, B) ∈ CovP holds, we say that B
covers A, or that A is covered by B. Relation IsolP is expressed as A is isolated
w.r.t. B.
Fig. 1. The left image depicts CovP (every a is at least below one b) and the
right one IsolP (every b has at most one a below).
b1 b2 b3 b4 ... b1 b2 b3 b4 ...
a1 a2 a1 a2 a3
B covers A A is isolated w.r.t. to B
The terminology of a covering is well established through out various branches
of mathematics. Presumably, the term isolation is less well known. In [1] is a
recent example of its use in matrix theory.
Definition 2. Let A, B ⊆ P . In case that (A, B) ∈ BlockP holds, we say that A
blocks B, or that B is blocked by A. Relation PackP is expressed as B is packed
w.r.t. A.
188 Christian Jäkel and Stefan E. Schmidt
Fig. 2. The left image depicts BlockP (every b has at least one a below) and the
right one PackP (every a is at most below one b).
b1 b2 b1 b2 b3
a1 a2 a3 a4 ... a1 a2 a3 a4 ...
A blocks B 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 [2,3]).
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. ⊔
⊓
Next, we define four optimization problems on CovP , IsolP , PackP and BlockP .
Definition 3. Let (A, B) ∈ CovP . The cover number of (A, B) is defined as
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.
Optimization Problems on Posets 189
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
find 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 :⇔ ∀(a ∈ A, b ∈ B) : a ≤ b ⇒ φ(a) ≤ φ(b),
– reverses order between A and B :⇔ ∀(a ∈ A, b ∈ B) : a ≤ b ⇒ φ(b) ≤ φ(a),
– reflects order between A and B :⇔ ∀(a ∈ A, b ∈ B) : a ≤ b ⇐ φ(a) ≤ φ(b),
– deflects order between A and 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.
Proposition 4. For A, B ⊆ P, let φ : P → Q be order preserving, and ψ : P → Q
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], there exists at least
one b̃ ∈ φ[B] with ã ≤ b̃, is true, since there exists a ∈ A and b ∈ B such that
φ(a) = ã and φ(b) = b̃. Hence, ã = φ(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 . ⊔
⊓
190 Christian Jäkel and Stefan E. Schmidt
Proposition 5. For A, B ⊆ P, let φ : P → Q be order reflecting, and ψ : P → Q
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] with ã ≤ 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:
Proposition 6. For A, B ⊆ P, let φ : P → Q be order preserving and reflecting,
and ψ : P → Q order reversing and deflecting, between A and B.
(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.
Theorem 1. For A, B ⊆ P, let φ : P → Q be order preserving and reflecting,
and ψ : P → Q order reversing and deflecting, between A and B.
For (A, B) ∈ CovP , it holds that:
covP (A, B) = covQ (φ[A], φ[B]) = blockQ (ψ[B], ψ[A]).
Generally, it holds that:
isolP (A, B) = isolQ (φ[A], φ[B]) = packQ (ψ[B], ψ[A]).
Similar equations hold if we swap cov and block (assuming (A, B) ∈ BlockP ),
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]). ⊔
⊓
Optimization Problems on Posets 191
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 → P be an order reversing involution and A, B ⊆ P.
It holds that:
1. (A, B) ∈ CovP ⇒ covP (A, B) = blockP (B ∗ , A∗ ),
2. isolP (A, B) = packP (B ∗ , A∗ ).
Similar equations hold if we swap cov and block (assuming (A, B) ∈ BlockP ),
as well as isol and pack.
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 = 2 G×M
. With A = 1 , B = Rec(K)
I
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 I c , the
intersection of this minimal number of rectangle complements must be too.
Fig. 3. The complementation in 2G×M .
I
{(g, m)}c
R1
R2 R3 (_)c
R3c R2c
R1c
{(g, m)}
Ic
The second example of a poset map that we want to investigate is based on
the powerset representations of P. These are an order preserving and an order
revering map into 2P .
rep⇂ : P → 2P , p 7→ (p] and rep↾ : P → 2P , p 7→ [p).
192 Christian Jäkel and Stefan E. Schmidt
For X ⊆ P these maps restrict to 2X , via
rep⇂X : P → 2X , p 7→ (p] ∩ X and rep↾X : P → 2X , p 7→ [p) ∩ X.
Theorem 3. Let (A, B) ∈ BlockP . It holds that:
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 effect 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 affected by this transformation.
Theorem 4. Let (A, B) ∈ CovP . It holds that:
1. covP (A, B) = block2P (rep↾B [B], rep↾B [A]),
2. isolP (A, B) = pack2P (rep↾B [B], rep↾B [A]).
Similar equations hold if we swap cov and block (assuming (A, B) ∈ BlockP ),
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)}.
Optimization Problems on Posets 193
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 inter-
val [γ(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 interpre-
tation 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).
Since ri(K) ≤ rc(K), another interesting consequence is the fact that the
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.
Theorem 5. Let (A, B) ∈ CovP ∩ BlockP .
Fig. 4. A commutative diagram depicting various poset maps.
rep⇂A rep↾B
2A P 2B
2(_) 2(_)
∗ ∗
∗
2A 2B
∗ ∗
P
rep↾A∗ rep⇂B ∗
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.
194 Christian Jäkel and Stefan E. Schmidt
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:
p 7→ [p) ∩ B 7→ {x | x ∈ [p) ∩ B}∗ = {x∗ | p ≤ x ∧ x ∈ B} =: S1 ,
p 7→ p∗ 7→ (p∗ ] ∩ B ∗ = {x | x ≤ p∗ ∧ x ∈ B ∗ } =: S2 .
If p ≤ x, then x∗ ≤ p∗ and if x ∈ B then x∗ ∈ B ∗ . Hence, it holds that
S1 ⊆ S2 . For y ∈ S2 , we have to find ỹ ∈ P with p ≤ ỹ and ỹ ∈ B, such that
ỹ ∗ = y. Since (_)∗ is an involution ỹ := y ∗ has this property. Consequently, we
conclude that S2 ⊆ S1 .
2. Since, 2(_) preserves and reflects order between rep↾B [B] and rep↾B [A], and
∗
rep↾B is order reversing and order deflecting between A and B, their composite
φ is order reversing and order deflecting between A and B too. Hence, Theorem
1 can be applied.
3. Similar to 2. ⊔
⊓
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→ {Rc | Rc ⊆ {(g, m)}c },
R 7→ Rc 7→ {Rc }.
Hence, for example the rectangle cover problem translates to the blocking prob-
lem 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→ Rc 7→ {{(g, m)}c | Rc ⊆ {(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.
Optimization Problems on Posets 195
3.3 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).
Theorem 6. For posets P and Q, let (A, B) ∈ CovP and (C, D) ∈ CovQ . Then
(A × C, B × D) ∈ CovP×Q . It holds that:
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 different
a, ã ∈ A0 the sets Ta and Tã 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 [6] that:
ˆ K2 ) ≤ rc(K1 ) rc(K2 ).
max( ri(K1 ) rc(K2 ), rc(K1 ) ri(K2 )) ≤ rc(K1 ×
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 [6] that whenever
ˆ K2 ) = rc(K1 ) rc(K2 ). Now, this
rc(K1 ) = ri(K1 ) or rc(K2 ) = ri(K2 ) then rc(K1 ×
follows from Corollary 1.
196 Christian Jäkel and Stefan E. Schmidt
4 Conclusion
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 sufficient 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 prod-
uct 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.
References
1. Beasley, L.B., Song, S.Z.: Upper bounds for the isolation number of a matrix over
semirings. Mathematics 7 7(1), 65 (2019)
2. Beule, J.D.: Blocking sets and partial spreads in finite polar spaces. Ph.D. thesis,
Universiteit Gent (2004)
3. Blokhuis, A., Brouwer, A.E., Wilbrink, H.A.: Blocking sets in pg(2,q) for small p,
and partial spreads in pg(3,7). Advances in Geometry 2003, 245–253 (2003)
4. Deiters, K., Erné, M.: Sums, products and negations of contexts and complete lattices.
Algebra Universalis 60, 469–496 (2009)
5. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer-
Verlag New York, Inc. (1997)
6. Jäkel, C., Schmidt, S.E.: Cover problems, dimensions and the tensor product of
complete lattices. Proceedings of the Fourteenth International Conference on Concept
Lattices and Their Applications, CLA 2018, Olomouc, Czech Republic (2018)