In this article, we analyze diferent dimensional concepts of complete (ortho)lattices and their tensor products. The determination of these dimensions can be translated to certain set cover problems and the cardinal product of the complementary underlying formal contexts. To treat this cover problems in a unified manner, we take a more universal approach via the general set cover problem and its product. This yields a suficient condition for the multiplicativity of various lattice dimensions with respect to the tensor product of complete lattices.
c paper author(s), 2018. Proceedings volume published and copyrighted by its editors.
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp. 81{92, Department of Computer Science, Palacky University Olomouc, 2018. Copying permitted only for private and academic purposes.
In this section, we will provide the facts from formal concept analysis that we
will use in the sequel. If not mentioned otherwise, 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 between finite sets. 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 the cartesian product A × B is a maximal rectangle of 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 ). It holds that: gIm ⇒ ⇐
γ (g) ≤ µ (m).
For two contexts K1 = (G1, M1, I1) and K2 = (G2, M2, I2), we use notation
from [
(g, m) ∈ I1 and (h, n) ∈ I2.
It follows that the direct and cardinal product fulfill De Morgan laws: (K1 × ˇ K2)c = Kc1 × ˆ Kc2 and (K1 × ˆ K2)c = Kc1 × ˇ Kc2.
For two complete lattices L1 and L2 the tensor product L1 ⊗ L2 is the concept lattice B(L1 × ˇ L2), where L1 and L2 are considered as formal contexts with respect to their order relations. The concept lattice of the direct product is isomorphic to the tensor product of the factors concept lattices.
B(K1 × ˇ K2) ∼= B(K1) ⊗ B(K2).
Next, we will treat the dimension theory of formal concepts. A Ferrers relation is a relation F ⊆ G × M such that (g, m), (h, n) ∈ F implies (g, n) ∈ F or (h, m) ∈ F . The definition states that F can be brought into a stair-shaped form (1 ) (2 ) (3) by permuting the rows and columns. 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 and F is k-step if k = #{ { g} F | g ∈ G} . Furthermore, it holds that the complement F c of a k-step Ferrers relation is a Ferrers relation of length k.
Let Ferr↾(K) denote the set of all Ferrers relations contained in I and Ferr⇂(K) the set of all Ferrers relations containing I. We define the Ferrers cover number2 and the Ferrers dimension of K:
fc(K) := min{ #F | F ⊆ fdim(K) := min{ #F | F ⊆
Ferr↾(K), I = [ F } ,
F ∈F Ferr⇂(K), I = \ F } .
F ∈F
Analogously, Ferr↾k(K) denotes the set of all at most k-step Ferrers relations contained in I and Ferr⇂k(K) the set of all Ferrers relations with length less than k containing I. We define the the Ferrers k-cover number2 and the Ferrers k-dimension:
fck(K) := min{ #F | F ⊆ fdimk(K) := min{ #F | F ⊆
Ferr↾k(K), I = [ F } ,
F ∈F Ferr⇂k(K), I = \ F } .
F ∈F Especially, we want to highlight fc1, the rectangle cover number3: rc(K) := min{ #F | F ⊆
B(K), I =
A × B} .
[ (A,B)∈F
Let AI be the adjacency matrix of the incidence relation I. In [
Lastly, we will state the dimension theory of complete lattices and relate it
to the above defined dimensions of formal contexts. The order dimension of a
complete lattice L, dim(L), is the least number of chains, such that L can be order
embedded in their product. If we restrict the cardinality of these chains to be at
2 This term is introduced by us, although the concept itself is described in [
In the next section, we will need a proposition from [
Proposition 1. [6, Hilfssatz 32] There exists an order embedding from B(K) into a complete lattice L if and only if there exist mappings α : G → L and β : M → L with gIm ⇒ ⇐
α (g) ≤ β (m).
Proof. "⇒ ": The required order embedding is given through φ (A, B) := Wg∈ A α (g). "⇐ ": Define α := φ ◦ γ and β := φ ◦ µ . 3
A tolerance relation or simply a tolerance is a reflexive and symmetric binary
relation τ on a non-empty finite set V . The pair (V, τ ) =: T is called tolerance
space and is a special case of a formal context. An introduction to tolerance
spaces together with applications can be found in [
For a tolerance τ on V , a non-empty subset S ⊆ V is called τ -preblock if S × S is contained in τ . A maximal τ -preblock with respect to set inclusion is called τ -block. In other words, this means that a τ -block S ⊆ V defines a non-enlargeable square S × S ⊆ τ . The set of all τ -blocks is denoted by Bl(T). Analogously, the set of all maximal squares of T is denoted by Sq(T). This set determines the tolerance τ , that is τ = S Sq(T). But often not all squares are necessary to cover τ . This motivates the definition of the square cover number5, sc(T), of a tolerance space T, as the minimal number of maximal squares necessary to cover τ : sc(T) := min{ #S | S ⊆
Sq(T), τ = [ S} .
Another covering problem of tolerance spaces is the block cover number6: bc(T) := min{ #B | B ⊆
Bl(T), V = [ B} .
Similarly to the Ferrers cover numbers and rectangle cover number of general formal contexts, we can relate these cover numbers of tolerance spaces to an 5 This term is introduced by us and is a logical consequence of the term "rectangle cover number". 6 This term is introduced by us. intersection problem and a dimension of the complements concept lattice.
We start with the square cover number and notice that the complement of a square is a symmetric Ferrers relation of length 1. Hence, we define the symmetric Ferrers 2-dimension of Tc, denoted by sfdim2, as the smallest number of symmetric Ferrers relations of length 1 whose intersection is equal to τ c.
The concept lattice7 B(Tc) was characterized in [
Remark 1. The map φ is a section from L1 to L2, such that φ and the dual of φ given by φ d : L1 →
L2, x 7→ (φ (xc1 ))c2 have ψ as a common retraction.
The next proposition provides an equivalent condition for the existence of an orthoembedding from B(Tc) to a Boolean algebra (in other words a distributive ortholattice) with the additional property that x ⊥ y ⇒ ⇐ x ∧ y = 0. 7 The concept lattice was treated under the name neighborhood ortholattice. Proposition 2. There exists an orthoembedding φ from B(Tc) into a Boolean algebra L = (L, ≤ , c), with the special property that for all x, y ∈ L it holds that x ⊥ y ⇒ ⇐ x ∧ y = 0, if and only if there exists a mapping α : V → L with uτ cv ⇒ ⇐
α (u) ⊥ α (v).
Proof. "⇒ ": We define α := φ ◦ γ and use Equation 1 to conclude that: u τ cv ⇒ ⇐ ⇒ ⇐ γ (u) ≤ µ (v) = γ (v)c γ (u) ⊥ γ (v) =⇒ φ ◦ γ (u) ⊥ φ ◦ γ (v).
u τ cv ⇒ ⇐
γ (u) ≤ γ (v)c ⇐ = ψ (φ ◦ γ (u)) ≤ ψ ((φ ◦ γ (v))c) ⇐ = φ ◦ γ (u) ≤ (φ ◦ γ (v))c ⇒ ⇐ φ ◦ γ (u) ⊥ φ ◦ γ (v). "⇐ ": We define φ (A, B) := Wa∈ A α (a). It follows from Proposition 1 that φ is an order embedding. Let (A, B) and (C, D) be formal concepts of B(Tc). We show that (A, B) ⊥ (C, D) =⇒ φ (A, B) ⊥ φ (C, D). From the definition of φ and the complement in B(Tc) it follows that: (A, B) ⊥ (C, D) ⇒ ⇐ (A, B) ≤ (D, C) ⇒ ⇐ _ α (a) ≤ a∈ A _ α (d), d∈ D φ (A, B) ⊥ φ (C, D) ⇒ ⇐ _ α (a) ∧ a∈ A _ α (c) = 0. c∈ C
In the next step, we show that 4 implies 5 by "connecting" the ends. "(4 )⇒ (5)": Since, (C, D) is a formal concept it holds that α (d) ≤ α (c)c for all d ∈ D and all c ∈ C.
(4) ⇒ _ α (a) ≤ _ α (a) = _ α (a) ∧ Finally, we take the meet with Wc∈ C α (c) and use distributivity. _ α (a) ∧ _ α (c) = ( _ α (a) ∧ c∈ C
Furthermore, we define the desired map ψ : L → B(Tc) through ψ (x) :=
({ v ∈ V | α (v) ≤ x} , { v ∈ V | x ≤ α (v)c} ) and show that ψ (x) is a formal
concept of B(Tc), as well as that ψ satisfies Property 1 and 2 from Definition
1 . The proof is similar to some parts of the proof from the Basic Theorem on
Concept Lattices (see [
The definition of formal concepts states that Aτ c = B and Bτ c = A must hold in order for (A, B) ∈ B(Tc). We only show the second condition as the first (4 ) (5) one can be shown in the same way.
u ∈ { v ∈ V | α (v) ≤ x} ⇒ ⇐
α (u) ≤ x ⇒ ⇐ ⇒ ⇐ ⇒ ⇐ α (u) ≤ α (w)c for all w ∈ { v ∈ V | x ≤ α (v)c} u τ cw for all w ∈ { v ∈ V | x ≤ α (v)c} u ∈ { v ∈ V | x ≤ α (v)c} τ c .
Next, we show that the second component from ψ (φ (A, B)) equals B. The ifrst component must then be equal to A, due to the fact shown above. { v ∈ V | _ α (a) ≤ α (v)c} = { v ∈ V | α (a) ≤ α (v)c for all a ∈ A} a∈ A = { v ∈ V | a τ cv for all a ∈ A} = Aτ c = B.
Lastly, we show that the first component from ψ (φ (A, B)c) equals B. The second component must then be equal to A, due to the fact shown above. Hence, we can conclude that ψ (φ (A, B)c) = ψ (Va∈ A α (a)c) = (B, A) = (A, B)c. { v ∈ V | α (v) ≤ ^ α (a)c} = { v ∈ V | α (v) ≤ α (a)c for all a ∈ A} a∈ A = { v ∈ V | v τ ca for all a ∈ A} = Aτ c = B.
Definition 2. The orthodimension of a complete ortholattice L = (L, ≤ , c), denoted by dim⊥ (L), is the smallest n such that there exists an orthoembedding from L to P(n).
Theorem 1. For a tolerance space T its holds that sc(T) = dim⊥ (B(Tc)).
Proof. If sc(T) = n, there exists a minimal square cover { S1 × S1, . . . , Sn × Sn} .
It follows from [
i | v ∈ Si} .
Consequently, α provides a minimal complementary set representation for Tc, that is u τ cv ⇒ ⇐ α (a) ∩ α (v) = ∅ . Since it holds that α (a) ∩ α (v) = ∅ ⇒ ⇐ α (a) ⊆ α (v)c ⇒ ⇐ α (a) ⊥ α (v), Proposition 2 yields that dim⊥ (B(Tc)) = n. As all stated implications are equivalences, it follows that sc(T) = dim⊥ (B(Tc)).
We have shown that analogue to general formal contexts, in the special case of tolerance spaces, it holds that:
sc(T) = sfdim2(Tc) = dim⊥ (B(Tc)).
Next, we will treat the block cover number. For this, we will use some tools from graph theory which we introduce in the following.
The underlying graph, GT, of a tolerance space T = (V, τ ) is defined through
the same relation but with all diagonal elements removed. Analogously, to the
block and square cover number of T, we can define the vertex clique cover
number, θ v(GT) = bc(T), and the edge clique cover number, θ e(GT) = sc(T) (see
[
We saw that B(Tc) is a complete ortholattice. An orthomap between complete
ortholattices (see [
Definition 3. We define the chromatic dimension, cdim(L), of a complete ortholattice L = (L, ≤ , c), to be the minimal n such that an orthomap to the powerset lattice P(n) exists.
The nomenclature is justified by the following proposition.
Proposition 3. For a graph G = (V, E) with an irreflexive and symmetric relation E ⊆ V × V , it holds that χ (G) = cdim(B(G)).
Proof. The chromatic number of G is n if and only if n is minimal with the
property that there exists a graph homomorphism to Kn, the complete graph with
n vertices. In [
The calculation of the chromatic number is a minimization problem, but not an intersection problem. In order to define an intersection problem, we notice that the complement Bc for a block B ∈ Bl(T) is an independent set of vertices with respect to τ c. Hence, we can define an intersection problem with respect to Tc. This yields the independence dimension of Tc, denoted by idim(Tc), to be the smallest number of independent sets whose intersection is empty.
bc(T) = idim(Tc) = χ (Tc) = cdim(B(Tc)). 8 The chromatic number of a graph is the minimal n such that a graph homomorphism, which is an edge preserving vertex map, to the complete graph with n vertices exists.
A set cover system is a triple S := (U, X, S), with universe U , a subset X ⊆ U and S ⊆ P(X). The cover number and isolation number of S are defined as: c(S) := min{ #S˜ | S˜ ⊆ S , X = [ S˜} , i(S) := max{ #X˜ | X˜ ⊆ X, ∀ S ∈ S : #(X˜ ∩ S) ≤ 1} .
The isolation number is the maximal cardinality of an isolated set X˜ from S, which means that X˜ is maximal with respect to the property that any pair of its elements is not contained in the same S ∈ S . Consequently, the isolation number is a lower bound for the cover number.
Remark 2. Both optimization problems can be described as an integer linear program. For this purpose, we define the representation matrix A ∈ { 0, 1} X×S of S through A(i, S) = 1 :⇔ i ∈ S.
minimize: subject to:
X xS S∈S Ax ≥ 1 xS ∈ { 0, 1} .
maximize: subject to:
X yi i∈ X AT y ≤ 1 yi ∈ { 0, 1} .
Thus, the inequality i(S) ≤ c(S) also follows from the weak duality theorem of optimization and the diference c(S) − i(S) is the duality gap.
A set intersection system is a triple S := (U, X, S), with universe U , a subset X ⊆ U and S ⊆ P(U ), such that X ⊆ S for all S ∈ S . The intersection number is defined as:
int(S) := min{ #S˜ | S˜ ⊆ S , X = \ S˜} .
It follows that the complement of a set cover system, defined through Sc := (U, Xc, { Sc | S ∈ S} )9, is a set intersection system with c(S) = int(Sc).
The product of two set cover systems S1 = (U1, X1, S1) and S2 = (U2, X2, S2)
is defined as S1 × S2 := (U1 × U2, X1 × X2, S1 × S 2). This definition yields to the
next theorem which is a generalization of Theorem 3.2 from [
For the lower bound, let S˜ be a minimal cover from S1 × S2 and X˜1 a maximal isolated set from S1. We define for i ∈ X˜1 the set S˜i := { (S, T ) | (S, T ) ∈ S˜, i ∈ S} . Since X˜1 is an isolated set, it follows that for diferent i, j ∈ X˜1, the sets S˜i and S˜j are disjoint. A similar argument implies that every S˜i induces a cover from S2 and hence #S˜i ≥ c(S2). These facts yield: #S˜ ≥ #( [+ S˜i) ≥ #X˜1 c(S2) = i(S1) c(S2).
i∈ X˜1
The other lower bound’s component can be deduced in the same way. 5
With Theorem 2 , it is easy to provide a suficient condition when dim, dimk, dim2,
dim⊥ and cdim are multiplicative with respect to the tensor product. Since every
complete lattice is isomorphic to a concept lattice ([
In the sense of Section 4 , we define the Ferrers isolation number fi , the k-Ferrers isolation number fi k, the rectangle isolation number ri, the square isolation number si and the block isolation number bi.
For the cardinal product of formal contexts, it holds that (A, B) ∈ B(K1 × ˆ K2)
if and only if there exists (A1, B1) ∈ B(K1) and (A2, B2) ∈ B(K2), such that
A = A1 × A2 and B = B1 × B2 (see [
Remark 3. We introduce the strong product of two simple graphs G1 = (V1, E1) and G2 = (V2, E2), defined as G1⊠G2 := (V1× V2, E˜), with (u1, u2)E˜(v1, v2) :⇒⇐ (u1E1v1 and u2 = v2) or (u1 = v1 and u2E2v2) or (u1E1v1 and u2E2v2).
The reflexive closure of a graph G = (V, E) is defined as Gref := (V, Eref ),
where Eref is the reflexive closure of the symmetric relation E. Hence, Gref is a
tolerance space. It holds that (G1 ⊠ G2)ref = Gr1ef × ˆ Gr2ef . Consequently, we have
that θ e(G1 ⊠ G2) = sc(Gr1ef × ˆ Gr2ef ). In [
In [
We showed that the three fold relationship between cover problem (Ferrers cover number), intersection problem (Ferrers dimension) and lattice dimension (order dimension) also applies to tolerance spaces. That is the equality of the square cover number, the symmetric Ferrers 2-dimension and the orthodimension. Surprisingly, this theme is also present in the case of the block cover number and the chromatic dimension.
Additionally, we highlighted how the cover problems with respect to tolerance spaces have a strong graph theoretic flavor, i.e., interpretations in terms of the chromatic number or the relationship to the strong product of graphs.
Our initial question, about the multiplicativity of the lattice dimension with respect to the tensor product, could, in all investigated examples, be translated to a cover problem of the cardinal product of the related formal contexts complements. This fundamental principle lead to the abstraction to the general set cover problem, which provides a unified setting to treat these various cover problems related to formal contexts. Especially, the question about the multiplicativity of the dimension of the cardinal product could be dealt with in a unified way. This in turn lead to a suficient condition for the multiplicativity of the lattice dimensions with respect to the tensor product of complete lattices.
The introduced isolation numbers have to our knowledge not been present in the theory of formal concept analysis. It is an open problem to find a purely lattice theoretical interpretation of these isolation numbers.
Acknowledgments. Finally, we want thank the anonymous referees for their efort and valuable suggestions.