Matroid

| Main Article
| Discussion
| Related Articles  [?]
| Bibliography  [?]
| External Links  [?]
| Citable Version  [?]

|
|
|
|
|
|
|
|

This editable Main Article is under development and subject to a disclaimer.

[edit intro]

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, B⊆A∈ℰ⇒B∈ℰ;
* The exchange property: if A,B∈ℰ with |B|=|A|+1 then there exists x∈B∖A such that A∪{x}∈ℰ.

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[edit]

The following sets form independence structures:

* ℰ={∅};
* ℰ=𝒫E;
* 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[edit]

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≤ρ(A)≤|A|;
A⊆B⇒ρ(A)≤ρ(B);
ρ(A)+ρ(B)≥ρ(A∩B)+ρ(A∪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.

## References[edit]

* 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.