Decomposable convexities in graphs and hypergraphs (Q1952718): Difference between revisions

Summary: Given a connected hypergraph \(\mathcal{H}\) with vertex set \(V\), a convexity space on \(\mathcal{H}\) is a subset \(\mathcal{C}\) of the powerset of \(V\) that contains \(\emptyset\), \(V\), and the singletons; furthermore, \(\mathcal{C}\) is closed under intersection and every set in \(\mathcal{C}\) is connected in \(\mathcal{H}\). The members of \(\mathcal{C}\) are called convex sets. The convex hull of a subset \(X\) of \(V\) is the smallest convex set containing \(X\). By a cluster of \(\mathcal{H}\) 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 \(\mathcal{H}\) is decomposable if it satisfies the following three axioms: {\parindent=7mm \begin{itemize}\item[(i)]the maximal clusters of \(\mathcal{H}\) form an acyclic hypergraph, \item[(ii)]every maximal cluster of \(\mathcal{H}\) is a convex set, and \item[(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. \end{itemize}} We prove that a decomposable convexity space \(\mathcal{C}\) on \(\mathcal{H}\) is fully specified by the maximal clusters of \(\mathcal{H}\) in that {\parindent=7mm \begin{itemize}\item[(1)]there is a closed formula which expresses the convex hull of a set in terms of certain convex clusters of \(\mathcal{H}\) and \item[(2)]\(\mathcal{C}\) is a convex geometry if and only if the subspaces of \(\mathcal{C}\) induced by maximal clusters of \(\mathcal{H}\) are all convex geometries. \end{itemize}} 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).