Matroid

A matroid is a structure that generalizes the notion of linear independence from vector spaces to arbitrary finite sets. It is defined by a ground set and a collection of independent subsets satisfying three axioms: the empty set is independent; subsets of independent sets are independent; and if one independent set is larger than another, it contains an element that can be added to the smaller while preserving independence. These axioms are deceptively simple, but they capture the combinatorial essence of independence across linear algebra, graph theory, and combinatorial optimization.

The deep significance of matroids for algorithm design is that they characterize exactly the problems for which greedy algorithms are optimal. Rado's theorem and Edmonds's matroid intersection theorem establish that a greedy algorithm yields an optimal solution if and only if the problem can be formulated as optimization over a matroid. This is not a coincidence; it is a structural equivalence. Matroids are the mathematical boundary of greediness — the frontier beyond which local optimization must fail. Understanding this frontier is essential for knowing when to trust a greedy heuristic and when to reach for dynamic programming or integer programming instead.