Matroids — Mathematics Knowledge System

Overview

Matroid theory provides an abstract framework that simultaneously generalizes linear independence in vector spaces and the notion of forests (acyclic subgraphs) in graphs. A matroid is a set system satisfying axioms that capture the combinatorial essence of independence. The theory unifies results from linear algebra, graph theory, and transversal theory, and finds applications in greedy algorithms, network flows, and optimization.

Intuition

Think of a matroid as an abstract notion of 'independence.' In a vector space, independent sets are linearly independent sets of vectors. In a graph, independent sets are forests (acyclic subgraphs). A matroid captures what these two notions have in common: the empty set is independent, any subset of an independent set is independent, and if two independent sets have different sizes you can extend the smaller one. The greedy algorithm works optimally precisely when the underlying structure is a matroid.

Formal Definition

Definition

A matroid M = (E, I) consists of a finite ground set E and a collection I of subsets of E (called independent sets) satisfying three axioms.

\emptyset \in \mathcal{I}

I1: empty set is independent

A \in \mathcal{I},; B \subseteq A \implies B \in \mathcal{I}

I2: hereditary property

A, B \in \mathcal{I},; |A| < |B| \implies \exists\, e \in B \setminus A \text{ s.t. } A \cup \{e\} \in \mathcal{I}

I3: augmentation (exchange) property

r(A) = \max\{|I| : I \subseteq A,; I \in \mathcal{I}\}

Rank function

Notation

Notation	Meaning
$M = (E, \mathcal{I})$	Matroid with ground set E and independent sets I
$r(A)$	Rank of subset A: size of largest independent subset of A
$\text{cl}(A)$	Closure (span) of A: largest set with same rank as A
$\mathcal{C}(M)$	Circuits of M: minimal dependent sets

Theorems

Theorem 1: Greedy Algorithm Theorem

A greedy algorithm finds a maximum-weight basis of a weighted matroid M = (E, \mathcal{I}) in O(|E| \log |E|) time

Theorem 2: Matroid Union Theorem

The union of k matroids M_1, \ldots, M_k on the same ground set E has rank function r(A) = \min_{T \subseteq A}\left(|A \setminus T| + \sum_{i=1}^k r_i(T)\right)

Theorem 3: Matroid Intersection Theorem (Edmonds)

\max\{|I| : I \in \mathcal{I}_1 \cap \mathcal{I}_2\} = \min_{A \subseteq E}(r_1(A) + r_2(E \setminus A))

Worked Examples

1
K_3 has 3 edges e1, e2, e3 forming a triangle. Forests (acyclic subgraphs) are the independent sets.
$E = \{e_1, e_2, e_3\},\quad \mathcal{I} = \{\emptyset, \{e_1\}, \{e_2\}, \{e_3\}, \{e_1,e_2\}, \{e_1,e_3\}, \{e_2,e_3\}\}$
2
The empty set and singletons are forests (I1, I2 satisfied). The full triangle is the unique circuit.
$\{e_1,e_2,e_3\} \notin \mathcal{I} \text{ (forms a cycle)}$
3
I3: take A={e1}, B={e1,e2}. Since |A|<|B|, we can add e2 to A to get {e1,e2} which is independent.
$A \cup \{e_2\} = \{e_1,e_2\} \in \mathcal{I}$

✓ Answer

The cycle matroid of K_3 is a matroid with 7 independent sets and rank 2.

Practice Problems

Mediumproof writing

Prove that the greedy algorithm correctly finds a maximum-weight basis for a matroid.

Hardfree response

Define the dual matroid M* of a matroid M = (E, I) and state what the bases of M* are.

Common Mistakes

Common Mistake

Thinking matroids require a specific ambient space

Matroids are abstract set systems defined by axioms. They generalize both linear independence (in vector spaces) and acyclicity (in graphs), but require neither.

Common Mistake

Assuming the matroid axioms force all independent sets to have the same size

Not all independent sets have the same size — only maximal ones (bases) do. The augmentation axiom implies all maximal independent sets (bases) are equicardinal.

Quiz

Which property does NOT follow from the matroid axioms?

All maximal independent sets have the same sizeThe greedy algorithm is optimal for any weight functionIndependent sets are closed under unionSubsets of independent sets are independent

The circuits of a matroid are:

All spanning trees of a graphMinimal dependent setsMaximal independent setsClosed sets under the closure operator

Historical Background

Whitney introduced matroids in 1935 to axiomatize the common properties of linear independence and graph-theoretic forests. Independently, Nakasawa developed a similar theory in Japan. The field was developed further by Tutte, who characterized graphic matroids and proved deep theorems about connectivity. Oxley's 1992 monograph is the standard modern reference.

1935
Whitney introduces matroids, axiomatizing linear and graphic independence
Hassler Whitney
1958
Tutte characterizes graphic matroids and proves the excluded minor theorem
William T. Tutte
1969
Edmonds develops matroid intersection theory for combinatorial optimization
Jack Edmonds
1992
Oxley's Matroid Theory becomes the standard reference
James Oxley

Summary

A matroid M = (E, I) axiomatizes independence via hereditary and augmentation properties.
Examples include linear matroids (from vector spaces) and graphic matroids (from forests in graphs).
All bases (maximal independent sets) have the same cardinality, called the rank of M.
The greedy algorithm finds optimal-weight bases in matroids.
Matroid intersection and union theorems are fundamental tools in combinatorial optimization.

References

BookOxley, J.G. — Matroid Theory, 2nd ed. (2011), Oxford University Press
WebsiteWikipedia — Matroid
WebsiteMathWorld — Matroid