Matroid embedding

In combinatorics, a matroid embedding is a type of set system used for characterizing problems that can be optimized by a greedy algorithm. It was introduced by Helman et al. in 1993.

An element x is said to be adjoined to another set X if we take the union of {x} with X.

The extension ext(X) of a feasible set X is the set of all elements that can be adjoined to X to form another feasible set.

The hereditary closure F^* of a collection of feasible sets F is the collection of all subsets of every member of F.

A matroid embedding is an accessible set system (F, E) that satisfies the Extensibility Property

for every feasible subset X of a basis B, some element in B but not in X can be adjoined to X to form another feasible set.

and the Closure-Congruence Property

for every superset A of a feasible set X disjoint from ext(X), either every element in ext(X) can be adjoined to A to form a set in F^*, or none can be so.

References

Helman, Paul; Moret, Bernard M. E.; Shapiro, Henry D. (1993). An exact characterization of greedy structures. SIAM J. Discrete Math. 6 (2), 274–283.