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  E {\displaystyle {\mathcal {E}}} of subsets of E, called independent sets, with the properties

* E {\displaystyle {\mathcal {E}}} is a downset, that is,  B ⊆ A ∈ E ⇒ B ∈ E {\displaystyle B\subseteq A\in {\mathcal {E}}\Rightarrow B\in {\mathcal {E}}} ;
* The exchange property: if  A , B ∈ E {\displaystyle A,B\in {\mathcal {E}}} with  | B | = | A | + 1 {\displaystyle |B|=|A|+1} then there exists  x ∈ B ∖ A {\displaystyle x\in B\setminus A} such that  A ∪ { x } ∈ E {\displaystyle A\cup \\{x\\}\in {\mathcal {E}}} .

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 = { ∅ } {\displaystyle {\mathcal {E}}=\\{\emptyset \\}} ;
* E = P E {\displaystyle {\mathcal {E}}={\mathcal {P}}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 | ; {\displaystyle 0\leq \rho (A)\leq |A|;\,}
A ⊆ B ⇒ ρ ( A ) ≤ ρ ( B ) ; {\displaystyle A\subseteq B\Rightarrow \rho (A)\leq \rho (B);\,}
ρ ( A ) + ρ ( B ) ≥ ρ ( A ∩ B ) + ρ ( A ∪ B ) . {\displaystyle \rho (A)+\rho (B)\geq \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.

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