Loading field map
Matroid theory is a branch of combinatorics that abstracts and generalizes the notion of linear independence from vector spaces. A matroid is a finite set equipped with a collection of subsets called independent sets, satisfying a small set of axioms that capture the essential behavior of linear independence. The theory provides a common framework for studying problems in graph theory, linear algebra, and optimization, often revealing that results in these disparate areas are instances of a single underlying structure.
The fundamental object of study is the matroid, defined by a ground set \(E\) and a family \(\mathcal{I}\) of subsets of \(E\) (the independent sets) such that:
These three axioms are a direct abstraction of the properties of linear independence in vector spaces. For any finite set of vectors, the linearly independent subsets satisfy them. They also hold for the edge sets of forests in a graph: the independent sets of the graphic matroid of a graph are precisely those edge sets that contain no cycle.
Matroid theory seeks to understand the structure and classification of all matroids, and to determine which theorems from linear algebra and graph theory hold for matroids in general. Key questions include:
Matroid theory was introduced by Hassler Whitney in a 1935 paper titled "On the abstract properties of linear dependence." Whitney, a pioneer in graph theory, observed that the linear independence of columns of a matrix and the acyclic subgraphs of a graph obey the same abstract axioms. He named the resulting structure a matroid, partly to emphasize its relation to matrices and partly to indicate its "mother" role for other combinatorial structures.
Independently, around the same time, the Japanese mathematician Takeo Nakasawa was developing a similar theory, though his work remained largely unnoticed for decades. Whitney's framework, however, caught on, and the field grew steadily through the mid-twentieth century.
The 1950s and 1960s saw the development of matroid duality and minors by Whitney and later by W. T. Tutte, who also introduced the Tutte polynomial, a two-variable polynomial invariant of a matroid that generalizes the chromatic polynomial of a graph and the Jones polynomial of a knot. Tutte's work laid the foundation for a rich interplay with graph theory and knot theory.
A major theoretical breakthrough came with the Rota conjecture (posed in 1971), which claimed that for any finite field, there are only finitely many matroids that cannot be represented over that field and that are excluded minors for representability. This conjecture was proved in 2014 by Jim Geelen, Bert Gerards, and Geoff Whittle, marking a high point of the structure theory of matroids.
Matroid theory is not divided into rival schools, but rather into several overlapping approaches that emphasize different aspects of the same object. These approaches often reflect different intellectual genealogies: one grows out of linear algebra, one out of graph theory, one out of discrete geometry, and one out of combinatorial optimization. Each offers a distinct way of seeing matroids, and each has produced its own techniques and results.
The earliest and most intuitive approach treats matroids as abstract linear dependence. A representable matroid is one that is isomorphic to the matroid of a set of vectors over a field. This perspective uses the language of matrices, vector spaces, and field theory. Its central problem is classification: which matroids are representable over which fields?
This approach naturally leads to the study of regular matroids (representable over every field), binary matroids (representable over the two-element field), and ternary matroids (representable over the three-element field). The structure theory of representable matroids, developed by Tutte, Jack Edmonds, and later by Geelen, Gerards, and Whittle, uses tools from graph theory, linear algebra, and finite geometry. The representability approach is limited by the fact that many matroids are not representable over any field; for these, the linear algebra picture gives no insight, and other approaches must be used.
A second tradition views matroids primarily as generalizations of graphs. The graphic matroid of a graph has the edges as its ground set and the forests as its independent sets. Many graph-theoretic concepts — connectivity, duality, minors, planarity — have natural matroid analogues, and graph-theoretic theorems often inspire matroid generalizations.
This approach has been especially fruitful in the study of graphic matroids and their minors. Tutte's theorem characterizing regular matroids (as those that exclude two specific minors) grew directly out of work on graphic matroids. The emphasis on forbidden minors, connectivity, and decomposition is characteristic of this tradition. Its limitation is that many important matroids are not graphic, and the graph analogy can obscure genuinely new phenomena that arise in non-graphic settings.
A third approach views matroids as abstract configurations of points in projective space. A linear matroid over a field can be seen as a set of points in a projective space over that field, with the independent sets being those that do not lie in a proper projective subspace. The lattice of flats of a matroid — the family of subspaces generated by subsets of the ground set, ordered by inclusion — is a geometric lattice, and matroids can be defined equivalently in terms of their lattice of flats.
This geometric vision is central to the study of representable matroids over finite fields, where matroids correspond to sets of points in finite projective geometries. The critical problem, mentioned earlier, is a natural question in this language. This approach also connects matroid theory to valuated matroids and to tropical geometry, where matroids appear as the combinatorial data of algebraic varieties. Its limitation is that a purely geometric intuition often applies only to representable matroids; the general theory must proceed without concrete geometric pictures.
A fourth approach, developed in the 1970s and 1980s, sees matroids as the combinatorial structure underlying a class of optimization problems that can be solved greedily. The greedy algorithm — a method that builds a solution by repeatedly taking the best available element — works correctly on matroid optimization problems: for any weight function on the ground set, the greedy algorithm finds a maximum-weight independent set.
This observation, made by Jack Edmonds and others, led to a rich theory of matroid intersection (finding a common independent set of two matroids), matroid union (combining matroids), and their applications in combinatorial optimization. From this perspective, matroids are the natural setting for a theory of exchange properties that guarantee the success of greedy algorithms and the applicability of polyhedral methods. This approach emphasizes algorithmic efficiency and the existence of polynomial-time algorithms, and it has produced strong connections to integer programming and to the theory of polymatroids. Its limitation is that it focuses on optimization and may overlook structural aspects that are not algorithmic.
A more recent, though deeply rooted, tradition is the structure theory of matroids, which aims to classify matroids by their minors and to describe how large matroids can be decomposed into smaller, well-understood pieces. This approach was strongly influenced by the graph minors project of Robertson and Seymour, and it has been developed for matroids by Geelen, Gerards, and Whittle, among others.
The central result of this approach is the resolution of Rota's conjecture, which states that for each finite field, the matroids representable over that field have a finite set of excluded minors. More generally, the structure theory seeks to prove that large excluded-minor classes of matroids have a tree-like decomposition into fragments that are themselves well understood. This approach uses tools from geometry, finite fields, and graph theory, and it has produced deep theorems about the global structure of matroids. Its limitation is that the proofs are highly technical and often provide little intuitive insight into why the results hold.
These approaches are not mutually exclusive. A single matroid can be studied from all four perspectives, and many theorems bridge the traditions. For example, the Tutte polynomial can be defined purely combinatorially, but it can also be interpreted as a generating function for the number of independent sets, the number of bases, and other invariants; its evaluations relate to the chromatic polynomial of a graph and to the weight enumerator of a linear code. This polynomial plays a central role in the optimization approach (via the reliability polynomial), the geometric approach (via Tutte's homotopy theory), and the representation approach (via its relation to the weight enumerator).
Similarly, the dual of a matroid — defined by taking the complement of bases — is a concept that appears naturally in all approaches. In linear algebra, the dual matroid corresponds to the orthogonal complement of a subspace. In graph theory, the dual of a planar graphic matroid is the graphic matroid of the dual graph. In optimization, duality underlies the theory of matroid intersection and the polyhedral description of independent sets.
Matroid theory today is a mature but active field. The resolution of Rota's conjecture has settled a central structural problem, but many open questions remain. The critical problem is still unsolved in general, and its connections to coding theory (specifically to the parameters of linear codes) continue to be explored. The interplay between matroids and tropical geometry has opened new directions, as has the use of matroids in algebraic statistics and machine learning — for instance, in understanding the geometry of maximum likelihood estimation.
In applied mathematics, matroids appear in the design of network coding schemes, in the analysis of crowd-sourcing systems, and in the study of phylogenetic trees. In theoretical computer science, matroids are used to design submodular optimization algorithms and differential privacy mechanisms. The greedy algorithm and its generalizations remain a cornerstone of algorithmic design.
The field continues to be organized around a few core problems: representation, duality, minors, connectivity, and polynomial invariants. The approaches described above are still the major ways of working, and the relationships among them remain a source of both depth and difficulty. A newcomer to matroid theory quickly learns that the same object appears in many guises, and that the power of the field lies precisely in the fact that a single abstract structure can be seen simultaneously as a set of vectors, a set of edges, a set of points in a geometry, and a family of feasible solutions to an optimization problem.