From Knowino
Jump to: navigation, search

In mathematics, a matroid or independence space is a structure that generalises the concept of linear and algebraic independence.

An independence structure on a ground set E is a family \mathcal{E} of subsets of E, called independent sets, with the properties

A basis in an independence structure is a maximal independent set. Any two bases have the same number of elements. A circuit is a minimal dependent set. Independence spaces can be defined in terms of their systems of bases or of their circuits.

[edit] Examples

The following sets form independence structures:

[edit] Rank

We define the rank ρ(A) of a subset A of E to be the maximum cardinality of an independent subset of A. The rank satisfies the following

0 \le \rho(A) \le |A| ;\,
A \subseteq B \Rightarrow \rho(A) \le \rho(B) ;\,
\rho(A) + \rho(B) \ge \rho(A\cap B) + \rho(A \cup B) .\,

The last of these is the submodular inequality.

A flat is a subset A of E such that the rank of A is strictly less than the rank of any proper superset of A.

[edit] References

Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools