Matroid

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

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in B \setminus A} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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:

• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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.

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \le \rho(A) \le |A| ;\,}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A \subseteq B \Rightarrow \rho(A) \le \rho(B) ;\,}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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

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