Matroid embedding

In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties. # Accessibility property: Every non-empty feasible set X contains an element x such that X \ {x} is feasible. # Extensibility property: For every feasible subset X 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 elements e not in X such that X ∪ {e} is feasible. # Closure–congruence property: For every superset A of a feasible set X disjoint from ext(X), A ∪ {e} is contained in some feasible set for either all e or no e in ext(X). # 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.

In combinatorics, a matroid embedding is a set system (F, E), where F is a collection of feasible sets, that satisfies the following properties. Accessibility property: Every non-empty feasible set X contains an element x such that X \ {x} is feasible. Extensibility property: For every feasible subset X 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 elements e not in X such that X ∪ {e} is feasible. Closure–congruence property: For every superset A of a feasible set X disjoint from ext(X), A ∪ {e} is contained in some feasible set for either all e or no e in ext(X). 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1323932785 under CC BY-SA 4.0; modifications have been made.