Editing Matroid embedding

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

Matroid embedding was introduced by {{harvtxt|Helman|Moret|Shapiro|1993}} to characterize problems that can be optimized by a [[greedy algorithm]].

== References ==
*{{citation
 | last1 = Helman | first1 = Paul
 | last2 = Moret | first2 = Bernard M. E. | author2-link = Bernard Moret
 | last3 = Shapiro | first3 = Henry D.
 | doi = 10.1137/0406021
 | issue = 2
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1215233
 | pages = 274–283
 | title = An exact characterization of greedy structures
 | volume = 6
 | year = 1993| citeseerx = 10.1.1.37.1825}}

[[Category:Matroid theory|Embedding]]