# Mathematical Morphology on Hypergraphs Using Vertex-Hyperedge Correspondence

Authors: Bino Sebastian; A. Unnikrishnan; Kannan Balakrishnan; P. B. Ramkumar
Journal: ISRN Discrete Mathematics
 (2014)

---

## Abstract

The focus of this paper is to develop computationally efficient mathematical morphology operators on hypergraphs. To this aim we consider lattice structures on hypergraphs on which we build morphological operators. We develop a pair of dual adjunctions between the vertex set and the hyperedge set of a hypergraphH, by defining a vertex-hyperedge correspondence. This allows us to recover the classical notion of a dilation/erosion of a subset of vertices and to extend it to subhypergraphs of H. This paper also studies the concept of morphological adjunction on hypergraphs for which both the input and the output are hypergraphs.


---

## Body

## 1. Introduction

Mathematical morphology, appeared in 1960s, is a theory of nonlinear information processing [1–4]. It is a branch of image analysis based on algebraic, set-theoretic, and geometric principles [5, 6]. Originally, it is developed for binary images by Matheron and Serra. They are the first to observe that a general theory of mathematical morphology is based on the assumption that the underlying image space is a complete lattice. Most of the morphological theories at this abstract level were developed and presented without making references to the properties of the underlying space. Considering digital objects carrying structural information, mathematical morphology has been developed on graphs [7–10] and simplicial complexes [11], but little work has been done on hypergraphs [12–15].When dealing with a hypergraphH, we need to consider the hypergraph induced by the subset X
• of vertices of H (see Figures 1(a) and 1(b), where the blue vertices and edges in (b) represent X). We associate with X
• the largest subset of hyperedges of H such that the obtained pair is a hypergraph. We denote it by H
(
X
•
) (see Section 3.1 and Figure 1(b)). We also consider a hypergraph induced by a subset X
× of the edges of H, namely, H
(
X
×
).Illustration of hypergraph dilation.
(a)
H
(b)
X
(c)
Dilation[
Δ
,
δ
]
(
X
)Here we propose a systematic study of the basic operators that are used to derive a set of hyperedges from a set of vertices and a set of vertices from a set of hyperedges. These operators are the hypergraph extension to the operators defined by Cousty et al. [7, 8] for graphs. Since a hypergraph becomes a graph when |
v
(
e
)
|
=
2 for every hyperedge e, all the properties of these operators are satisfied for graphs also. We emphasise that the input and output of these operators are both hypergraphs. The blue subhypergraph in Figure 1(c) is the result of the dilation [
Δ
,
δ
]
(
X
) of the blue subhypergraph X in Figure 1(b) proposed in this paper. Here the resultant subhypergraph in Figure 1(c) is not induced by its vertex set.This paper is organized as follows. In Section2 we recall some related works on graphs and hypergraphs. In Section 3, we recall some preliminary definitions and results on mathematical morphology and hypergraphs. In Section 4, we define the vertex-hyperedge correspondence along with various dilations, erosions, and adjunctions on hypergraphs. The properties of these morphological operators are studied in this section. Section 5 concludes the paper with possible future works in this regard.


## 2. Related Works

Graph theoretic methods have found increasing applications in image analysis. Morphological operators are well studied on graphs. Vincent [10] defined morphological operators on a graph G
=
(
V
,
E
), where V represents a set of weighted vertices and E represents a set of edges between vertices. The dilation (resp., erosion) replaces the value of each vertex with the maximum (resp., minimum) value of its neighbors. Cousty et al. [7, 8] considered a graph as a pair G
=
(
G
•
,
G
×
), where G
• is the set of vertices and G
× is the edge set of the graph G. They define morphological operators on various lattices formed by the graph G by defining an edge-vertex correspondence. This powerful tool allows them to recover the classical notion of a dilation/erosion of a subset of vertices of G. This leads them to propose several new openings, closings, and granulometries and alternate sequential filters acting on the subsets of the edge sets, subsets of vertex sets, and the lattice of subgraphs of G. These operators are further extended to functions that weight the vertices and edges of G [16] and are found to be useful in image filtering. In this work we aim to develop morphological operators on hypergraphs by defining a vertex-hyperedge correspondence.The theory of hypergraphs originated as a natural generalisation of graphs in 1960s. In a hypergraph, edges can connect any number of vertices and are called hyperedges. Considering the topological and geometrical aspects of an image, Bretto et al. [17] have proposed a hypergraph model to represent an image. The theory of hypergraphs became an active area of research in image analysis. The study of mathematical morphology operators on hypergraphs started recently, and little work is being reported in this regard. Properties of morphological operators on hypergraphs are studied in [15], in which subhypergraphs are considered as relations on hypergraphs. Recently, Bloch and Bretto [12] introduced mathematical morphology on hypergraphs by forming various lattices on hypergraphs. Similarity and pseudometrics based on mathematical morphology are defined and illustrated in [14]. Based on these morphological operators, similarity measures are used for classification of data represented as hypergraphs [13].


## 3. Preliminaries

### 3.1. Hypergraphs

We define ahypergraph [12, 18] as a pair H
=
(
H
•
,
H
×) where H
• is a set of points calledvertices and H
× is composed of a family of subsets of H
• calledhyperedges. We denote H
× by H
×
=
(
e
i
)
i
∈
I where I is a finite set of indices. The set of vertices forming the hyperedge e is denoted by v
(
e
). A vertex x in H
• is called anisolated vertex of H if x
∉
∪
i
∈
I
v
(
e
i
). Theempty hypergraph is the hypergraph H
ϕ such that H
•
=
ϕ and H
×
=
ϕ. Thepartial hypergraph
H
′ of H generated by J
⊆
I is the hypergraph H
′
=
(
H
′
•
,
H
′
×) where H
′
•
=
H
• and H
′
×
=
(
e
j
)
j
∈
J. A hypergraph X
=
(
X
•
,
X
×
) is called asubhypergraph of H, denoted by X
⊆
H, if X
•
⊆
H
• and X
×
⊆
H
×.LetX
•
⊆
H
• and X
×
⊆
H
× where X
×
=
(
e
j
)
,
j
∈
J such that J
⊆
I. We denote by X
•
¯ (resp., X
×
¯) by the complementary set of X
• (resp., X
× ). Let H
(
X
•
) and H
(
X
×
), respectively, denote the hypergraphs (
X
•
,
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
X
•
}
) and (
∪
j
∈
J
v
(
e
j
)
,
(
e
j
)
j
∈
J
).While dealing with a hypergraphH, we consider the subhypergraph induced by a subset X
• of vertices of H, namely, H
(
X
•
), and the subhypergraph induced by a subset X
× of hyperedges, namely, H
(
X
×
). H
(
X
•
) is the largest subhypergraph of H with X
• as vertex set and H
(
X
×
) is the smallest subhypergraph of H with X
× as its hyperedge set.


### 3.2. Mathematical Morphology

Now let us briefly recall some algebraic tools that are fundamental in mathematical morphology [5–7, 19]. Given two lattices ℒ
1 and ℒ
2, any operator δ
:
ℒ
1
→
ℒ
2 that distributes over the supremum and preserves the least element is called adilation (i.e.,  ∀
ε
⊆
ℒ
1
,
δ
(
∨
1
ε
)
=
∨
2
{
δ
(
X
)
∣
X
∈
ε
}
). Similarly an operator that distributes over the infimum and preserves the greatest element is called anerosion.Two operatorsϵ
:
ℒ
1
→
ℒ
2 and δ
:
ℒ
2
→
ℒ
1 form anadjunction
(
ϵ
,
δ
), if for any X
∈
ℒ
1 and any Y
∈
ℒ
2, we have δ
(
X
)
≤
1
Y
⇔
X
≤
2
ϵ
(
Y
), where ≤
1 and ≤
2 denote the order relations in ℒ
1 and ℒ
2, respectively [19]. Given two operators ϵ and δ, if the pair (
ϵ
,
δ
) is an adjunction, then ϵ is an erosion and δ is a dilation. If ℒ
1, ℒ
2, and ℒ
3 are three lattices and if δ
:
ℒ
1
→
ℒ
2, δ
′
:
ℒ
2
→
ℒ
3, ϵ
:
ℒ
2
→
ℒ
1, and ϵ
′
:
ℒ
3
→
ℒ
2 are four operators such that (
ϵ
,
δ
) and (
ϵ
′
,
δ
′
) are adjunctions, then the pair (
ϵ
∘
ϵ
′
,
δ
∘
δ
′
) is also an adjunction.Given two complemented lattices,ℒ
1 and ℒ
2, two operators α and β aredual with respect to the complement of each other, if for each X
∈
ℒ
1, we have β
(
X
)
=
α
(
X
¯
)
¯. If α and β are dual of each other, then β is an erosion whenever α is a dilation.


## 3.1. Hypergraphs

We define ahypergraph [12, 18] as a pair H
=
(
H
•
,
H
×) where H
• is a set of points calledvertices and H
× is composed of a family of subsets of H
• calledhyperedges. We denote H
× by H
×
=
(
e
i
)
i
∈
I where I is a finite set of indices. The set of vertices forming the hyperedge e is denoted by v
(
e
). A vertex x in H
• is called anisolated vertex of H if x
∉
∪
i
∈
I
v
(
e
i
). Theempty hypergraph is the hypergraph H
ϕ such that H
•
=
ϕ and H
×
=
ϕ. Thepartial hypergraph
H
′ of H generated by J
⊆
I is the hypergraph H
′
=
(
H
′
•
,
H
′
×) where H
′
•
=
H
• and H
′
×
=
(
e
j
)
j
∈
J. A hypergraph X
=
(
X
•
,
X
×
) is called asubhypergraph of H, denoted by X
⊆
H, if X
•
⊆
H
• and X
×
⊆
H
×.LetX
•
⊆
H
• and X
×
⊆
H
× where X
×
=
(
e
j
)
,
j
∈
J such that J
⊆
I. We denote by X
•
¯ (resp., X
×
¯) by the complementary set of X
• (resp., X
× ). Let H
(
X
•
) and H
(
X
×
), respectively, denote the hypergraphs (
X
•
,
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
X
•
}
) and (
∪
j
∈
J
v
(
e
j
)
,
(
e
j
)
j
∈
J
).While dealing with a hypergraphH, we consider the subhypergraph induced by a subset X
• of vertices of H, namely, H
(
X
•
), and the subhypergraph induced by a subset X
× of hyperedges, namely, H
(
X
×
). H
(
X
•
) is the largest subhypergraph of H with X
• as vertex set and H
(
X
×
) is the smallest subhypergraph of H with X
× as its hyperedge set.


## 3.2. Mathematical Morphology

Now let us briefly recall some algebraic tools that are fundamental in mathematical morphology [5–7, 19]. Given two lattices ℒ
1 and ℒ
2, any operator δ
:
ℒ
1
→
ℒ
2 that distributes over the supremum and preserves the least element is called adilation (i.e.,  ∀
ε
⊆
ℒ
1
,
δ
(
∨
1
ε
)
=
∨
2
{
δ
(
X
)
∣
X
∈
ε
}
). Similarly an operator that distributes over the infimum and preserves the greatest element is called anerosion.Two operatorsϵ
:
ℒ
1
→
ℒ
2 and δ
:
ℒ
2
→
ℒ
1 form anadjunction
(
ϵ
,
δ
), if for any X
∈
ℒ
1 and any Y
∈
ℒ
2, we have δ
(
X
)
≤
1
Y
⇔
X
≤
2
ϵ
(
Y
), where ≤
1 and ≤
2 denote the order relations in ℒ
1 and ℒ
2, respectively [19]. Given two operators ϵ and δ, if the pair (
ϵ
,
δ
) is an adjunction, then ϵ is an erosion and δ is a dilation. If ℒ
1, ℒ
2, and ℒ
3 are three lattices and if δ
:
ℒ
1
→
ℒ
2, δ
′
:
ℒ
2
→
ℒ
3, ϵ
:
ℒ
2
→
ℒ
1, and ϵ
′
:
ℒ
3
→
ℒ
2 are four operators such that (
ϵ
,
δ
) and (
ϵ
′
,
δ
′
) are adjunctions, then the pair (
ϵ
∘
ϵ
′
,
δ
∘
δ
′
) is also an adjunction.Given two complemented lattices,ℒ
1 and ℒ
2, two operators α and β aredual with respect to the complement of each other, if for each X
∈
ℒ
1, we have β
(
X
)
=
α
(
X
¯
)
¯. If α and β are dual of each other, then β is an erosion whenever α is a dilation.


## 4. Hypergraph Morphology: Dilations, Erosions, and Adjunctions

In a hypergraphH, we can consider sets of points as well as sets of hyperedges. Therefore it is convenient to consider operators that go from one kind of sets to the other one. In this section we define such operators and study their morphological properties. Based on these operators, we propose several dilations, erosions, and adjunctions on various lattices formed by H.Hereafter the workspace (see [7, 8] for a similar structure defined for graphs) is a hypergraph H
=
(
H
•
,
H
×) and we consider the sets ℋ
•
,
ℋ
×, and ℋ of,respectively, all subsets of H
•, all subsets of H
×, and all subhypergraphs of ℋ.The setℋ of all subhypergraphs of a hypergraph H forms a complete lattice [15]. ℋ is not a Boolean algebra as the complement of a subhypergraph of H needs not be a subhypergraph of H. But ℋ
• and ℋ
× are Boolean algebras. We define morphological operators on these lattices. We establish a correspondence between the vertex set and the hyperedge set of H. Composing these mappings produces morphological operators on the lattices ℋ
•, ℋ
×, and ℋ.Definition 1 (vertex-hyperedge correspondence).
We define the operatorsδ
•, ϵ
• from ℋ
× into ℋ
• and the operators δ
×, ϵ
× from ℋ
• into ℋ
× as in Table 1.Table 1
ℋ
×
→
ℋ
•
ℋ
•
→
ℋ
×
Provide the object with a hypergraph structure
X
×
→
δ
•
(
X
×) such that (δ
•
(
X
×), X
×) = H
(
X
×
)
X
•
→
ϵ
×
(
X
•
) such that (
X
•
,
ϵ
×
(
X
•
) = H
(
X
•
)
Provide its complement with a hypergraph structure
X
×
→
ϵ
•
(
X
×) such that (ϵ
•
(
X
×
)
¯
,
X
×
¯
) = H
(
X
×
¯
)
X
•
→
δ
×
(
X
•
) such that (
X
•
¯
,
δ
×
(
X
•
)
¯ = H
(
X
•
¯
)These operators are illustrated in Figures2(a)–2(f). The choice of H is in such a way that every hyperedge of H is incident with exactly four vertices, and the choice of X is made to present a representative sample of the different possible configurations on subhypergraphs.Illustration of dilations and erosions.
(a)
H
(b)
X
(c)
δ
•
(
X
×
)
(d)
ϵ
×
(
X
•
)
(e)
ϵ
•
(
X
×
)
(f)
δ
×
(
X
•
)
(g)
δ
(
X
•
)
(h)
ϵ
(
X
•
)
(i)
Δ
(
X
×
)
(j)
ε
(
X
×
)
(k)
[
δ
,
Δ
]
(
X
)
(l)
[
ϵ
,
ε
]
(
X
)Property 1.
For anyX
•
⊆
H
• and any X
×
⊆
H
×, where X
×
=
(
e
j
)
,
j
∈
J such that J
⊆
I
(1)
δ
•


:
H
×
→
H
• is such that δ
•
(
X
×
)
=
∪
j
∈
J
v
(
e
j
);
(2)
ϵ
×


:
H
•
→
H
× is such that ϵ
×
(
X
•
)
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
X
•
};
(3)
ϵ
•


:
H
×
→
H
• is such that ϵ
•
(
X
×
)
=
∩
j
∉
J
v
(
e
j
)
¯;
(4)
δ
×



:
H
•
→
H
× is such that δ
×
(
X
•
)
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
∩
X
•
≠
ϕ
}.Proof.
(1) and (2) follow from the definition ofδ
• and ϵ
×.
(3)H
(
X
×
¯
)
=
(
∪
j
∉
J
v
(
e
j
)
,
(
e
j
)
j
∉
J
). Thus,
(1)
ϵ
•
(
X
×
)
=
⋃
j
∉
J
v
(
e
j
)
¯
=
⋂
j
∉
J
v
(
e
j
)
¯
(
By
De
Morgan's
Law
)
.
(4)δ
×
(
X
•
)
¯
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
X
•
¯
}
). Thus, δ
×
(
X
•
)
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
∩
X
•
≠
ϕ
}.Note thatδ
•
(
X
×
)
=
{
x
∈
H
•
∣
∃
e
j
∈
X
× such that x
∈
v
(
e
j
) for some j
∈
J
}. This property states that δ
•
(
X
×
) is the set of all vertices which belong to a hyperedge of X
×, ϵ
×
(
X
•
) is the set of all hyperedges whose vertices are composed of vertices of X
•, ϵ
•
(
X
×
) is the set of all vertices which do not belong to any edge of X
×
¯, and δ
×
(
X
•
) is the set of all hyperedges in H
× with at least one vertex in X
•. Therefore the previous property locally characterizes the operators defined in vertex-hyperedge correspondence. This property leads to simple linear time algorithms (with respect to |
H
•
| and |
H
×
|) to compute δ
•, δ
×, ϵ
•, and ϵ
×.Property 2 (dilation, erosion, adjunction, and duality).
(1) Operatorsϵ
× and δ
× (resp., ϵ
• and δ
•) are dual of each other.
(2) Both(
ϵ
×
,
δ
•
) and (
ϵ
•
,
δ
×
) are adjunctions.
(3) Operatorsϵ
• and ϵ
× are erosions.
(4) Operatorsδ
• and δ
× are dilations.Proof.
(1) We will prove thatδ
×
(
X
•
¯
)
¯
=
ϵ
×
(
X
•
) and δ
•
(
X
×
¯
)
¯
=
ϵ
•
(
X
×
):
(2)
δ
×
(
X
•
¯
)
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
∩
X
•
¯
≠
ϕ
}
(
By
Property
1
of
δ
×
)
δ
×
(
X
•
¯
)
¯
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
X
•
}
δ
×
(
X
•
¯
)
¯
=
ϵ
×
(
X
•
)
.
Thus, ϵ
× and δ
× are duals:
(3)
δ
•
(
X
×
)
=
⋃
j
∈
J
v
(
e
j
)
δ
•
(
X
×
¯
)
=
⋃
j
∉
J
v
(
e
j
)
δ
•
(
X
×
¯
)
¯
=
⋃
j
∉
J
v
(
e
j
)
¯
δ
•
(
X
×
¯
)
¯
=
⋂
j
∉
J
v
(
e
j
)
¯
(
By
De
Morgan's
Law
)
δ
•
(
X
×
¯
)
¯
=
ϵ
•
(
X
×
)
.
Therefore, ϵ
• and δ
• are duals.
(2) Suppose thatX
×
⊆
ϵ
×
(
Y
•
). Then,
(4)
x
∈
δ
•
(
X
×
)
⟹
x
∈
⋃
j
∈
J
v
(
e
j
)
⟹
x
∈
v
(
e
j
)
for
some
j
∈
J
⟹
∃
e
∈
X
×
such
that
x
∈
v
(
e
)
⟹
e
∈
ϵ
×
(
Y
•
)
(
∵
X
×
⊆
ϵ
×
(
Y
•
)
)
⟹
e
∈
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
Y
•
}
⟹
v
(
e
)
⊆
Y
•
⟹
x
∈
Y
•
(
∵
x
∈
v
(
e
)
)
.
Therefore, δ
•
(
X
×
)
⊆
Y
•.
Conversly, ifδ
•
(
X
×
)
⊆
Y
•, then,
(5)
e
∈
X
×
⟹
v
(
e
)
⊆
δ
•
(
X
×
)
⟹
v
(
e
)
⊆
Y
•
(
∵
δ
•
(
X
×
)
⊆
Y
•
)
⟹
e
∈
ϵ
×
(
Y
•
)
.
Thus, X
×
⊆
ϵ
×
(
Y
•
). Therefore, (
ϵ
×
,
δ
•
) is an adjunction:
(6)
δ
×
(
X
•
)

⊆
Y
×
⟺
ϵ
×
(
X
•
¯
)
¯
⊆
Y
×


(
By
duality
of
ϵ
×
and
δ
×
)
⟺
Y
×
¯
⊆
ϵ
×
(
X
•
¯
)
⟺
δ
•
(
Y
×
¯
)
⊆
X
•
¯
(
By
adjunction
property
of
(
ϵ
×
,
δ
•
)
)
⟺
X
•
⊆
δ
•
(
Y
×
¯
)
¯
⟺
X
•
⊆
ϵ
•
(
Y
×
)
(
By
duality
of
ϵ
•
and
δ
•
)
.
Therefore, (
ϵ
•
,
δ
×
) is an adjunction.
Properties (3) and (4) follow from the dilation/erosion property of adjunctions.Definition 2 (vertex dilation, vertex erosion).
We defineδ and ϵ that act on ℋ
• by δ
=
δ
•
∘
δ
× and ϵ
=
ϵ
•
∘
ϵ
×.Property 3.
For anyX
•
⊆
H
•, (1)
δ
(
X
•
)
=
{
x
∈
H
•
∣
∃
e
i
,
i
∈
I such that x
∈
v
(
e
i
)
and
v
(
e
i
)
∩
X
•
≠
ϕ
};
(2)
ϵ
(
X
•
)
=
{
x
∈
H
•
∣
∀
e
i
,
i
∈
I such that x
∈
v
(
e
i
)
,
v
(
e
i
)
⊆
X
•
}.Proof.
Consider the following:
(1)(7)
δ
(
X
•
)
=
δ
•
(
δ
×
(
X
•
)
)
=
δ
•
[
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⋂
X
•
≠
ϕ
}
]
(
By
Property
1
of
δ
×
)
=
⋃
i
∈
I
,
v
(
e
i
)
∩
X
•
≠
ϕ
v
(
e
i
)
(
By
Property
1
of
δ
•
)
=
{
⋂
X
•
x
∈
H
•
∣
∃
e
i
,
i
∈
I
such
that
x
∈
v
(
e
i
)
,
v
(
e
i
)
⋂
X
•
≠
ϕ
}
,
(2)(8)
ϵ
(
X
•
)
=
ϵ
•
(
ϵ
×
(
X
•
)
)
=
ϵ
•
[
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⊆
X
•
}
]
(
By
Property
1
of
ϵ
×
)
=
⋂
i
∈
I
,
v
(
e
i
)
⊈
X
•
v
(
e
i
)
¯
(
By
Property
1
of
ϵ
•
)
=
{
x
∈
X
•
∣
∀
e
i
∈
H
×
with
x
∈
v
(
e
i
)
,
v
(
e
i
)
⊆
X
•
}
.Definition 3 (hyper-edge dilation, hyper-edge erosion).
We defineΔ and ε that act on ℋ
× by Δ
=
δ
×
∘
δ
• and ε
=
ϵ
×
∘
ϵ
•.Property 4.
For anyX
×
⊆
H
×, X
×
=
(
e
j
)
j
∈
J:(1)
Δ
(
X
×
)
=
{
e
i
,
i
∈
I
∣
∃
e
j
,
j
∈
J such that v
(
e
i
)
∩
v
(
e
j
)
≠
ϕ
};
(2)
ε
(
X
×
)
=
{
e
j
,
j
∈
J
∣
v
(
e
j
)
∩
v
(
e
i
)
=
ϕ
,
∀
i
∈
I
∖
J
}.Proof.
Consider the following:
(1)(9)
Δ
(
X
×
)
=
δ
×
∘
δ
•
(
X
×
)
=
δ
×
[
⋃
j
∈
J
v
(
e
j
)
]
(
By
property
1
of
δ
×
)
=
{
e
i
,
i
∈
I
∣
v
(
e
i
)
⋂
[
⋃
j
∈
J
v
(
e
j
)
]
≠
ϕ
}
.
(
By
property
1
of
δ
•
)
=

{
e
i
,
i
∈
I
∣
∃
e
j
,
j
∈
J
such
that
v
(
e
i
)
⋂
v
(
e
j
)

≠
ϕ
}
,
(2)(10)
ε
(
X
×
)
=
ϵ
×
∘
ϵ
•
(
X
×
)
=
ϵ
×
[
⋂
i
∈
I
∖
J
v
(
e
i
)
¯
]
(
By
property
1
of
ϵ
•
)
=
{
e
j
,
j
∈
J
∣
v
(
e
j
)
⊆
[
⋂
i
∈
I
∖
J
v
(
e
i
)
¯
]
=
{
e
j
,
j
∈
J
∣
v
(
e
j
)
⊆
[
⋃
i
∈
I
∖
J
v
(
e
i
)
¯
]
}
(
By
De
Morgan's
Law
)
=
{
e
j
,
j
∈
J
∣
v
(
e
j
)
⋂
v
(
e
i
)
=
ϕ
,
∀
i
∈
I
∖
J
}
.Remark 4.
Being the compositions of, respectively, dilations and erosions,δ and ϵ are, respectively, a dilation and an erosion [19]. Moreover by composition of adjunctions and dual operators, δ and ϵ are dual and (
ϵ
,
δ
) is an adjunction. In a similar manner (
ε
,
Δ
) is also an adjunction.Definition 5 (hypergraph dilation, hypergraph erosion).
We define the operators[
δ
,
Δ
] and [
ϵ
,
ε
] by, respectively, [
δ
,
Δ
]
(
X
)
=
(
δ
(
X
•
)
,
Δ
(
X
×
)
) and [
ϵ
,
ε
]
(
X
)
=
(
ϵ
(
X
•
)
,
ε
(
X
×
)
), for any X
∈
ℋ.Theorem 6.
The operators[
δ
,
Δ
] and [
ϵ
,
ε
] are, respectively, a dilation and an erosion acting on the lattice (
ℋ
,
⊆
).Proof.
We will prove that for everye
∈
Δ
(
X
×
), v
(
e
)
⊆
δ
(
X
•
). e
∈
Δ
(
X
×
) implies that there exists some j
∈
J such that v
(
e
)
∩
v
(
e
j
)
≠
ϕ. But v
(
e
j
)
⊆
X
•, since j
∈
J. Thus, v
(
e
)
∩
X
•
≠
ϕ. Therefore, v
(
e
)
⊆
∪
j
∈
J
,
v
(
e
i
)
∩
X
•
≠
ϕ
v
(
e
i
)
=
δ
(
X
•
). This implies [
δ
,
Δ
]
(
X
)
∈
ℋ.
Ife
∈
ε
(
X
×
), then v
(
e
)
∩
v
(
e
i
)
=
ϕ for every i
∈
I
∖
J, and so v
(
e
)
∩
[
∪
i
∈
I
∖
J
v
(
e
i
)
]
=
ϕ:
(11)
v
(
e
)
⊆
⋃
i
∈
I
∖
J
v
(
e
i
)
¯
=
⋂
i
∈
I
∖
J
v
(
e
i
)
¯
⊆
⋂
v
(
e
i
)
⊈
X
•
v
(
e
i
)
¯
(
Since
v
(
e
i
)
⊆
X
•
,
∀
i
∈
J
)
=
ε
(
X
•
)
(
By
Property
3
of
ε
)
.
Therefore, [
ϵ
,
ε
]
(
X
)
∈
ℋ.Theorem 7.
(
[
ϵ
,
ε
]
,
[
δ
,
Δ
]
) is an adjunction.Proof.
LetX and Y be two hypergraphs in ℋ. The following statements are equivalent:
(12)
[
δ
,
Δ
]
(
X
)
⊆
Y
δ
(
X
•
)
⊆
Y
•
,
Δ
(
X
×
)
⊆
Y
×
X
•
⊆
ϵ
(
Y
•
)
,
X
×
⊆
ε
(
Y
×
)
(
since
[
ϵ
,
ε
]
,
and
[
δ
,
Δ
]
are
adjunctions
on
⁡
ℋ
)
X
⊆
[
ϵ
,
ε
]
(
Y
)
.
Thus the pair (
[
ϵ
,
ε
]
,
[
δ
,
Δ
]
) is an adjunction, which implies that [
ϵ
,
ε
] is an erosion and [
δ
,
Δ
] is a dilation.


## 5.  Conclusion

This paper investigates the lattice of all subhypergraphs of a hypergraphH and provides it with morphological operators. By the composition of the operators presented in this paper, we can define other adjunctions on hypergraphs. The proposed framework can be extended to morphological filtering on hypergraphs and is left to the future work.



---

*Source: 436419-2014-03-13.xml*