In combinatorics, a matroid embedding is a set system (F,E), where F is a collection of feasible sets, that satisfies the following properties.

1. Accessibility property: Every non-empty feasible setX contains an elementx such that X\{x} is feasible.

2. Extensibility property: For every feasible subsetX of a basis (i.e., maximal feasible set) B, some element in B but not in X belongs to the extension ext(X) of X, where ext(X) is the set of all elementse not in X such that X∪{e} is feasible.

3. Closure–congruence property: For every supersetA of a feasible setX disjoint from ext(X), A∪{e} is contained in some feasible set for either alle or noe in ext(X).

4. The collection of all subsets of feasible sets forms a matroid.

Matroid embeddings were introduced by to characterize problems that can be optimized by a greedy algorithm.

References