Decomposable Convexities in Graphs and Hypergraphs

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). 1. Introduction A (finite) convexity space [1] over a finite nonempty set is a subset of the powerset of that contains and and is closed under intersection. The members of are called convex sets. The convex hull of a subset of , denoted by , is the smallest convex set containing . It is well known that (i) , (ii) if then , and (iii) . A convexity space over is a point-convexity space [2] if, for every element of , the singleton is a convex set. 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 is a convex set, the subspace of induced by is the convexity space on the (connected) subhypergraph induced by . Most convexities in graphs and hypergraphs have been stated in terms of？？“feasible” paths [8]; accordingly, a vertex set is convex if contains all vertices on every feasible path joining two vertices in . 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 ( -convexity, for short) and all-paths convexity (ap-convexity, for short) enjoy similar properties.