Matroid
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 of subsets of E, called independent sets, with the properties
- is a downset, that is, ;
- The exchange property: if with then there exists such that .
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.
Examples
The following sets form independence structures:
- ;
- ;
- Linearly independent sets in a vector space;
- Algebraically independent sets in a field extension;
- Affinely independent sets in an affine space;
- Forests in a graph.
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
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.
References
- Victor Bryant; Hazel Perfect (1980). Independence Theory in Combinatorics. Chapman and Hall. ISBN 0-412-22430-5.
- James Oxley (1992). Matroid theory. Oxford University Press. ISBN 0-19-853563-5.