# Matroid

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

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

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

• ${\displaystyle {\mathcal {E}}}$ is a downset, that is, ${\displaystyle B\subseteq A\in {\mathcal {E}}\Rightarrow B\in {\mathcal {E}}}$;
• The exchange property: if ${\displaystyle A,B\in {\mathcal {E}}}$ with ${\displaystyle |B|=|A|+1}$ then there exists ${\displaystyle x\in B\setminus A}$ such that ${\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

The following sets form independence structures:

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

${\displaystyle 0\leq \rho (A)\leq |A|;\,}$
${\displaystyle A\subseteq B\Rightarrow \rho (A)\leq \rho (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.