Antimatroid - Convex Geometries

Convex Geometries

See also: Convex set, Convex geometry, and Closure operator

If F is the set system defining an antimatroid, with U equal to the union of the sets in F, then the family of sets

complementary to the sets in F is sometimes called a convex geometry, and the sets in G are called convex sets. For instance, in a shelling antimatroid, the convex sets are intersections of U with convex subsets of the Euclidean space into which U is embedded.

Complementarily to the properties of set systems that define antimatroids, the set system defining a convex geometry should be closed under intersections, and for any set S in G that is not equal to U there must be an element x not in S that can be added to S to form another set in G.

A convex geometry can also be defined in terms of a closure operator τ that maps any subset of U to its minimal closed superset. To be a closure operator, τ should have the following properties:

• τ(∅) = ∅: the closure of the empty set is empty.
• Any set S is a subset of τ(S).
• If S is a subset of T, then τ(S) must be a subset of τ(T).
• For any set S, τ(S) = τ(τ(S)).

The family of closed sets resulting from a closure operation of this type is necessarily closed under intersections. The closure operators that define convex geometries also satisfy an additional anti-exchange axiom:

• If neither y nor z belong to τ(S), but z belongs to τ(S ∪ {y}), then y does not belong to τ(S ∪ {z}).

A closure operation satisfying this axiom is called an anti-exchange closure. If S is a closed set in an anti-exchange closure, then the anti-exchange axiom determines a partial order on the elements not belonging to S, where x ≤ y in the partial order when x belongs to τ(S ∪ {y}). If x is a minimal element of this partial order, then S ∪ {x} is closed. That is, the family of closed sets of an anti-exchange closure has the property that for any set other than the universal set there is an element x that can be added to it to produce another closed set. This property is complementary to the accessibility property of antimatroids, and the fact that intersections of closed sets are closed is complementary to the property that unions of feasible sets in an antimatroid are feasible. Therefore, the complements of the closed sets of any anti-exchange closure form an antimatroid.