a matroid
/ MAY-troid /
Why does greedy work beautifully for some problems and fail for others? Matroid theory gives a single abstract answer. A matroid is a mathematical structure that captures the essence of 'independence' — like a set of vectors with no redundancy, or a set of graph edges with no cycle — in a way general enough to explain a whole class of greedy successes at once.
Formally a matroid is a ground set E together with a family of subsets called the independent sets, satisfying three axioms. First, the empty set is independent. Second, hereditary (downward-closed): every subset of an independent set is independent. Third, and the crucial one, the exchange property: if A and B are both independent and A has fewer elements than B, then some element of B can be added to A keeping it independent. The two canonical examples make this concrete. The graphic matroid: ground set = edges of a graph, independent sets = the acyclic edge sets (forests); adding an edge that makes no cycle keeps you independent, and the exchange property holds because a smaller forest can always borrow an edge from a larger one without creating a cycle. The linear matroid: ground set = a collection of vectors, independent sets = the linearly independent subsets. In both, a maximal independent set is called a basis (a spanning tree, or a basis of vectors), and a remarkable fact is that all bases have the same size — the rank — which follows from the exchange property.
The payoff is the matroid-greedy theorem: if you want a maximum-weight independent set in a weighted matroid, the greedy rule of considering elements from heaviest to lightest and adding each one that keeps the set independent is provably optimal — for every matroid, no separate exchange argument needed. This is exactly why Kruskal's MST works (the graphic matroid). And it sharpens the failure stories too: 0/1 knapsack's feasible sets do NOT form a matroid (the exchange property fails), which is the structural reason greedy breaks there. Matroids do not cover every greedy problem — some need their own arguments — but they explain a large, important family in one stroke.
Graphic matroid on a triangle (edges AB, BC, CA): the independent sets are all edge subsets with no cycle — the empty set, every single edge, and every pair of edges. The full set {AB, BC, CA} is dependent (a cycle). Every basis (maximal independent set) is a pair of edges — a spanning tree — and all have size 2, the rank.
Forests of a graph form a matroid; the three axioms (nonempty, hereditary, exchange) are what greedy needs to be optimal.
Not every problem greedy solves is a matroid, and not every greedy success needs matroid theory — but when the feasible sets form a matroid, greedy optimality is automatic by the matroid-greedy theorem.