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

• ${\displaystyle {ℰ}}$ is a downset, that is, ${\displaystyle B\subseteq A\in {ℰ}\Rightarrow B\in {ℰ}}$;
• The exchange property: if ${\displaystyle A,B\in {ℰ}}$ with ${\displaystyle |B|=|A|+1}$ then there exists ${\displaystyle x\in B\setminus A}$ such that ${\displaystyle A\cup \{x\}\in {ℰ}}$.

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:

• ${\displaystyle {ℰ}=\{\mathrm{\varnothing }\}}$;
• ${\displaystyle {ℰ}={𝒫}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

${\displaystyle 0\le \rho (A)\le |A|;}$

${\displaystyle A\subseteq B\Rightarrow \rho (A)\le \rho (B);}$

${\displaystyle \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.

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.