Matroid

In mathematics, an independence space is a structure that generalises the concept of linear and algebraic independence.

An independence structure on a set E is a family ${\mathcal {E}}$ of subsets of E, called independent sets, with the properties

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

Examples

The following sets form independence structures:

• ${\mathcal {E}}=\{\emptyset \}$;
• ${\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.

References

• Victor Bryant; Hazel Perfect (1980). Independence Theory in Combinatorics. Chapman and Hall. ISBN 0-412-22430-5.