Decomposable Convexities in Graphs and Hypergraphs. (13th January 2013)

• Record Type: Journal Article
• Authors: Malvestuto, Francesco M.
• Other Names: Manstavicius E. Academic Editor.; Menasco W. Academic Editor.
• Is Part Of: ISRN combinatorics. Volume 2013(2013)
• Publication Date: 2013-01-13
• Subjects: Combinatorial analysis -- Periodicals; Combinatorial analysis; Electronic journals; Periodicals; 511.6
• DOI: 10.1155/2013/453808
• Languages: English
• ISSNs: 2090-8911

Abstract

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).