The prime stems of rooted circuits of closure spaces and minimum implicational bases

Masataka Nakamura¹ ; Kenji Kashiwabara¹

¹University of Tokyo

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

A rooted circuit is firstly introduced for convex geometries (antimatroids). We generalize it for closure systems or equivalently for closure operators. A rooted circuit is a specific type of a pair $(X,e)$ of a subset $X$, called a stem, and an element $e\not\in X$, called a root. We introduce a notion called a 'prime stem', which plays the key role in this article. Every prime stem is shown to be a pseudo-closed set of an implicational system. If the sizes of stems are all the same, the stems are all pseudo-closed sets, and they give rise to a canonical minimum implicational basis. For an affine convex geometry, the prime stems determine a canonical minimum basis, and furthermore gives rise to an optimal basis. A 'critical rooted circuit' is a special case of a rooted circuit defined for an antimatroid. As a precedence structure, 'critical rooted circuits' are necessary and sufficient to fix an antimatroid whereas critical rooted circuits are not necessarily sufficient to restore the original antimatroid as an implicational system. It is shown through an example.

Détail

DOI : 10.37236/3068

Classification : 06A15, 52B40
Mots-clés : closure system, closure operator, Armstrong's axioms, pseudo-closed set, convex geometry, rooted circuit, precedence structure, antimatroid