Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs
math.CO, cs.DM
Submitted: 2026-03-15
Updated: 2026-10-30
Comments: Long version, 28 pages with appendices, 14 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: Optimizing an implicational base of a closure system consists in turning this implicational base into an equivalent one with premises and conclusions as small as possible.
Terminology
Abstract
Optimizing an implicational base of a closure system consists in turning this implicational base into an equivalent one with premises and conclusions as small as possible. This task is known to be hard in general but tractable for a number of classes of closure systems. In particular, several classes of convex geometries are known to have tractable optimization, while the problem was recently claimed to remain hard in general convex geometries. Continuing this line of research, we give a characterization of the optimum bases of a convex geometry in terms of what we call quasi-closed hypergraphs. We then use this characterization to show that when each quasi-closed hypergraph has disjoint edges, any implicational base of the convex geometry can be optimized in polynomial time with existing minimization and reduction algorithms. Finally, we prove that this property applies to double-shelling convex geometries, D-geometries, convex geometries with the n-Carousel property and q-acceptant convex geometries, thus unifying and extending the existing results regarding the tractability of optimization.
Sources
- Complexity Results for Implication Bases of Convex Geometries
- Independence of Essential Sets in Finite Implication Bases
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality