Decomposable convexities in graphs and hypergraphs
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).
- A fast algorithm for query optimization in universal-relation databases
- Algorithmic Aspects of Monophonic Convexity
- Canonical and monophonic convexities in hypergraphs
- Complexity results related to monophonic convexity
- Connections in acyclic hypergraphs
- Convex sets in a graph
- Convex sets in graphs. II: Minimal path convexity
- Convexities related to path properties on graphs
- Convexity in Graphs and Hypergraphs
- Decomposition of a hypergraph by partial-edge separators
- scientific article; zbMATH DE number 1539530 (Why is no real title available?)
- scientific article; zbMATH DE number 863476 (Why is no real title available?)
- Hull numbers of path convexities on graphs
- Modular Interval Spaces
- On the Desirability of Acyclic Database Schemes
- On triangle path convexity in graphs
- Optimal decomposition by clique separators
- Pruning processes and a new characterization of convex geometries
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Treewidth. Computations and approximations
- Canonical and monophonic convexities in hypergraphs
- A monadic second-order definition of the structure of convex hypergraphs.
- A matrix approach to hypergraph stable set and coloring problems with its application to storing problem
- Decomposability of abstract and path-induced convexities in hypergraphs
- Equivalence between hypergraph convexities
- scientific article; zbMATH DE number 3892078 (Why is no real title available?)
This page was built for publication: Decomposable convexities in graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1952718)
