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 supersetA 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, embedding, combinatorics, matroid, embedding, system, where, collection, feasible, sets, that, satisfies, following, properties, accessibility, property, every, empty, feasible, contains, element, such, that, feasible, extensibility, property, every, . 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 embedding was introduced by Helman Moret amp Shapiro 1993 to characterize problems that can be optimized by a greedy algorithm References EditHelman Paul Moret Bernard M E Shapiro Henry D 1993 An exact characterization of greedy structures SIAM Journal on Discrete Mathematics 6 2 274 283 CiteSeerX 10 1 1 37 1825 doi 10 1137 0406021 MR 1215233 Retrieved from https en wikipedia org w index php title Matroid embedding amp oldid 1119299793, wikipedia, wiki, book, books, library,
