Decomposable convexities in graphs and hypergraphs
type: Item
instance of: scholarly article
title: Decomposable convexities in graphs and hypergraphs
zbMATH Open document ID: 1264.05089
DOI: 10.1155/2013/453808
published in: ISRN Combinatorics
publication date: 2013-06-03T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 6169805
zbMATH Keywords: decomposable convexity space
zbMATH Keywords: decomposability
zbMATH Keywords: decomposable convexities
zbMATH Keywords: connected hypergraph
zbMATH Keywords: smallest convex set
zbMATH Keywords: acyclic hypergraph
zbMATH Keywords: maximal clusters
zbMATH Keywords: convex hull
zbMATH Keywords: convex cluster
zbMATH Keywords: convex geometries
Wikidata QID: Q58997007
author: Francesco M. Malvestuto
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2013/453808
OpenAlex ID: W1992880576
cites work: Modular Interval Spaces
cites work: Q4519717
cites work: Convex sets in a graph
cites work: Convexity in Graphs and Hypergraphs
cites work: Convex sets in graphs. II: Minimal path convexity
cites work: On triangle path convexity in graphs
cites work: Canonical and monophonic convexities in hypergraphs
cites work: Convexities related to path properties on graphs
cites work: Q5506514
cites work: Algorithmic Aspects of Monophonic Convexity
cites work: Complexity results related to monophonic convexity
cites work: Q4871755
cites work: Treewidth. Computations and approximations
cites work: On the Desirability of Acyclic Database Schemes
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Connections in acyclic hypergraphs
cites work: Pruning processes and a new characterization of convex geometries
cites work: A fast algorithm for query optimization in universal-relation databases
cites work: Optimal decomposition by clique separators
cites work: Decomposition of a hypergraph by partial-edge separators
description: scientific article; zbMATH DE number 6169805