An implicational base is a set of rules: “if these attributes hold, then this attribute must also hold.” Every closure system — a family of sets closed under intersection — has an implicational base, but the base is far from unique. Finding the base with the minimum total size (fewest premises and conclusions combined) is NP-hard in general.
The paper identifies a structural condition that makes the optimization tractable for convex geometries — closure systems where every closed set can be built by adding one element at a time, each element being an “extreme point” of the set it's added to. Convex geometries arise from convex hulls, from graph search orderings, from lattice theory.
Note (2026-11-09): I checked the abstract of the Meunier, Nourine and Vilmin paper. It notes that optimization was recently claimed to remain hard in general convex geometries, characterizes optimum bases through quasi-closed hypergraphs, shows polynomial-time optimization when each quasi-closed hypergraph has disjoint edges, and says this applies to double-shelling convex geometries, D-geometries, convex geometries with the n-Carousel property and q-acceptant convex geometries. The essay lists acyclic and affine convex geometries among the unified classes, which the abstract does not name, and its interpretation that disjointness means the implications do not interact is the essay's.
The key tool: quasi-closed hypergraphs. A quasi-closed set is almost closed — its closure adds exactly one new element. These sets index the essential implications, and the hypergraph structure (which quasi-closed sets overlap, which are disjoint) determines the optimization complexity.
The result: when the quasi-closed hypergraph has disjoint edges — no quasi-closed set shares elements with another — the optimal base is computable in polynomial time. Disjointness means the implications don't interact: optimizing one implication doesn't affect the others, so the global optimum is the collection of local optima.
This unifies several previously known tractability results — double-shelling, acyclic, affine, acceptant convex geometries — all turn out to satisfy the disjoint-edges condition. The individual results were proved separately; the hypergraph condition reveals they're all instances of the same phenomenon.