Dependence Abstracted: A Narrative Review of Matroid Theory from Whitney's Axioms to Systems Analysis

Abstract

Matroid theory---the abstraction of independence from vectors to graphs to geometries---moved from Whitney's 1935 axioms through Tutte's connectivity and Edmonds's greedy algorithm to Welsh's and Lawler's texts, Seymour's decomposition, the oriented matroids, Oxley's encyclopedia, Truemper's decomposition, White's survey volumes, and Murota's systems analysis. This article presents a narrative review of that arc's canonical line: Whitney's 1935 abstract properties, Tutte's 1959 matroids and graphs, Edmonds's 1971 matroids and the greedy algorithm, Welsh's 1976 Matroid Theory, Lawler's 1976 Combinatorial Optimization, Seymour's 1980 regular decomposition, Brylawski and Kelly's 1980 combinatorial geometries, White's 1986 Theory of Matroids, Oxley's 1992 Matroid Theory, Truemper's 1992 Matroid Decomposition, Bjorner and colleagues's 1993 Oriented Matroids, and Murota's 2000 Matrices and Matroids for Systems Analysis. The review is organized around three themes: Whitney's abstraction, in which the independence's axioms and the duality's graph-theoretic abstraction founded the theory's object; the optimization and the greedy algorithm, in which the exchange's property characterized the greedy's optimality and brought the matroids into the combinatorial optimization's center; and the structure's synthesis, in which the regular's decomposition, the orientations's, the encyclopedias's, and the applications's systems carried the theory to its modern form. It is concluded that matroid theory is the independence's pure abstraction---and that its arc is the object's survival through the abstraction's, the optimization's, and the structure's framings.