Translating Between the Representations of an Acyclic Convex Geometry of Bounded Degree
Abstract
We consider the problem of translating between irreducible closed sets and implicational bases in closure systems. To date, the complexity status of this problem is widely open, and it is further known to generalize the notorious hypergraph dualization problem, even in the case of acyclic convex geometries, i.e., closure systems admitting an acyclic implicational base. This paper studies this case with a focus on the degree, which corresponds to the maximal number of implications in which an element occurs. We show that the problem is tractable for bounded values of this parameter, even when relaxed to the notions of premise- and conclusion-degree. Our algorithms rely on structural properties of acyclic convex geometries and involve various techniques from algorithmic enumeration such as solution graph traversal, saturation techniques, and a sequential approach leveraging from acyclicity. They are shown to perform in incremental-polynomial time. Finally, we complete these results by showing that our running times cannot be improved to polynomial delay using the standard framework of flashlight search.
Related
- A Bounded Closed Convex Set in c0(ℂ) without Modulus Support Functionals
- Triangles minimize the Monge-Ampère eigenvalue among planar bounded convex domains of a given area
- Surjective Hausdorff Isometries of Hyperspaces of Bounded Closed Convex Sets
- Strict Concavity of the Torsion Function for the Restricted Half-Laplacian in Bounded Convex Domains
- Bounded-orbit lattice representations of finite groups
BibTeX
@article{defrain2026translating,
title = {{Translating Between the Representations of an Acyclic Convex Geometry of Bounded Degree}},
author = {Oscar Defrain and Arthur Ohana and Simon Vilmin},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = oct,
doi = {10.37236/14966},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p22},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Translating Between the Representations of an Acyclic Convex Geometry of Bounded Degree
AU - Oscar Defrain
AU - Arthur Ohana
AU - Simon Vilmin
PY - 2026
DA - 2026/10/23
JO - The Electronic Journal of Combinatorics
DO - 10.37236/14966
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p22
AB - We consider the problem of translating between irreducible closed sets and implicational bases in closure systems. To date, the complexity status of this problem is widely open, and it is further known to generalize the notorious hypergraph dualization problem, even in the case of acyclic convex geometries, i.e., closure systems admitting an acyclic implicational base. This paper studies this case with a focus on the degree, which corresponds to the maximal number of implications in which an element occurs. We show that the problem is tractable for bounded values of this parameter, even when relaxed to the notions of premise- and conclusion-degree. Our algorithms rely on structural properties of acyclic convex geometries and involve various techniques from algorithmic enumeration such as solution graph traversal, saturation techniques, and a sequential approach leveraging from acyclicity. They are shown to perform in incremental-polynomial time. Finally, we complete these results by showing that our running times cannot be improved to polynomial delay using the standard framework of flashlight search.
SN - 1077-8926
ER -