Matroid embedding (original) (raw)
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 set X contains an element x such that X \ {x} is feasible. 2. * 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. 3. * 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). 4. * The collection of all subsets of feasible sets forms a matroid.
| Property | Value |
|---|---|
| dbo:abstract | 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 set X contains an element x such that X \ {x} is feasible. 2. * 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. 3. * 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). 4. * The collection of all subsets of feasible sets forms a matroid. Matroid embedding was introduced by to characterize problems that can be optimized by a greedy algorithm. (en) |
| dbo:wikiPageID | 735426 (xsd:integer) |
| dbo:wikiPageLength | 1628 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119299793 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Matroid_theory dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Combinatorics dbr:Matroid dbr:Superset dbr:Greedy_algorithm dbr:Set_system |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Short_description |
| dct:subject | dbc:Matroid_theory |
| gold:hypernym | dbr:System |
| rdfs:comment | 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 set X contains an element x such that X \ {x} is feasible. 2. * 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. 3. * 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). 4. * The collection of all subsets of feasible sets forms a matroid. (en) |
| rdfs:label | Matroid embedding (en) |
| owl:sameAs | freebase:Matroid embedding wikidata:Matroid embedding https://global.dbpedia.org/id/4rUaK |
| prov:wasDerivedFrom | wikipedia-en:Matroid_embedding?oldid=1119299793&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Matroid_embedding |
| is dbo:wikiPageWikiLink of | dbr:Index_of_combinatorics_articles dbr:Matroid |
| is foaf:primaryTopic of | wikipedia-en:Matroid_embedding |