- Atlas
- Mathematics
- Matroid Theory
Matroid Theory
Matroid Theory Matroid theory is the abstract study of dependence.
9 frameworks, from 1935 to today · Combinatorics · Mathematics
- Matroid 1935-Present
- Matroid representation 1940-Present
- Matroid Structure Theory and Minors 1950-Present
- Tutte polynomial 1950-Present
- Transversal and Matching Matroids 1955-Present
- Matroid Optimization and Polyhedral Combinatorics 1968-Present
- Matroid decomposition theory 1975-Present
- Oriented matroid 1975-Present
- Algebraic and Geometric Combinatorics of Matroids 1990-Present
Overview
Matroid Theory
Matroid theory is the abstract study of dependence1. It began as a way to isolate what makes a set of vectors in a vector space linearly independent, or what makes a set of edges in a graph acyclic, and it grew into a general theory of "independence structures" that applies to both and to many other things besides1. A matroid is a finite set together with a rule saying which of its subsets are "independent"—a rule that must satisfy a few simple axioms modelled on linear independence1. From those axioms flows a rich structure: bases, circuits, rank, closure, duality, and a polynomial that encodes an enormous amount of information about the object. The subject matters because it is the natural home of the idea of independence, and because matroids sit at a crossroads where combinatorics meets linear algebra, geometry, topology, and optimization. The history of the field is largely the history of learning how far the analogy with vector spaces can be pushed, and where it breaks.
Origins: Whitney and the Axioms of Independence (1930s)
The field begins with Hassler Whitney, who in 1935 published "On the Abstract Properties of Linear Dependence." Whitney was interested in the combinatorial essence of the linear dependence of vectors1. He noticed that the property of being a set of independent vectors could be characterized without any mention of coordinates or fields, by axioms on the family of independent sets1. He called the resulting structure a "matroid."1 The same year, independently, the Japanese mathematician Takeo Nakasawa developed a similar axiomatic theory, though his work remained little known outside Japan for decades and did not shape the field's development.
Whitney's key observation was that graphs give a second, entirely different source of matroids1. Take a graph and let the independent sets be the edge sets that contain no cycle—a forest1. These "graphic matroids" satisfy the same axioms as vector matroids, even though they arise from a combinatorial rather than an algebraic setting1. This coincidence was the founding insight: matroids are the common abstraction of two very different theories1. Whitney also introduced the notion of duality for matroids, generalizing the planar dual of a graph, and the notion of a matroid being "representable" over a field—realizable as a set of vectors.
The Mid-Century Consolidation: Rank, Duality, and Representability
Through the 1940s and 1950s the basic vocabulary was assembled1. The rank function—assigning to each subset the size of the largest independent set it contains—became a central tool, and it was shown to characterize matroids completely2. Saunders Mac Lane, in work on field theory, encountered matroids through the study of algebraic dependence, and the connection to projective geometry became clear: a representable matroid is essentially a finite configuration of points in a projective space, with independence meaning linear independence of the corresponding vectors. This gave matroid theory a geometric face1.
The question of representability—which matroids come from vectors over some field?—became a defining problem1. It was known early that not every matroid is representable. The smallest example, the seven-point "Fano matroid," comes from the seven nonzero vectors of the three-dimensional vector space over the two-element field, but its dual is not representable over any field of characteristic other than two. This showed that representability is a delicate and field-dependent property, and it opened a long program of characterizing representable matroids by excluded configurations.
Tutte and the Structure of Matroids (1950s–1960s)1
W. T. Tutte dominated the next phase1. In a series of papers through the 1950s and 1960s he developed the theory of matroid minors—the operations of deletion and contraction, which for graphs correspond to deleting an edge or contracting it—and proved that a matroid is representable over the two-element field exactly when it has no minor isomorphic to a certain small "forbidden" matroid. This was the first of the great excluded-minor theorems, and it established the pattern: characterize a class of matroids by the small configurations it cannot contain.
Tutte also introduced the polynomial now bearing his name3. The Tutte polynomial of a graph, defined by a deletion–contraction recursion, specializes to the chromatic polynomial, the flow polynomial, and the reliability polynomial; for matroids it generalizes the rank-generating function. It became the central invariant of the subject, a single object from which many combinatorial quantities can be read off1. Tutte's work gave matroid theory its structural backbone: minors, duality, representability, and invariants all fit together4.
Transversal Matroids and the Matching Connection (1950s–1960s)
A parallel strand came from matching theory1. Given a family of subsets of a ground set—think of a bipartite graph and the sets of neighbours of each vertex—the subsets that can be matched to distinct elements form the independent sets of a matroid, called a transversal matroid1. This was recognized in the 1950s and 1960s through work connected with Philip Hall's marriage theorem and the theory of matchings. Transversal matroids showed that matroids arise not only from algebra and graph theory but from the combinatorics of systems of distinct representatives1. They also connected matroid theory to combinatorial optimization, since matching problems are solvable by efficient algorithms1.
Optimization and the Greedy Algorithm (1950s–1970s)
The algorithmic side of matroid theory crystallized around a deceptively simple fact: the greedy algorithm—repeatedly add the cheapest element that keeps the set independent—produces a maximum-weight independent set exactly when the independence structure is a matroid1. This was proved by David Gale in 1968 and independently by Jack Edmonds, and it gave matroids a central place in combinatorial optimization. Edmonds, in the late 1960s and early 1970s, developed the theory of matroid intersection and matroid polyhedra, showing that many optimization problems over matroids can be solved efficiently and characterized by linear inequalities. The "matroid polytope"—the convex hull of the incidence vectors of bases—became a bridge to polyhedral combinatorics5. This work established that matroids are not merely a classification device but a computational framework: they tell you which problems are easy1.
Decomposition and the Minors Program (1970s–2000s)
The excluded-minor program launched by Tutte grew into a major industry1. In the 1970s and 1980s, work by Paul Seymour and others on matroid decomposition—splitting a matroid into simpler pieces along separations—produced structure theorems analogous to the graph-theoretic decomposition theorems1. Seymour's "decomposition theorem for regular matroids" (1980) showed that every regular matroid (representable over every field) can be built from graphic, cographic, and a small exceptional matroid by simple operations. This was a matroid analogue of the graph structure theory being developed at the same time.
The minors program reached a landmark with the proof of the "excluded minor" conjectures for representable matroids over finite fields, and with the growing sense that matroid minors behave like graph minors. The Robertson–Seymour graph minors theorem had a matroid counterpart in the work of Neil Robertson and Paul Seymour themselves, and later in the 2000s and 2010s by Jim Geelen, Bert Gerards, and others, who proved deep structure theorems for matroids representable over finite fields. These results are technical but carry the same message: large matroids in a well-behaved class have a tree-like decomposition into small pieces.
Oriented Matroids and Topological Representation (1970s–1980s)
A separate development concerned orientation6. An oriented matroid is a matroid equipped with a signing of its circuits that records the "direction" of dependence, generalizing the way a real vector configuration has oriented circuits6. The theory was developed in the 1970s and 1980s by Robert Bland, Michel Las Vergnas, Bernd Sturmfels, Günter Ziegler, and others, building on earlier work on oriented geometries. Oriented matroids turned out to be equivalent to arrangements of hyperplanes and to certain topological objects, and they connected matroid theory to the theory of convex polytopes, to the "topological representation" of combinatorial types, and to the study of the Grassmannian. The "oriented matroid" became a meeting point for combinatorics, geometry, and topology.
Algebraic and Geometric Combinatorics of Matroids (1990s–present)
In the last three decades matroid theory has been absorbed into algebraic and geometric combinatorics. The characteristic polynomial of a matroid, the Tutte polynomial, and the matroid polytope have become objects of study in their own right, connected to hyperplane arrangements, to the cohomology of the complement of an arrangement, and to the theory of "matroid invariants" that are universal among valuations. The "Kazhdan–Lusztig" and "Hodge-theoretic" approaches to matroid invariants, developed in the 2010s, showed that the Tutte polynomial is not the end of the story: there are finer invariants that see more of the matroid's structure. The "matroid stratification" of the Grassmannian and the "matroid basis exchange" graph have become central in algebraic geometry and in the study of cluster algebras. The field now has a vigorous algebraic and geometric life alongside its combinatorial and algorithmic one.
The Present: Open Questions and Active Approaches
Today matroid theory is a mature but still expanding field1. The structure theory of representable matroids over finite fields is an active research area, with the Geelen–Gerards–Whittle program producing deep results and leaving open questions about the precise decomposition. The representability problem—deciding whether a given matroid is representable over some field—remains hard in general, and the search for excluded-minor characterizations continues. Algorithmically, matroid intersection and the matroid parity problem are well understood, but many optimization questions over matroids remain open. The algebraic and geometric side is flourishing, with new invariants and new connections to topology and representation theory. What unites the field is still the original insight: that independence is a structure worth studying for its own sake, and that the matroids arising from vectors, graphs, and matchings are all faces of the same underlying idea.
References
- Matroid (introduction, Matroids from graph theory, Matroids from linear algebra, Definition, Independent sets, History, Tutte polynomial, Algorithms, Minors), Wikipedia
- Matroid rank, Wikipedia
- Tutte polynomial (History), Wikipedia
- Matroid minor, Wikipedia
- Matroid polytope, Wikipedia
- Oriented matroid, Wikipedia
The frameworks of Matroid Theory
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1935-Present
- 1940-Present
- 1950-Present
Matroid Structure Theory and Minors
How do matroids decompose into minors?
- 1950-Present
- 1955-Present
- 1968-Present
Matroid Optimization and Polyhedral Combinatorics
Which problems does greedy solve?
- 1975-Present
- 1975-Present
- 1990-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Matroid Optimization and Polyhedral Combinatorics grew out of Matroid
The greedy algorithm theorem of Gale and Edmonds characterizes matroids by the success of greedy optimization, making Whitney's independence axioms the foundation of a computational framework. Edmonds then built matroid intersection and polyhedra on this basis.
Carried by Jack Edmonds; David Gale.
Matroid decomposition theory grew out of Matroid Structure Theory and Minors
Seymour's decomposition theorem for regular matroids grew out of the minors program, splitting matroids along separations into graphic, cographic, and exceptional pieces. Decomposition theory is a direct continuation of Tutte's structural approach via minors.
Carried by Paul Seymour.
Matroid Structure Theory and Minors influenced by Matroid representation
Tutte's excluded-minor characterization of binary matroids was framed as a representability result: a matroid is representable over GF(2) exactly when it avoids a certain minor. The representability question thus drove the minors program.
Carried by W. T. Tutte.
Oriented matroid grew out of Matroid representation
Oriented matroids refine real representability by adding a signing of circuits that records orientation of vector configurations. The theory grew out of the study of real-representable matroids and their geometric realizations.
Carried by Robert Bland; Michel Las Vergnas.
Algebraic and Geometric Combinatorics of Matroids influenced by Tutte polynomial
The Tutte polynomial and characteristic polynomial became central objects in the algebraic and geometric combinatorics of matroids, studied through connections to polytopes and hyperplane arrangements. This later work took the Tutte polynomial as a primary invariant to interpret algebraically and geometrically.
Matroid Optimization and Polyhedral Combinatorics influenced by Transversal and Matching Matroids
Matching theory and transversal matroids supplied Edmonds with key examples and techniques when he developed matroid intersection and polyhedral methods. The algorithmic solvability of matching problems motivated the optimization framework.
Carried by Jack Edmonds.
Algebraic and Geometric Combinatorics of Matroids influenced by Matroid Optimization and Polyhedral Combinatorics
The matroid polytope developed in Edmonds's polyhedral work became a central object in the algebraic and geometric combinatorics of matroids, connected to the Grassmannian and to valuations. This later framework built on the polyhedral foundations.
Carried by Jack Edmonds.
Algebraic and Geometric Combinatorics of Matroids influenced by Oriented matroid
Oriented matroid theory, with its links to hyperplane arrangements and the Grassmannian, fed directly into the algebraic and geometric combinatorics of matroids. The topological and geometric methods of oriented matroids were taken up in this later work.
Carried by Bernd Sturmfels; Günter Ziegler.
Beyond the field
Where Matroid Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 21 links.
Matroid led to Oriented matroid in Discrete Geometry
Oriented matroid theory is a subfield of matroid theory, obtained by orienting the circuits and cocircuits. It developed as a direct extension of the matroid framework.
Matroid led to Greedy algorithms and matroid theory in Graph Algorithms
Greedy algorithms and matroid theory is a branch of matroid theory, deriving the greedy-optimality criterion from the matroid axioms.
Carried by Jack Edmonds; Richard Rado.
Matroid Structure Theory and Minors influenced Structural graph theory and graph minors in Graph Theory
Robertson and Seymour's graph minors programme was explicitly modelled on matroid minor theory, and their structure theorem for graphs excluding a minor parallels the matroid decomposition results of the 1970s–1980s. The matroid work supplied the template of excluded-minor structure and well-quasi-ordering.
Carried by Neil Robertson; Paul Seymour.
Matroid decomposition theory grew out of Matroid in Algebraic Combinatorics
Matroid decomposition theory is a branch of matroid theory itself, growing out of the structural theory founded by Whitney and developed by Tutte, Seymour and others; decomposition theorems such as Seymour's for regular matroids are refinements within the same subject.
Carried by W. T. Tutte; Paul Seymour.
Matroid decomposition theory grew out of Matroid in Combinatorics
The decomposition programme in matroids is a direct specialisation of general matroid theory, taking its axioms and representability questions and asking how matroids split into connected or structured pieces.
Oriented matroid grew out of Matroid in Algebraic Combinatorics
Oriented matroids are a direct refinement of matroid theory: the covector and chirotope axiomatisations, developed by Folkman, Lawrence and Bland, generalise the matroid axioms with orientations.
Carried by Jon Folkman; Jim Lawrence.
Oriented matroid grew out of Matroid in Combinatorics
The oriented matroid framework arose as the oriented version of the classical matroid notion, keeping its independence and rank structure while adding sign data.
Algebraic and Geometric Combinatorics of Matroids grew out of Matroid in Algebraic Combinatorics
Algebraic and geometric combinatorics of matroids is a branch of matroid theory itself, taking matroid structure into the algebra of their invariant theory and the geometry of their polytopes.
Algebraic and Geometric Combinatorics of Matroids grew out of Matroid in Combinatorics
The algebraic-geometric combinatorics of matroids is a direct outgrowth of general combinatorial matroid theory, applying matroid axioms to characteristic polynomials, Tutte polynomials and related invariants.
Matroid influenced by Matrix Analysis in Linear Algebra
Hassler Whitney's 1935 paper 'On the Abstract Properties of Linear Dependence' defined matroids by abstracting the dependence relations of columns of a matrix, taking the notion of linear independence from matrix analysis as the model to be axiomatised.
Carried by Hassler Whitney.
Matroid influenced by Vector space in Linear Algebra
The matroid axioms generalise the notion of linear independence in a vector space; Whitney took the vector-space concept of basis and dependence and kept only its combinatorial properties.
Carried by Hassler Whitney.
Matroid representation influenced Oriented matroid in Discrete Geometry
Oriented matroid theory took over the representability question from matroid representation theory, asking when an oriented matroid comes from a real vector configuration. The concept of representability passed directly into the oriented setting.

Matroid Theory is a planet in Nousfarer
Its city has a tower for each of these 9 frameworks. Land, walk in, and climb one concept at a time.
Land on Matroid TheoryRelated fields
Fields its ideas are linked to
- Algebraic Combinatorics 4 links
- Combinatorics 4 links
- Graph Algorithms 3 links
- Discrete Geometry 3 links
- Linear Algebra 2 links
- Graph Theory 2 links
- Algorithms 1 link
- Mathematical Optimization 1 link
- Combinatorial Optimization 1 link