# Decomposable Convexities in Graphs and Hypergraphs

Authors: Francesco M. Malvestuto
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

Given a connected hypergraphℋwith vertex set V, a convexity space on ℋ is a subset
𝒞 of the powerset of V that contains ∅, V, and the singletons; furthermore, 𝒞 is closed under intersection and every set in 𝒞 is connected in ℋ. The members of 𝒞 are called convex sets. The convex hull of a subset X of V is the smallest convex set containing X. By a cluster of ℋ we mean any nonempty subset of V in which every two vertices are separated by no convex set. We say that a convexity space on ℋ is decomposable if it satisfies the following three axioms: (i) the maximal clusters of ℋ form an acyclic hypergraph, (ii) every maximal cluster of ℋ is a convex set, and (iii) for every nonempty vertex set X, a vertex does not belong to the convex hull of X if and only if it is separated from X by a convex cluster. We prove that a decomposable convexity space 𝒞 on ℋ is fully specified by the maximal clusters of ℋ in that (1) there is a closed formula which expresses the convex hull of a set in terms of certain convex clusters of ℋ and (2) 𝒞 is a convex geometry if and only if the subspaces of 𝒞 induced by maximal clusters of ℋ are all convex geometries. Finally, we prove the decomposability of some known convexities in graphs and hypergraphs taken from the literature (such as “monophonic” and “canonical” convexities in hypergraphs and “all-paths” convexity in graphs).


---

## Body

## 1. Introduction

A (finite) convexity space [1] over a finite nonempty set V is a subset 𝒞 of the powerset of V that contains ∅ and V and is closed under intersection. The members of 𝒞 are called convex sets. The convex hull of a subset X of V, denoted by 〈X〉, is the smallest convex set containing X. It is well known that (i) X⊆〈X〉, (ii) if X⊆Y then 〈X〉⊆〈Y〉, and (iii) 〈〈X〉〉=〈X〉. A convexity space 𝒞 over V is a point-convexity space [2] if, for every element ν of V, the singleton {ν} is a convex set. Abstract convexity theory has been applied to graphs [3–6] and hypergraphs [4, 7]. A convexity space on a connected hypergraph is a point-convexity space 𝒞 such that every convex set is connected. If X is a convex set, the subspace of 𝒞induced by X is the convexity space 𝒞(X)={A∩X:A∈𝒞} on the (connected) subhypergraph induced by X.Most convexities in graphs and hypergraphs have been stated in terms of  “feasible” paths [8]; accordingly, a vertex set X is convex if X contains all vertices on every feasible path joining two vertices in X. For example, geodetic convexity, monophonic convexity, and all-paths convexity are obtained using shortest paths, chordless paths, or all paths, respectively.We note that in graphs monophonic convexity (m-convexity, for short) and all-paths convexity (ap-convexity, for short) enjoy similar properties. For example, Duchet [5] proved that “a vertex ν does not belong to the m-convex hull of a set X if and only if ν is separated from X by a clique,” and known results on ap-convexity [3, 9] imply that “a vertex ν does not belong to the ap-convex hull of a set X if and only if ν is separated from X by a cut-vertex.” This similarity also applies to the algorithms to compute m-convex hulls [7, 9–11] and ap-convex hulls [9].In this paper, we show thatm-convexity and ap-convexity belong to a wide class of convexity spaces on hypergraphs, which we call “decomposable” and define by means of three axioms. To this end, we need to introduce the notion of a “cluster.”Let𝒞 be a convexity space on a connected hypergraph ℋ with vertex set V. Acluster of ℋ is a nonempty subset of V in which every two vertices are separated by no convex set. The cluster hypergraph of ℋ is the set of maximal clusters of ℋ. A convexity space on ℋ is decomposable if it satisfies the following three axioms.Axiom.
The cluster hypergraph ofℋ is acyclic.Axiom.
Every edge of the cluster hypergraph ofℋ is a convex set.Axiom.
For every nonempty vertex setX, a vertex does not belong to the convex hull of X if and only if it is separated from X by a convex cluster.Our main result is that if𝒞 is a decomposable convexity space on ℋ, then 𝒞 enjoys the following two properties.(D1)
there is a closed formula which expresses the convex hull of a set in terms of certain convex clusters ofℋ.(D2)
𝒞 is a convex geometry if and only if the subspaces of 𝒞 induced by maximal clusters of ℋ are all convex geometries.The rest of the paper is organized as follows. In Section2 we recall more-or-less standard definitions and some preliminary results on acyclic hypergraphs, which will be used in the sequel. In Section 3 we state general properties of the cluster hypergraph. In Section 4 we prove some properties of convexity spaces that satisfy Axioms 1 and 2. In Section 5 we prove that decomposable convexity spaces enjoy properties (D1) and (D2). In Section 6, we give three examples of decomposable convexity spaces taken from the literature. Finally, Section 7 contains a closing note.


## 2. Preliminaries

LetV be a finite set. A hypergraph [12] on V is a nonempty set of subsets of V whose union recovers V. The elements of V are the verticesof ℋ and the sets in ℋ are the (hyper) edges of ℋ. If V=∅, then we call ℋ={∅} theempty hypergraph. A nonempty hypergraph is trivialif it has exactly one edge. A hypergraph is simple if no edge is a subset of another edge. A partial hypergraph of hypergraph ℋ is a nonempty subset of ℋ. A cover of ℋ is a simple hypergraph 𝒦 on V such that each edge of ℋ is contained in some edge of 𝒦.A vertex is aleaf if it belongs to exactly one edge.Two vertices areadjacent if they belong together to some edge. A vertex ν is adjacent to a vertex set X if X contains a vertex u such that u and ν are adjacent.Aclique is a nonempty vertex set in which every two vertices are adjacent. A partial edge is a nonempty vertex set included in some edge. A hypergraph is conformal if every clique is a partial edge. The clique hypergraph of a hypergraph ℋ is the hypergraph whose edges are precisely the maximal cliques of ℋ.A (vertex) pathis a sequence of distinct vertices (u1,u2,…,uk),k≥1, such that if k>1 then uh and uh+1 are adjacent for h=1,…,k-1; the path is said to joinu1 and uk from u1 to uk and to pass through any set X such that X∩{u2,…,uk-1}≠∅. A hypergraph is connected if every two vertices are joined by a path. The connected components of a hypergraph are its maximal partial hypergraphs that are connected.LetX be a nonempty subset of V; the subhypergraphof ℋinduced by X is the hypergraph on X, denoted by ℋ(X), whose edges are the nonempty intersections of X with edges of ℋ. A subset X of V is connected if ℋ(X) is connected.LetX be a nonempty proper subset of V; by ℋ-X we denote the subhypergraph of ℋ induced by V∖X. If ℋ′ is a connected component of ℋ-X, the neighborhood of ℋ′, denoted by N(ℋ′), is the set of vertices in X that are adjacent to the vertex set of ℋ′.A vertexν is separated from a set Y by X if ν∉X∪Y and Y is disjoint from the vertex set of the connected component of ℋ-X containing ν.In the next two subsections we deal with “separators” and “acyclic hypergraphs.”


### 2.1. Separators

Letℋ be a connected hypergraph with vertex set V. A subset X of V is a separator of ℋ if ℋ-X is not connected. If X is a separator of ℋ, then X is said to separate every two vertices that are in distinct connected components of ℋ-X. Note that X separates two vertices u and ν if and only if X∩{u,ν}=∅ and every path joining u and ν passes through X. A separator X separates a subset Y of V if X separates two distinct vertices in Y. A set X is a minimal separator for a vertex pair {u,ν} if u and ν are separated by X and are separated by no proper subset of X. A set X is a minimal vertex separator (MVS) [13] of ℋ if there exists a vertex pair for which X is a minimal separator.


### 2.2. Acyclic Hypergraphs

A hypergraph isacyclic if there exists a running-intersection ordering(A1,A2,…,An) of its edges, that is, if n>1 then, for each i>1 there exists ji<i such that
(1)(A1∪⋯∪Ai-1)∩Ai=Aji∩Ai.
Several equivalent definitions of acyclicity exist [14]. A test for acyclicity is given by the following algorithm which reduces a hypergraph ℋ to the empty hypergraph {∅} if and only if ℋ is acyclic [14].Graham Reduction.
Repeatedly apply the following two operations until neither can be longer applied:(vertex deletion): remove a vertex if it is a leaf.(edge deletion): remove an edge if it is contained in another edge.A more efficient algorithm to test acyclicity was given in [15]. The following two facts state well known properties of MVSs of an acyclic hypergraph [14, 16] and they will be used in the sequel.Fact 1.
Letℋ be an acyclic, simple, and connected hypergraph. The MVSs of ℋ are exactly the partial edges of ℋ that are removed during the Graham reduction of ℋ.Fact 2.
Letℋ be an acyclic, simple, and connected hypergraph. If Y is an MVS of ℋ, then there exist two edges A and B of ℋ such that Y=A∩B and, for every u∈A∖B and ν∈B∖A, Y is the only minimal separator for {u,ν}.For our purposes, we need a modification of Graham reduction when there is a setX of sacred vertices that may not be deleted by vertex deletion. Let GR(ℋ,X) denote the result of applying Graham reduction to a hypergraph ℋ with the vertex deletion rule modified to disallow the removal of any vertex in X, the application of rules proceeding until such time as no more applications are possible [16]. We call GR(ℋ,X) the Graham reduction of ℋwith sacred setX. It is well known [16] that GR(ℋ,X) is defined uniquely, that is, if a deletion rule is applicable to a vertex or edge, applying a rule elsewhere does not make the first inapplicable; so, the reduction procedure proceeds to do everything that is ever possible, independent of the order of reductions chosen. In other words, the Graham reduction process enjoys the so-called Church-Rosser property [16], which makes it a pruning process according to the terminology used in [17]. It is also well known [16] that if ℋ is an acyclic, simple and connected hypergraph, then(i)
GR(ℋ,X) is an acyclic, simple, and connected hypergraph;(ii)
the edges ofGR(ℋ,X) are the maximal edges of an induced subhypergraph of ℋ whose vertex set contains X;(iii)
X is a subset of the vertex set of GR(ℋ,X);(iv)
the MVSs ofℋ are the MVSs of GR(ℋ,X) plus the partial edges ℋ removed during the Graham reduction process.The following lemma contains one more property ofGR(ℋ,X) which will be used later on.Lemma 1 (see [18]).
Letℋ be an acyclic hypergraph on V, X a nonempty proper subset of V, and u a vertex in V∖X. The following holds:(i)
a vertexu of ℋ belongs to the vertex set of GR(ℋ,X) if and only if u is separated from X by no partial edge of ℋ;(ii)
ifu is not a vertex of GR(ℋ,X), then there exists an edge of GR(ℋ,X) that separates u from X in ℋ;(iii)
ifA is an edge of GR(ℋ,X), then A is the union of A∩X with the neighborhoods of the connected components of ℋ-A whose vertex sets are not disjoint from X.Figure1 illustrates part (iii) of Lemma 1 for the two cases in which A∩X=∅ and A∩X≠∅.Figure 1Corollary 2.
Letℋ be an acyclic hypergraph on V, X a nonempty proper subset of V, and u a vertex in V∖X. If A is an edge of GR(ℋ,X), u is not a vertex of GR(ℋ,X), and A∪{u} is a partial edge of ℋ, then A is contained in every partial edge of ℋ that separates u from X in ℋ.Proof.
First of all, observe that the connected component ofℋ-A that contains u has an empty intersection with X. Let B be a partial edge of ℋ that separates u from X in ℋ, and let Z be the vertex set of a connected component ℋ′ of ℋ-A such that Z∩X≠∅. Then B must contain the neighborhood of ℋ′ for, otherwise, u and each vertex in Z∩X would be in the same connected component of ℋ-B. Moreover, A∩X⊆B for, otherwise, u and some vertex in A∩X would be in the same connected component of ℋ-B. From part (iii) of Lemma 1, it follows that A⊆B.


## 2.1. Separators

Letℋ be a connected hypergraph with vertex set V. A subset X of V is a separator of ℋ if ℋ-X is not connected. If X is a separator of ℋ, then X is said to separate every two vertices that are in distinct connected components of ℋ-X. Note that X separates two vertices u and ν if and only if X∩{u,ν}=∅ and every path joining u and ν passes through X. A separator X separates a subset Y of V if X separates two distinct vertices in Y. A set X is a minimal separator for a vertex pair {u,ν} if u and ν are separated by X and are separated by no proper subset of X. A set X is a minimal vertex separator (MVS) [13] of ℋ if there exists a vertex pair for which X is a minimal separator.


## 2.2. Acyclic Hypergraphs

A hypergraph isacyclic if there exists a running-intersection ordering(A1,A2,…,An) of its edges, that is, if n>1 then, for each i>1 there exists ji<i such that
(1)(A1∪⋯∪Ai-1)∩Ai=Aji∩Ai.
Several equivalent definitions of acyclicity exist [14]. A test for acyclicity is given by the following algorithm which reduces a hypergraph ℋ to the empty hypergraph {∅} if and only if ℋ is acyclic [14].Graham Reduction.
Repeatedly apply the following two operations until neither can be longer applied:(vertex deletion): remove a vertex if it is a leaf.(edge deletion): remove an edge if it is contained in another edge.A more efficient algorithm to test acyclicity was given in [15]. The following two facts state well known properties of MVSs of an acyclic hypergraph [14, 16] and they will be used in the sequel.Fact 1.
Letℋ be an acyclic, simple, and connected hypergraph. The MVSs of ℋ are exactly the partial edges of ℋ that are removed during the Graham reduction of ℋ.Fact 2.
Letℋ be an acyclic, simple, and connected hypergraph. If Y is an MVS of ℋ, then there exist two edges A and B of ℋ such that Y=A∩B and, for every u∈A∖B and ν∈B∖A, Y is the only minimal separator for {u,ν}.For our purposes, we need a modification of Graham reduction when there is a setX of sacred vertices that may not be deleted by vertex deletion. Let GR(ℋ,X) denote the result of applying Graham reduction to a hypergraph ℋ with the vertex deletion rule modified to disallow the removal of any vertex in X, the application of rules proceeding until such time as no more applications are possible [16]. We call GR(ℋ,X) the Graham reduction of ℋwith sacred setX. It is well known [16] that GR(ℋ,X) is defined uniquely, that is, if a deletion rule is applicable to a vertex or edge, applying a rule elsewhere does not make the first inapplicable; so, the reduction procedure proceeds to do everything that is ever possible, independent of the order of reductions chosen. In other words, the Graham reduction process enjoys the so-called Church-Rosser property [16], which makes it a pruning process according to the terminology used in [17]. It is also well known [16] that if ℋ is an acyclic, simple and connected hypergraph, then(i)
GR(ℋ,X) is an acyclic, simple, and connected hypergraph;(ii)
the edges ofGR(ℋ,X) are the maximal edges of an induced subhypergraph of ℋ whose vertex set contains X;(iii)
X is a subset of the vertex set of GR(ℋ,X);(iv)
the MVSs ofℋ are the MVSs of GR(ℋ,X) plus the partial edges ℋ removed during the Graham reduction process.The following lemma contains one more property ofGR(ℋ,X) which will be used later on.Lemma 1 (see [18]).
Letℋ be an acyclic hypergraph on V, X a nonempty proper subset of V, and u a vertex in V∖X. The following holds:(i)
a vertexu of ℋ belongs to the vertex set of GR(ℋ,X) if and only if u is separated from X by no partial edge of ℋ;(ii)
ifu is not a vertex of GR(ℋ,X), then there exists an edge of GR(ℋ,X) that separates u from X in ℋ;(iii)
ifA is an edge of GR(ℋ,X), then A is the union of A∩X with the neighborhoods of the connected components of ℋ-A whose vertex sets are not disjoint from X.Figure1 illustrates part (iii) of Lemma 1 for the two cases in which A∩X=∅ and A∩X≠∅.Figure 1Corollary 2.
Letℋ be an acyclic hypergraph on V, X a nonempty proper subset of V, and u a vertex in V∖X. If A is an edge of GR(ℋ,X), u is not a vertex of GR(ℋ,X), and A∪{u} is a partial edge of ℋ, then A is contained in every partial edge of ℋ that separates u from X in ℋ.Proof.
First of all, observe that the connected component ofℋ-A that contains u has an empty intersection with X. Let B be a partial edge of ℋ that separates u from X in ℋ, and let Z be the vertex set of a connected component ℋ′ of ℋ-A such that Z∩X≠∅. Then B must contain the neighborhood of ℋ′ for, otherwise, u and each vertex in Z∩X would be in the same connected component of ℋ-B. Moreover, A∩X⊆B for, otherwise, u and some vertex in A∩X would be in the same connected component of ℋ-B. From part (iii) of Lemma 1, it follows that A⊆B.


## 3. The Cluster Hypergraph

Let𝒞 be a convexity space on a connected hypergraph ℋ. Recall from the Introduction that a cluster of ℋ is a nonempty vertex set that is separated by no convex set of ℋ, and the cluster hypergraph of ℋ is the hypergraph, henceforth denoted by 𝒦, whose edges are precisely the maximal clusters of ℋ. In this section, we shall state some general properties of the cluster hypergraph.Theorem 3.
Letℋ be a connected hypergraph and 𝒞 a convexity space on ℋ. The cluster hypergraph 𝒦 of ℋ is a cover of the clique hypergraph of ℋ and is a conformal hypergraph.Proof.
Since every clique ofℋ is a cluster, every maximal clique of ℋ is a partial edge of 𝒦, that is, 𝒦 is a cover of the clique hypergraph of ℋ. Moreover, since two vertices u and ν of 𝒦 are adjacent (in 𝒦) if and only if {u,ν} is a cluster of ℋ, one has that every clique of 𝒦 is a cluster of ℋ and, hence, a partial edge of 𝒦.By Theorem3, 𝒦 is a cover of ℋ so that every separator of 𝒦 is also a separator of ℋ. We now prove that the converse also holds for convex separators of ℋ.Lemma 4.
Letℋ be a connected hypergraph, 𝒞 a convexity space on ℋ, 𝒦 the cluster hypergraph of ℋ, and X a convex set of ℋ. Two vertices that are separated by X in ℋ are also separated by X in 𝒦.Proof.
Letu and ν be two vertices that are separated by X in ℋ. Since X is a convex set, the vertex pair {u,ν} is not a cluster of ℋ and, hence, u and ν are not adjacent in 𝒦. Suppose, by contradiction, that u and ν are not separated by X in 𝒦. Then, there exists in 𝒦 a path (u1=u,u2,…,uk=ν),  k≥3, such that uh∉X for all h, 1≤h≤k. Since each vertex pair {uh,uh+1} is a partial edge of 𝒦, the set {uh,uh+1} is a cluster of ℋ and, since X is a convex set, uh and uh+1 cannot be separated by X in ℋ so that in ℋ there exists a path ph from uh to uh+1 such that no vertex on ph belongs to X. Combining the paths p1,p2,…,pk-1, we obtain a path p in ℋ from u to ν and no vertex on p belongs to X, which contradicts the hypothesis that u and ν are separated by X in ℋ.The next lemma is useful for the sequel.Lemma 5.
Letℋ be a connected hypergraph, 𝒞 a convexity space on ℋ, 𝒦 the cluster hypergraph of ℋ, and X a convex set. If the vertex sets of a connected component of ℋ-X and of a connected component of 𝒦-X are not disjoint, then they coincide.Proof.
LetY be the vertex set of a connected component of ℋ-X and Z the vertex set of a connected component of 𝒦-X such that Y∩Z≠∅. By Theorem 3, 𝒦 is a cover of ℋ and, since Y∩Z≠∅, one has Y⊆Z. Suppose, by contradiction, that Y≠Z, and let u∈Y and ν∈Z∖Y. Since neither u nor ν are in X, u, and ν are separated by X in ℋ. By Lemma 4, u and ν are separated by X in 𝒦, which contradicts the fact that u and ν are both in Z.The next result relates the MVSs of the cluster hypergraph ofℋ with “minimal vertex convex separators” of ℋ, which we define as follows. A convex set X of ℋ is a minimal convex separator of ℋ for a vertex pair {u,ν} if u and ν are separated by X and are separated by no convex proper subset of X. A set X is a minimal vertex convex separator (MVCS) of ℋ if there exists a vertex pair for which X is a minimal convex separator.Theorem 6.
Letℋ be a connected hypergraph, 𝒞 a convexity space on ℋ, and 𝒦 the cluster hypergraph of ℋ. Every MVCS of ℋ is the convex hull of an MVS of 𝒦.Proof.
LetX be an MVCS of ℋ, and let {u,ν} be a vertex pair for which X is a minimal convex separator of ℋ. Since X is a convex set, X separates u and ν in 𝒦 by Lemma 4; therefore, X must contain a minimal separator of 𝒦 for {u,ν}. Let Y be such an MVS of 𝒦. Since Y⊆X, one has 〈Y〉⊆〈X〉=X and, hence, neither u nor ν belongs to 〈Y〉. Therefore, since Y separates u and ν in 𝒦 and since Y⊆〈Y〉, also the set 〈Y〉 separates u and ν in 𝒦 and, since 𝒦 is a cover of ℋ, the set 〈Y〉 separates u and ν in ℋ. Finally, since 〈Y〉⊆X and X is a minimal convex separator of ℋ for {u,ν}, one has 〈Y〉=X.Example 7.
Consider the (hyper)graphℋ with vertex set V={a,b,c,d,e} that is shown in Figure 2, and the convexity space 𝒞 that only contains ∅, V, the five singletons, and the set {a,d,e}. The MVCSs of ℋ are the set {d} (which is a minimal convex separator for the vertex pairs {a,e}, {b,e}, and {c,e}) and the set {a,d,e} (which is a minimal convex separator for the vertex pair {b,c}). The cluster hypergraph of ℋ is 𝒦={{a,b,d},{a,c,d},{d,e}}. The MVSs of 𝒦 are the set {d} (which is a minimal separator for the vertex pairs {a,e}, {b,e}, and {c,e}) and the set {a,d} (which is a minimal separator for the vertex pair {b,c}). The MVCS {a,d,e} of ℋ is the convex hull of the MVS {a,d} of 𝒦, and the MVCS {d} of ℋ is the convex hull of the MVS {d} of 𝒦.Figure 2


## 4. Axioms1 and 2

In this section we state some properties of convexity spaces that satisfy Axioms1 and 2. Recall that a convexity space on ℋ satisfies Axiom 1 if the cluster hypergraph of ℋ is acyclic, and satisfies Axiom 2 if every maximal cluster of ℋ is a convex set. First of all, observe that the following condition is equivalent to Axiom 2.Fact 3.
Letℋ be a connected hypergraph. A convexity space 𝒞 on ℋ satisfies Axiom 2 if and only if the convex hull of every cluster is a cluster.Proof of (“only if”).
LetY be any cluster of ℋ and X a maximal cluster containing Y. By Axiom 2, X is a convex set. Since Y⊆X, one has 〈Y〉⊆〈X〉=X and, hence, 〈Y〉 is a cluster.Proof of (“if”).
LetX be any maximal cluster of ℋ. We need to prove that X=〈X〉. Of course, X⊆〈X〉. By hypothesis, 〈X〉 is a cluster. Let Y be a maximal cluster of ℋ that contains 〈X〉. Then, one has X⊆〈X〉⊆Y. Since X is a maximal cluster, one has X=Y so that X=〈X〉.The following are two properties of convexity spaces that satisfy both Axioms1 and 2.Theorem 8.
Letℋ be a connected hypergraph, 𝒞 a convexity space on ℋ and 𝒦 the cluster hypergraph of ℋ. If 𝒞 satisfies Axioms 1 and 2, then every MVS of 𝒦 is a convex set.Proof.
Since𝒞 satisfies Axiom 1, 𝒦 is an acyclic hypergraph. Let Y be any MVS of 𝒦. By Fact 2, Y=A∩B for some two edges A and B of 𝒦. Since 𝒞 satisfies Axiom 2, A and B are convex sets of ℋ so that Y is a convex set of ℋ.Corollary 9.
Letℋ be a connected hypergraph, 𝒞 a convexity space on ℋ, and 𝒦 the cluster hypergraph of ℋ. If 𝒞 satisfies Axioms 1 and 2, then the MVCSs of ℋ are exactly the MVSs of  𝒦.Proof.
We first prove that (i) every MVCS ofℋ is an MVS of 𝒦 and, then, that (ii) every MVS of 𝒦 is an MVCS of H.
Proof of (i). Let X be an MVCS of ℋ. By Theorem 6, there exists an MVS Y of 𝒦 such that X=〈Y〉. By Theorem 8, 〈Y〉=Y so that X=Y.
Proof of (ii). Let Y be an MVS of 𝒦. Since 𝒦 is acyclic, by Fact 2 there exists a vertex pair {u,ν} for which Y is the only minimal separator in 𝒦. Therefore, u and ν are not adjacent in 𝒦 so that {u,ν} is not a cluster of ℋ. Let X be a minimal convex separator of ℋ for {u,ν}. By Lemma 4, X separates u and ν in 𝒦. Since Y is the only minimal vertex separator for {u,ν} in 𝒦, one has that Y⊆X. On the other hand, since Y is convex by Theorem 8 and since 𝒦 is a cover of ℋ, Y is also a convex separator of ℋ for {u,ν}. Finally, since X is a minimal convex separator of ℋ for {u,ν}, one has Y=X.Example 10.
Consider again the (hyper)graphℋ of Figure 2 and the convexity space 𝒞 on ℋ that only contains ∅, V, the singletons and the four sets {a,b,d}, {a,c,d}, {a,d} and {d,e}. The MVCSs of ℋ are {d} and {a,d} and the cluster hypergraph is 𝒦={{a,b,d},{a,c,d},{d,e}}. Since 𝒦 is an acyclic hypergraph and its edges are all convex sets, 𝒞 satisfies Axioms 1 and 2. Note that the MVCSs of ℋ are exactly the MVSs of  𝒦.


## 5. Decomposable Convexity Spaces

Recall that a convexity space𝒞 on ℋ is decomposable if 𝒞 satisfies Axioms 1 and 2 and, for every subset X of V, the convex hull of X equals the set of vertices that are separated from X by no convex cluster of ℋ.Example  10 (continued). The convexity space 𝒞 is not decomposable since the convex hull of the set {a,b,c,d} is the whole vertex set V but the vertex e is separated from {a,b,c,d} by the convex cluster {d}.In the next two subsections, we shall prove the properties (D1 and D2) mentioned in the introduction.


### 5.1. Property (D1)

Given any convexity space𝒞 on ℋ that satisfies Axioms 1 and 2, we first provide a closed formula for the set of vertices that are separated from a set X by no convex cluster of ℋ. It will follow that if 𝒞 is decomposable, then the same formula is an expression of the convex hull of X.Lemma 11.
Letℋ be a hypergraph on V, 𝒞 a convexity space on ℋ that satisfies Axioms 1 and 2, 𝒦 the cluster hypergraph of ℋ, and X a nonempty subset of V. The set of vertices that are separated from X by no convex cluster of ℋ is given by the union of the convex hulls of edges of GR(𝒦,X).Proof.
LetX*=⋃A∈GR(𝒦,X)〈A〉. We now prove that u∉X* if and only if u is separated from X by some convex cluster of ℋ.
Proof of (“if”). Let u be a vertex of ℋ that is separated from X by a convex cluster of ℋ. Let Y such a convex cluster. Since Y is a convex set, Y separates u from X in 𝒦 by Lemma 5. Moreover, since Y is a cluster of ℋ, Y is a partial edge of 𝒦. In order to prove that u∉X*, we first show that u is not a vertex of GR(𝒦,X) and, then, u∉〈A〉 for every edge A of GR(𝒦,X).
Since in𝒦 the vertex u is separated from X by the partial edge Y of 𝒦, u is not a vertex of GR(𝒦,X) by part (i) of Lemma 1. Consider now any edge A of GR(𝒦,X). If 〈A〉=A then, since A is a subset of the vertex set of GR(𝒦,X), one has that u∉〈A〉. Assume that 〈A〉≠A and suppose, by contradiction, that u∈〈A〉. By Corollary 2, one has that A⊆Y and, hence, 〈A〉⊆〈Y〉=Y. To sum up, u∈〈A〉 by assumption, and u∉Y since Y separates u from X, which is in contradiction with the inclusion 〈A〉⊆Y.
Proof of (“only if”). Assume that u∉X*. We now prove that there exists a convex cluster that separates u from X in ℋ. Recall that the vertex set of GR(𝒦,X) is a subset of X* and 〈A〉 is a subset of X* for every edge A of GR(𝒦,X). Therefore, since u∉X*, u is not a vertex of GR(𝒦,X) and u∉〈A〉 for every edge A of GR(𝒦,X). Since u is not a vertex of GR(𝒦,X), by part (ii) of Lemma 1 there exists an edge A of GR(𝒦,X) that separates u from X in 𝒦 and, since u∉X* and 〈A〉⊆X*, one has that u∉〈A〉 and, hence, 〈A〉 separates u from X in 𝒦. Since 𝒦 is a cover of ℋ, u is separated from X by the convex cluster 〈A〉 in ℋ.At this point, we are in a position to prove property (D1) of decomposable convexity spaces.Theorem 12.
Letℋ be a hypergraph on V, 𝒞 a decomposable convexity space on ℋ, 𝒦 the cluster hypergraph of ℋ, and X a subset of V. The convex hull of X is given by the union of the convex hulls of the edges of GR(𝒦,X), that is,
(2)〈X〉=⋃A∈GR(𝒦,X)〈A〉.Proof.
By Lemma11 and Axiom 3.Theorem12 also leads to the following characterization of convex sets.Theorem 13.
Letℋ be a connected hypergraph on V, 𝒞 a decomposable convexity space on ℋ, and 𝒦 the cluster hypergraph of ℋ. A nonempty subset X of V is convex if and only if (a)
X equals the vertex set of GR(𝒦,X), and(b)
every edge ofGR(𝒦,X) is a convex set.Proof of (“if”).
By condition (a),X equals the vertex set of GR(𝒦,X) and, by condition (b), 〈A〉=A  for every edge of GR(𝒦,X). By (2), one has
(3)〈X〉=⋃A∈GR(𝒦,X)〈A〉=⋃A∈GR(𝒦,X)A=X,
and, hence, X is a convex set.Proof of (“only if”).
First of all, recall that for any subsetX of V, one has that X is a subset of the vertex set of GR(𝒦,X). Moreover, A⊆〈A〉 for every edge A of GR(𝒦,X). Therefore, one has
(4)X⊆⋃A∈GR(𝒦,X)A=⋃A∈GR(𝒦,X)〈A〉⊆〈X〉.
Assume that X is a convex set. Then X=〈X〉 so that, by (2), one has that  X=⋃A∈GR(𝒦,X)A and A=〈A〉 for every edge A of GR(𝒦,X), which are exactly conditions (a) and (b).


### 5.2. Property (D2)

We begin with a few basic definitions and preliminary results. A vertexν in a convex set X is an extreme point of X if X∖{ν} is a convex set. A convexity space is a convex geometry if it enjoys the Minkowsky-Krein-Milman property: every convex set is the convex hull of the set of its extreme points.In order to prove property (D2), we make use of the following two characterizations of convex geometries.Lemma 14 (e.g., see [17]).
A convexity space𝒞 is a convex geometry if and only if, for every set X in 𝒞, X≠V, there exists ν∉X such that X∪{ν} belongs to 𝒞.The next characterization of convex geometries is based on the notion of a “descending path,” which is defined as follows. LetX and Y be two convex sets with Y⊂X. A descending path [17] from X to Y in the lattice of 𝒞 is an ordering (ν1,…,νn) of the elements of X∖Y such that, for each i, 1≤i≤n, the set X∖{ν1,ν2,…,νi} is convex.Lemma 15 (see [4]).
A convexity space𝒞 is a convex geometry if and only if, for every set X in 𝒞, X≠V, there exists a descending path from V to X in the lattice of 𝒞.Corollary 16.
Let𝒞 be a convex geometry and let X and Y be two convex sets. If Y is a subset of X, Y≠X, then there exists a descending path from X to Y in the lattice of the induced subspace 𝒞(X).Proof.
SinceY is a convex set, by Lemma 15, there exists a descending path p=(ν1,…,νn), n=|V∖Y|. Thus, each set Vi=V∖{ν1,ν2,…,νi} is convex, 1≤i≤n. Of course, each vertex in X∖Y must appear in p. Let i(1)<⋯<i(k), k=|X∖Y|, be the positions in p of the vertices in X∖Y. Since both X and Vi(h) are convex sets, the set X∩Vi(h) is convex, 1≤h≤k; moreover, X∩Vi(h)=X∖{νi(1),…,νi(h)}, 1≤h≤k, so that X∩Vi(k)=Y. Therefore, (νi(1),…,νi(k)) is a descending path from X to Y in the lattice of 𝒞(X).At this point, we are in a position to prove property (D2) of decomposable convexity spaces.Theorem 17.
Letℋ be a connected hypergraph, 𝒞 a decomposable convexity space on ℋ, and 𝒦 the cluster hypergraph of ℋ. The convexity space 𝒞 is a convex geometry if and only if the subspaces of 𝒞 induced by edges of 𝒦 are all convex geometries.Proof.
Proof of (“only if”). Let X be any edge of 𝒦. Since 𝒞 is decomposable, X is a convex set by Axiom 2. Let 𝒞(X) be the subspace of 𝒞 induced by X. Consider any convex set Y in 𝒞(X), Y≠X. By Corollary 16, there exists a descending path from X to Y in the lattice of 𝒞(X), which by Lemma 15 proves that 𝒞(X) is a convex geometry.
Proof of (“if”). Let X be any convex set with X≠V. By Lemma 14, we need to prove that there exists a vertex ν∉Xsuch that X∪{ν} is convex. By Theorem 13, X equals the vertex set of GR(𝒦,X) and every edge of GR(𝒦,X) is a convex set. Distinguish two cases depending on whether or not GR(𝒦,X) is a partial hypergraph of 𝒦 (i.e., every edge of GR(𝒦,X) is an edge of 𝒦).
Case  1. GR(𝒦,X) is a partial hypergraph of 𝒦. Since X≠V, all the edges of 𝒦 that are not edges of GR(𝒦,X) have been deleted during the Graham reduction of 𝒦 with sacred set X. Let Y be the edge of 𝒦 that has been deleted; then, its residual part, say A, was found to be contained in an edge of GR(𝒦,X). Then, A is an MVS of 𝒦 (see the properties of the Graham reduction). Since 𝒞 is decomposable, Y is a convex set by Axiom 2, and A is a convex set by Theorem 8.
Case  2.
GR
(
𝒦
,
X
) is not a partial hypergraph of 𝒦. Then there exists an edge A of GR(𝒦,X) that is strictly contained in an edge of 𝒦. Let Y be an edge of 𝒦 that contains A. Since 𝒞 is decomposable, Y is a convex set by Axiom 2, and A is a convex set by condition (b) of Theorem 13.
In both cases, by hypothesis,𝒞(Y) is a convex geometry. Therefore, since A is a proper subset of Y, by Lemma 14 there exists ν∈Y∖A such that the set A∪{ν} is convex. We will show that X∪{ν} is a convex set, which by Lemma 14 proves that 𝒞 is a convex geometry. Since ν∈Y∖A, by the Church-Rosser property of the Graham reduction procedure, we can assume that ν is the last vertex that is deleted during the Graham reduction of 𝒦 with sacred set X. Therefore, in Case1 the hypergraph GR(𝒦,X∪{ν}) can be viewed as being obtained from GR(𝒦,X) by adding the edge A∪{ν}, and in Case  2 the hypergraph GR(𝒦,X∪{ν}) can be viewed as being obtained from GR(𝒦,X) by deleting the edge A and adding the edge A∪{ν}. Since X is a convex set, by condition (a) of Theorem 13 the vertex set of GR(𝒦,X) equals X, so that the vertex set of GR(𝒦,X∪{ν}) equals X∪{ν}, which proves that X∪{ν} satisfies condition (a) of Theorem 13. Morever, an edge of GR(𝒦,X∪{ν}) is either A∪{ν} or an edge of GR(𝒦,X) and, since A∪{ν} is a convex set and every edge of GR(𝒦,X) is a convex set by condition (b) of Theorem 13, one has that every edge of GR(𝒦,X∪{ν}) is a convex set, which proves that X∪{ν} satisfies condition (b) of Theorem 13. So, by Theorem 13, X∪{ν} is convex.It is worth observing that, by Theorem13, every descending path in a decomposable convex geometry 𝒞 on ℋ is a Graham elimination ordering of vertices of the cluster hypergraph 𝒦 (or, equivalently, is a perfect elimination ordering of the chordal graph on the vertex set of ℋ where two vertices are adjacent if and only if they form a cluster of ℋ).


## 5.1. Property (D1)

Given any convexity space𝒞 on ℋ that satisfies Axioms 1 and 2, we first provide a closed formula for the set of vertices that are separated from a set X by no convex cluster of ℋ. It will follow that if 𝒞 is decomposable, then the same formula is an expression of the convex hull of X.Lemma 11.
Letℋ be a hypergraph on V, 𝒞 a convexity space on ℋ that satisfies Axioms 1 and 2, 𝒦 the cluster hypergraph of ℋ, and X a nonempty subset of V. The set of vertices that are separated from X by no convex cluster of ℋ is given by the union of the convex hulls of edges of GR(𝒦,X).Proof.
LetX*=⋃A∈GR(𝒦,X)〈A〉. We now prove that u∉X* if and only if u is separated from X by some convex cluster of ℋ.
Proof of (“if”). Let u be a vertex of ℋ that is separated from X by a convex cluster of ℋ. Let Y such a convex cluster. Since Y is a convex set, Y separates u from X in 𝒦 by Lemma 5. Moreover, since Y is a cluster of ℋ, Y is a partial edge of 𝒦. In order to prove that u∉X*, we first show that u is not a vertex of GR(𝒦,X) and, then, u∉〈A〉 for every edge A of GR(𝒦,X).
Since in𝒦 the vertex u is separated from X by the partial edge Y of 𝒦, u is not a vertex of GR(𝒦,X) by part (i) of Lemma 1. Consider now any edge A of GR(𝒦,X). If 〈A〉=A then, since A is a subset of the vertex set of GR(𝒦,X), one has that u∉〈A〉. Assume that 〈A〉≠A and suppose, by contradiction, that u∈〈A〉. By Corollary 2, one has that A⊆Y and, hence, 〈A〉⊆〈Y〉=Y. To sum up, u∈〈A〉 by assumption, and u∉Y since Y separates u from X, which is in contradiction with the inclusion 〈A〉⊆Y.
Proof of (“only if”). Assume that u∉X*. We now prove that there exists a convex cluster that separates u from X in ℋ. Recall that the vertex set of GR(𝒦,X) is a subset of X* and 〈A〉 is a subset of X* for every edge A of GR(𝒦,X). Therefore, since u∉X*, u is not a vertex of GR(𝒦,X) and u∉〈A〉 for every edge A of GR(𝒦,X). Since u is not a vertex of GR(𝒦,X), by part (ii) of Lemma 1 there exists an edge A of GR(𝒦,X) that separates u from X in 𝒦 and, since u∉X* and 〈A〉⊆X*, one has that u∉〈A〉 and, hence, 〈A〉 separates u from X in 𝒦. Since 𝒦 is a cover of ℋ, u is separated from X by the convex cluster 〈A〉 in ℋ.At this point, we are in a position to prove property (D1) of decomposable convexity spaces.Theorem 12.
Letℋ be a hypergraph on V, 𝒞 a decomposable convexity space on ℋ, 𝒦 the cluster hypergraph of ℋ, and X a subset of V. The convex hull of X is given by the union of the convex hulls of the edges of GR(𝒦,X), that is,
(2)〈X〉=⋃A∈GR(𝒦,X)〈A〉.Proof.
By Lemma11 and Axiom 3.Theorem12 also leads to the following characterization of convex sets.Theorem 13.
Letℋ be a connected hypergraph on V, 𝒞 a decomposable convexity space on ℋ, and 𝒦 the cluster hypergraph of ℋ. A nonempty subset X of V is convex if and only if (a)
X equals the vertex set of GR(𝒦,X), and(b)
every edge ofGR(𝒦,X) is a convex set.Proof of (“if”).
By condition (a),X equals the vertex set of GR(𝒦,X) and, by condition (b), 〈A〉=A  for every edge of GR(𝒦,X). By (2), one has
(3)〈X〉=⋃A∈GR(𝒦,X)〈A〉=⋃A∈GR(𝒦,X)A=X,
and, hence, X is a convex set.Proof of (“only if”).
First of all, recall that for any subsetX of V, one has that X is a subset of the vertex set of GR(𝒦,X). Moreover, A⊆〈A〉 for every edge A of GR(𝒦,X). Therefore, one has
(4)X⊆⋃A∈GR(𝒦,X)A=⋃A∈GR(𝒦,X)〈A〉⊆〈X〉.
Assume that X is a convex set. Then X=〈X〉 so that, by (2), one has that  X=⋃A∈GR(𝒦,X)A and A=〈A〉 for every edge A of GR(𝒦,X), which are exactly conditions (a) and (b).


## 5.2. Property (D2)

We begin with a few basic definitions and preliminary results. A vertexν in a convex set X is an extreme point of X if X∖{ν} is a convex set. A convexity space is a convex geometry if it enjoys the Minkowsky-Krein-Milman property: every convex set is the convex hull of the set of its extreme points.In order to prove property (D2), we make use of the following two characterizations of convex geometries.Lemma 14 (e.g., see [17]).
A convexity space𝒞 is a convex geometry if and only if, for every set X in 𝒞, X≠V, there exists ν∉X such that X∪{ν} belongs to 𝒞.The next characterization of convex geometries is based on the notion of a “descending path,” which is defined as follows. LetX and Y be two convex sets with Y⊂X. A descending path [17] from X to Y in the lattice of 𝒞 is an ordering (ν1,…,νn) of the elements of X∖Y such that, for each i, 1≤i≤n, the set X∖{ν1,ν2,…,νi} is convex.Lemma 15 (see [4]).
A convexity space𝒞 is a convex geometry if and only if, for every set X in 𝒞, X≠V, there exists a descending path from V to X in the lattice of 𝒞.Corollary 16.
Let𝒞 be a convex geometry and let X and Y be two convex sets. If Y is a subset of X, Y≠X, then there exists a descending path from X to Y in the lattice of the induced subspace 𝒞(X).Proof.
SinceY is a convex set, by Lemma 15, there exists a descending path p=(ν1,…,νn), n=|V∖Y|. Thus, each set Vi=V∖{ν1,ν2,…,νi} is convex, 1≤i≤n. Of course, each vertex in X∖Y must appear in p. Let i(1)<⋯<i(k), k=|X∖Y|, be the positions in p of the vertices in X∖Y. Since both X and Vi(h) are convex sets, the set X∩Vi(h) is convex, 1≤h≤k; moreover, X∩Vi(h)=X∖{νi(1),…,νi(h)}, 1≤h≤k, so that X∩Vi(k)=Y. Therefore, (νi(1),…,νi(k)) is a descending path from X to Y in the lattice of 𝒞(X).At this point, we are in a position to prove property (D2) of decomposable convexity spaces.Theorem 17.
Letℋ be a connected hypergraph, 𝒞 a decomposable convexity space on ℋ, and 𝒦 the cluster hypergraph of ℋ. The convexity space 𝒞 is a convex geometry if and only if the subspaces of 𝒞 induced by edges of 𝒦 are all convex geometries.Proof.
Proof of (“only if”). Let X be any edge of 𝒦. Since 𝒞 is decomposable, X is a convex set by Axiom 2. Let 𝒞(X) be the subspace of 𝒞 induced by X. Consider any convex set Y in 𝒞(X), Y≠X. By Corollary 16, there exists a descending path from X to Y in the lattice of 𝒞(X), which by Lemma 15 proves that 𝒞(X) is a convex geometry.
Proof of (“if”). Let X be any convex set with X≠V. By Lemma 14, we need to prove that there exists a vertex ν∉Xsuch that X∪{ν} is convex. By Theorem 13, X equals the vertex set of GR(𝒦,X) and every edge of GR(𝒦,X) is a convex set. Distinguish two cases depending on whether or not GR(𝒦,X) is a partial hypergraph of 𝒦 (i.e., every edge of GR(𝒦,X) is an edge of 𝒦).
Case  1. GR(𝒦,X) is a partial hypergraph of 𝒦. Since X≠V, all the edges of 𝒦 that are not edges of GR(𝒦,X) have been deleted during the Graham reduction of 𝒦 with sacred set X. Let Y be the edge of 𝒦 that has been deleted; then, its residual part, say A, was found to be contained in an edge of GR(𝒦,X). Then, A is an MVS of 𝒦 (see the properties of the Graham reduction). Since 𝒞 is decomposable, Y is a convex set by Axiom 2, and A is a convex set by Theorem 8.
Case  2.
GR
(
𝒦
,
X
) is not a partial hypergraph of 𝒦. Then there exists an edge A of GR(𝒦,X) that is strictly contained in an edge of 𝒦. Let Y be an edge of 𝒦 that contains A. Since 𝒞 is decomposable, Y is a convex set by Axiom 2, and A is a convex set by condition (b) of Theorem 13.
In both cases, by hypothesis,𝒞(Y) is a convex geometry. Therefore, since A is a proper subset of Y, by Lemma 14 there exists ν∈Y∖A such that the set A∪{ν} is convex. We will show that X∪{ν} is a convex set, which by Lemma 14 proves that 𝒞 is a convex geometry. Since ν∈Y∖A, by the Church-Rosser property of the Graham reduction procedure, we can assume that ν is the last vertex that is deleted during the Graham reduction of 𝒦 with sacred set X. Therefore, in Case1 the hypergraph GR(𝒦,X∪{ν}) can be viewed as being obtained from GR(𝒦,X) by adding the edge A∪{ν}, and in Case  2 the hypergraph GR(𝒦,X∪{ν}) can be viewed as being obtained from GR(𝒦,X) by deleting the edge A and adding the edge A∪{ν}. Since X is a convex set, by condition (a) of Theorem 13 the vertex set of GR(𝒦,X) equals X, so that the vertex set of GR(𝒦,X∪{ν}) equals X∪{ν}, which proves that X∪{ν} satisfies condition (a) of Theorem 13. Morever, an edge of GR(𝒦,X∪{ν}) is either A∪{ν} or an edge of GR(𝒦,X) and, since A∪{ν} is a convex set and every edge of GR(𝒦,X) is a convex set by condition (b) of Theorem 13, one has that every edge of GR(𝒦,X∪{ν}) is a convex set, which proves that X∪{ν} satisfies condition (b) of Theorem 13. So, by Theorem 13, X∪{ν} is convex.It is worth observing that, by Theorem13, every descending path in a decomposable convex geometry 𝒞 on ℋ is a Graham elimination ordering of vertices of the cluster hypergraph 𝒦 (or, equivalently, is a perfect elimination ordering of the chordal graph on the vertex set of ℋ where two vertices are adjacent if and only if they form a cluster of ℋ).


## 6. Examples

In this section we prove thatm-convexity spaces [4, 5, 7] and c-convexity spaces [7] in hypergraphs are decomposable, and that ap-convexity spaces [3, 9] in graphs are decomposable.


### 6.1.m-Convexity in Hypergraphs

Letℋ be a connected hypergraph with vertex set V. A path p in ℋ is chordless if, for every two nonconsecutive vertices u and ν on p, u and ν are not adjacent. A subset X of V is m-convex if either X=∅ or X contains all vertices on every chordless path joining two vertices in X [4, 5]. Equivalently, a subset X of V is m-convex if either X=V or X=∅ or the neighborhood of every connected component of ℋ-X is a clique of ℋ [5, 7]. Note that every clique of ℋ is an m-convex set. By 〈X〉m we denote the m-convex hull of X. Efficient algorithms for computing m-convex hulls in graphs were given in [9–11]. A similar algorithm for computing m-convex hulls in hypergraphs was given in [7]; it makes use of the acyclic hypergraph whose edges are the maximal sets that are not separable by cliques of ℋ [19]. This hypergraph is called the prime hypergraph of ℋ [7]. Let ℋ~ denote the prime hypergraph of ℋ. We can summarize the algorithm in [7] into the following formula:
(5)〈X〉m=⋃A∈GR(ℋ~,X)α~(A),
where
(6)α~(A)={A,ifAisacliqueofℋ,theedgeofℋ~thatcontainsA,otherwise.Fact 4.
IfX is an edge of ℋ~, then GR(ℋ~,X)={X} and, hence, 〈X〉m=X. It follows that every edge of ℋ~ is an m-convex set.Fact 5.
IfX is cluster of ℋ (i.e., X is a partial edge of ℋ~), then GR(ℋ~,X)={X} and, hence, 〈X〉m=α~(X).In order to prove the decomposability ofm-convexity, we need the following lemma.Lemma 18.
Letℋ be a connected hypergraph, and let 𝒞 be the m-convexity space on ℋ. The cluster hypergraph of ℋ equals the prime hypergraph of ℋ.Proof.
It is sufficient to prove that two vertices ofℋ are separated by an m-convex set of ℋ if and only if they are separated by a clique of ℋ.
Proof of (if). The statement follows from the fact that every clique of ℋ is an m-convex set of ℋ.
Proof of (only if). We need to prove that if two vertices u and ν of ℋ are separated by an m-convex set of ℋ, then they are separated by a clique of ℋ. Let X be an m-convex set separating u and ν. Thus, u and ν belong to two distinct connected components of ℋ-X. Let ℋ′ be the connected component of ℋ-X containing u, and let Y be the neighborhood of ℋ′. Then, ℋ′ is also a connected component of ℋ-Y and the vertex ν belongs to another connected component of ℋ-Y. Therefore, u and ν are separated by Y and, since X is an m-convex set of ℋ and Y is the neighborhood of a connected component of ℋ-X, Y is a clique of ℋ, which proves the statement.Theorem 19.
Letℋ be a connected hypergraph. The m-convexity space on ℋ is decomposable.Proof.
Let𝒞 be the m-convexity space on ℋ. By Lemma 18, the cluster hypergraph of ℋ is acyclic so that, by Fact 4, every-edge of the cluster hypergraph of ℋ is an m-convex set. Therefore, 𝒞 satisfies Axioms 1 and 2. Moreover, by Lemmas 11 and 18 and by Fact 5, the right-hand side of (5) equals the set of vertices that are separated from  X  by no m-convex cluster of ℋ. Finally, by the equality in (5), 𝒞 also satisfies Axiom 3, which proves the statement.


### 6.2.c-Convexity in Hypergraphs

Letℋ be a connected hypergraph with vertex set V. A subset X of V is c-convex if either X=V or X=∅ or the neighborhood of every connected component of ℋ-X is a partial edge of ℋ [7]. Note that every partial edge of ℋ is a c-convex set. By 〈X〉c we denote the c-convex hull of X.An efficient algorithm for computingc-convex hulls in hypergraphs was given in [12]; it makes use of the acyclic hypergraph whose edges are the maximal sets that are not separable by partial edges of ℋ [20]. The hypergraph is called the compact hypergraph of ℋ [7, 18, 20]. Let ℋ^ denote the compact hypergraph of ℋ. We can summarize the algorithm in [7] into the following formula:
(7)〈X〉c=⋃A∈GR(ℋ^,X)α^(A),
where
(8)α^(A)={A,ifAisapartialedgeofℋ,theedgeofℋ^thatcontainsA,otherwise.Fact 6.
IfX is an edge of ℋ^, then GR(ℋ^,X)={X} and, hence, 〈X〉c=X. It follows that every edge of ℋ^ is a c-convex set.Fact 7.
IfX is cluster of ℋ (i.e., X is a partial edge of   ℋ^), then GR(ℋ^,X)={X} and, hence, 〈X〉c=α^(X).In order to prove the decomposability ofc-convexity, we need the following lemma whose proof is analogous to the proof of Lemma 18.Lemma 20.
Letℋ be a connected hypergraph and let 𝒞 be the c-convexity space on ℋ. The cluster hypergraph of ℋ equals the compact hypergraph of ℋ.Theorem 21.
Letℋ be a connected hypergraph. The c-convexity space on ℋ is decomposable.Proof.
Let𝒞 be the c-convexity space on ℋ.By Lemma 20, the cluster hypergraph of ℋ is acyclic so that, by Fact 6, every-edge of the cluster hypergraph of ℋ is a c-convex set. Therefore, 𝒞 satisfies Axioms 1 and 2. Moreover, by Lemmas 11 and 20 and by Fact 7, the right-hand side of (7) equals the set of vertices that are separated from X by no c-convex cluster of ℋ. Finally, by the equality in (7), 𝒞 also satisfies Axiom 3, which proves the statement.


### 6.3. ap-Convexity in Graphs

Letℋ be a connected graph with vertex set V. A subset X of  V  is ap-convex if either X=∅ or X contains all vertices on every path joining two vertices in X [3, 9]. By 〈X〉ap we denote the ap-convex hull of X.Letℋ- be the block hypergraph of ℋ; that is, ℋ- is the acyclic hypergraph whose edges are the maximal sets that are not separable by cut vertices of ℋ. From results in [3, 9], it follows that the ap-convex hull of a subset X of V is given by the following formula:
(9)〈X〉ap=⋃A∈GR(ℋ-,X)α-(A),
where α-(A) is the edge of ℋ- that contains A.At this point, it is a mere exercise to prove that the cluster hypergraph ofℋ equals the block hypergraph of ℋ and that the ap-convexity space on ℋ is decomposable.


## 6.1.m-Convexity in Hypergraphs

Letℋ be a connected hypergraph with vertex set V. A path p in ℋ is chordless if, for every two nonconsecutive vertices u and ν on p, u and ν are not adjacent. A subset X of V is m-convex if either X=∅ or X contains all vertices on every chordless path joining two vertices in X [4, 5]. Equivalently, a subset X of V is m-convex if either X=V or X=∅ or the neighborhood of every connected component of ℋ-X is a clique of ℋ [5, 7]. Note that every clique of ℋ is an m-convex set. By 〈X〉m we denote the m-convex hull of X. Efficient algorithms for computing m-convex hulls in graphs were given in [9–11]. A similar algorithm for computing m-convex hulls in hypergraphs was given in [7]; it makes use of the acyclic hypergraph whose edges are the maximal sets that are not separable by cliques of ℋ [19]. This hypergraph is called the prime hypergraph of ℋ [7]. Let ℋ~ denote the prime hypergraph of ℋ. We can summarize the algorithm in [7] into the following formula:
(5)〈X〉m=⋃A∈GR(ℋ~,X)α~(A),
where
(6)α~(A)={A,ifAisacliqueofℋ,theedgeofℋ~thatcontainsA,otherwise.Fact 4.
IfX is an edge of ℋ~, then GR(ℋ~,X)={X} and, hence, 〈X〉m=X. It follows that every edge of ℋ~ is an m-convex set.Fact 5.
IfX is cluster of ℋ (i.e., X is a partial edge of ℋ~), then GR(ℋ~,X)={X} and, hence, 〈X〉m=α~(X).In order to prove the decomposability ofm-convexity, we need the following lemma.Lemma 18.
Letℋ be a connected hypergraph, and let 𝒞 be the m-convexity space on ℋ. The cluster hypergraph of ℋ equals the prime hypergraph of ℋ.Proof.
It is sufficient to prove that two vertices ofℋ are separated by an m-convex set of ℋ if and only if they are separated by a clique of ℋ.
Proof of (if). The statement follows from the fact that every clique of ℋ is an m-convex set of ℋ.
Proof of (only if). We need to prove that if two vertices u and ν of ℋ are separated by an m-convex set of ℋ, then they are separated by a clique of ℋ. Let X be an m-convex set separating u and ν. Thus, u and ν belong to two distinct connected components of ℋ-X. Let ℋ′ be the connected component of ℋ-X containing u, and let Y be the neighborhood of ℋ′. Then, ℋ′ is also a connected component of ℋ-Y and the vertex ν belongs to another connected component of ℋ-Y. Therefore, u and ν are separated by Y and, since X is an m-convex set of ℋ and Y is the neighborhood of a connected component of ℋ-X, Y is a clique of ℋ, which proves the statement.Theorem 19.
Letℋ be a connected hypergraph. The m-convexity space on ℋ is decomposable.Proof.
Let𝒞 be the m-convexity space on ℋ. By Lemma 18, the cluster hypergraph of ℋ is acyclic so that, by Fact 4, every-edge of the cluster hypergraph of ℋ is an m-convex set. Therefore, 𝒞 satisfies Axioms 1 and 2. Moreover, by Lemmas 11 and 18 and by Fact 5, the right-hand side of (5) equals the set of vertices that are separated from  X  by no m-convex cluster of ℋ. Finally, by the equality in (5), 𝒞 also satisfies Axiom 3, which proves the statement.


## 6.2.c-Convexity in Hypergraphs

Letℋ be a connected hypergraph with vertex set V. A subset X of V is c-convex if either X=V or X=∅ or the neighborhood of every connected component of ℋ-X is a partial edge of ℋ [7]. Note that every partial edge of ℋ is a c-convex set. By 〈X〉c we denote the c-convex hull of X.An efficient algorithm for computingc-convex hulls in hypergraphs was given in [12]; it makes use of the acyclic hypergraph whose edges are the maximal sets that are not separable by partial edges of ℋ [20]. The hypergraph is called the compact hypergraph of ℋ [7, 18, 20]. Let ℋ^ denote the compact hypergraph of ℋ. We can summarize the algorithm in [7] into the following formula:
(7)〈X〉c=⋃A∈GR(ℋ^,X)α^(A),
where
(8)α^(A)={A,ifAisapartialedgeofℋ,theedgeofℋ^thatcontainsA,otherwise.Fact 6.
IfX is an edge of ℋ^, then GR(ℋ^,X)={X} and, hence, 〈X〉c=X. It follows that every edge of ℋ^ is a c-convex set.Fact 7.
IfX is cluster of ℋ (i.e., X is a partial edge of   ℋ^), then GR(ℋ^,X)={X} and, hence, 〈X〉c=α^(X).In order to prove the decomposability ofc-convexity, we need the following lemma whose proof is analogous to the proof of Lemma 18.Lemma 20.
Letℋ be a connected hypergraph and let 𝒞 be the c-convexity space on ℋ. The cluster hypergraph of ℋ equals the compact hypergraph of ℋ.Theorem 21.
Letℋ be a connected hypergraph. The c-convexity space on ℋ is decomposable.Proof.
Let𝒞 be the c-convexity space on ℋ.By Lemma 20, the cluster hypergraph of ℋ is acyclic so that, by Fact 6, every-edge of the cluster hypergraph of ℋ is a c-convex set. Therefore, 𝒞 satisfies Axioms 1 and 2. Moreover, by Lemmas 11 and 20 and by Fact 7, the right-hand side of (7) equals the set of vertices that are separated from X by no c-convex cluster of ℋ. Finally, by the equality in (7), 𝒞 also satisfies Axiom 3, which proves the statement.


## 6.3. ap-Convexity in Graphs

Letℋ be a connected graph with vertex set V. A subset X of  V  is ap-convex if either X=∅ or X contains all vertices on every path joining two vertices in X [3, 9]. By 〈X〉ap we denote the ap-convex hull of X.Letℋ- be the block hypergraph of ℋ; that is, ℋ- is the acyclic hypergraph whose edges are the maximal sets that are not separable by cut vertices of ℋ. From results in [3, 9], it follows that the ap-convex hull of a subset X of V is given by the following formula:
(9)〈X〉ap=⋃A∈GR(ℋ-,X)α-(A),
where α-(A) is the edge of ℋ- that contains A.At this point, it is a mere exercise to prove that the cluster hypergraph ofℋ equals the block hypergraph of ℋ and that the ap-convexity space on ℋ is decomposable.


## 7. Closing Note

Given a convexity space𝒞 on a connected hypergraph ℋ, we introduced the notions of a cluster of ℋ and of the cluster hypergraph of ℋ. Using them, we define decomposability of 𝒞 by means of three axioms and proved that decomposability implies the existence of a closed formula (see (2) above) which expresses the convex hull of a vertex set X in terms of the convex hulls of edges of GR(𝒦,X), where 𝒦 is the cluster hypergraph of ℋ. Moreover, we proved that a decomposable convexity space 𝒞 is a convex geometry if and only if the subspaces of 𝒞 induced by the edges of 𝒦 are all convex geometries. Finally, we showed that both m-convexity and c-convexity in hypergraphs are decomposable, and that ap-convexity in graphs is decomposable. An open problem is the search for other decomposable known hypergraph convexities. We conjecture that not only ap-convexity is decomposable in hypergraphs too, but also every convexity that is coarser than m-convexity (such as “simple-path convexity” [4]) is decomposable. On the other hand, it is easy to see that geodetic convexity (g-convexity) is not decomposable in the general case as is proven by the following example. However, since m-convexity and g-convexity are equivalent in distance-hereditary graphs [4], one has that g-convexity is decomposable in distance-hereditary graphs.Example 22.
Consider the (hyper)graphℋ shown in Figure 3 and the g-convexity space on ℋ. Recall from the introduction that a vertex set X is g-convex if X contains all vertices on every shortest path joining two vertices in X.
It is easy to see that the sets{b,e,h} and {d,e,f} are the only minimal vertex g-convex separators of ℋ. Moreover, the cluster hypergraph of ℋ is 𝒦={{a,b,d,e}, {b,c,e,f}, {d,e,g,h}, {e,f,h,i}}. Since 𝒦 is not an acyclic hypergraph, the g-convexity space on ℋ is not decomposable.Figure 3



---

*Source: 453808-2013-01-13.xml*