In combinatorics, a branch of mathematics, a matroid (pronounced /ˈmeɪtrɔɪd/) or independence structure is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces.
There are many equivalent ways to define a matroid, and many concepts within matroid theory have a variety of equivalent formulations. Depending on the sophistication of the concept, it may be nontrivial to show that the different formulations are equivalent, a phenomenon sometimes called cryptomorphism. Significant definitions of matroid include those in terms of independent sets, bases, circuits, closed sets or flats, closure operators, and rank functions.
Matroid theory borrows extensively from the terminology of linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields.
Contents 
There are dozens of equivalent ways to define a (finite) matroid. Here are some of the most important. There is no one preferred or customary definition; in that respect, matroids differ from many other mathematical structures, such as groups and topologies.
One of the most valuable definitions is that given in terms of independence. In this definition a finite matroid M is a pair (E, I), where E is a finite set and I is a collection of subsets of E (called the independent sets) with the following properties:
The first two properties are simple, and define a combinatorial structure known as an independence system, but the motivation behind the third property is not obvious. The examples in the example section below will make its motivation clearer.
A subset of E that is not independent is called dependent. A maximal independent set—that is, an independent set which becomes dependent on adding any element of E—is called a basis for the matroid. It is a basic result of matroid theory, directly analogous to a similar theorem of linear algebra, that any two bases of a matroid M have the same number of elements. This number is called the rank of M.
A circuit in a matroid M is a minimal dependent subset of E—that is, a dependent set whose proper subsets are all independent. In spite of the similarity to the definition of basis this notion has no analogue in classical linear algebra. The terminology comes from graph theory; see below.
The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely. Furthermore, the collection of dependent sets, or of bases, or of circuits each has simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid M to be a pair (E, B), where E is a finite set as before and B is a collection of subsets of E, called bases, with the following property:
If M is a matroid on E, and A is a subset of E, then a matroid on A can be defined by considering a subset of A independent if and only if it is independent in M. This allows us to talk about submatroids and about the rank of any subset of E.
The rank function r assigns a natural number to every subset of E and has the following properties:
These three properties can be used as one of the alternative definitions of a finite matroid: the independent sets are then defined as those subsets A of E with r(A) = A.
The difference A − r(A) is called the nullity of the subset A. It is the minimum number of elements that must be removed from A to obtain an independent set. The nullity of E in M is called the nullity of M.
Let M be a matroid on a finite set E, defined as above. The closure cl(A) of a subset A of E is the subset of E containing A and every element x in E\A, such that there is a circuit C containing x and contained in the union of A and {x}. This defines the closure operator, from P(E) to P(E), where P denotes the power set.
The closure operator cl from P(E) to P(E) has the following property:
In fact this may be taken as another definition of matroid – any closure operator on E with this property determines a matroid on E.
A set whose closure equals itself is said to be closed, or a flat of the matroid. The closed sets of a matroid are characterized by a covering partition property:
The class L(M) of all flats, partially ordered by set inclusion, forms a matroid lattice. Conversely, the set A of atoms of any matroid lattice L form a matroid under the following closure operator: for a set S of atoms whose join in L is x,
Equivalently, the flats of the matroid are the sets
Thus, the lattice of flats of this matroid is naturally isomorphic to L.
A matroid is called simple if it has no circuits consisting of 1 or 2 elements. That is, it has no loops and no parallel elements.
Let E be a finite set and k a natural number. One may define a matroid on E by taking every kelement subset of E to be a basis. This is known as the uniform matroid of rank k. All uniform matroids of rank at least 2 are simple.
The uniform matroid of rank 2 on n points is called the npoint line.
A matroid is called discrete if every element is a loop or a coloop. Equivalently, every proper, nonempty subset of the ground set E is a separator (loop, coloop, and separator are defined in Additional Terminology below).
Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. Matroids from vector spaces are still the main examples. There are two ways to present them.
A matroid that is equivalent to a vector matroid, although it may be presented differently, is called representable. If M is equivalent to a vector matroid over a field F, then we say M is representable over F ; in particular, M is realrepresentable if it is representable over the real numbers. For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field. A basic problem in matroid theory is to determine whether a given matroid M is representable over a given field F. Whitney found one solution to this problem when F is a field with two elements (see "Binary matroids", below), but the general situation is famously complicated. The main results so far are characterizations of binary matroids due to Tutte (1950s), of ternary matroids (representable over the 3element field) due to Reid and Bixby, and separately to Seymour (1970s), and of quaternary matroids (representable over the 4element field) due to Geelen, Gerards, and Kapoor (2000). This is very much an open area.
A second original source for the theory of matroids is graph theory.
Every finite graph (or multigraph) G gives rise to a matroid as follows: take as E the set of all edges in G and consider a set of edges independent if and only if it does not contain a simple cycle. Such an edge set is called a forest in graph theory. This is called the cycle matroid or graphic matroid of G ; it is usually written M(G). The graphic matroid of G can also be defined as the column matroid of any oriented incidence matrix of G.
Any matroid that is equivalent to the cycle matroid of a (multi)graph, even if it is not presented in terms of graphs, is called a graphic matroid. The matroids that are graphic have been characterized by Tutte.
Other matroids on graphs were discovered subsequently.
Graphic matroids have been generalized to matroids from signed graphs, gain graphs, and biased graphs. A graph G with a distinguished linear class B of cycles, known as a "biased graph", has two matroids, known as the frame matroid and the lift matroid of the biased graph (G,B). If every cycle belongs to the distinguished class, these matroids coincide with the cycle matroid of G. If no cycle is distinguished, the frame matroid is the bicircular matroid of G.
A signed graph, whose edges are labeled by signs, and a gain graph, which is a graph whose edges are labeled orientably from a group, have the same two matroids since it gives rise to a biased graph.
A matroid M is called a frame matroid if it, or a matroid that contains it, has a basis such that all the points of M are contained in the lines that join pairs of basis elements.
Given a set of "points", E, and a class A of subsets of E, a transversal of A is a subset S of E such that there is a onetoone function f from S to A by which x belongs to f (x) for each x in S. (A may have repeated members, which are treated as separate subsets of E.) The set of transversals forms the class of independent sets of a matroid, called the transversal matroid of (E, A). These matroids are a special simple case of the Gammoid structures defined above. Simply define a bipartite graph with A on the left, E on the right, and join X in A to x in E if x is an element of X. The distinguished sets in the gammoid are A and E respectively.
A third original source of matroid theory is field theory.
An extension of a field gives rise to a matroid. Suppose F and K are fields with K containing F. Let E be any finite subset of K. Define a subset S of E to be independent if the extension field F[S] has transcendence degree equal to S.
A matroid that is equivalent to a matroid of this kind is called an algebraic matroid. The problem of characterizing algebraic matroids is extremely difficult; little is known about it.
Matroids with a small number of elements are often pictured as in the diagram. The dots are the elements of the underlying set, and a curve has been drawn through every 3element circuit. The diagram shows a rank 3 matroid called the Fano matroid, an example that appeared in the original 1935 paper of Whitney.
The name arises from the fact that the Fano matroid is the projective plane of order 2, known as the Fano plane, whose coordinate field is the 2element field. This means the Fano matroid is the vector matroid associated to the seven nonzero vectors in a threedimensional vector space over a field with two elements.
It is known from projective geometry that the Fano matroid is not representable by any set of vectors in a real or complex vector space (or in any vector space over a field whose characteristic differs from 2).
A less famous example is the antiFano matroid, defined in the same way as the Fano matroid with the exception that the circle in the above diagram is missing. The antiFano matroid is representable over a field if and only if its characteristic differs from 2.
The direct sum of a Fano matroid and an antiFano matroid is the simplest example for a matroid which is not representable over any field.
On the other hand, consider this nonexample: let E be a set of pairs (v,c) where v ranges over the vertices of a graph and c ranges over the set {red, blue, yellow}. Let the independent sets be the sets of pairs that associate only one color with each vertex and do not associate the same color with two adjacent vertices; that is, they represent valid graph colorings. The empty set is a valid threecoloring, and any subset of a valid threecoloring is a valid threecoloring, but the exchange property does not hold, because it's possible to have two maximal threecolored subgraphs of different sizes, as shown to the right. It's no surprise that this is not a matroid, since if it were, it would give us a greedy algorithm for the NPcomplete 3coloring problem, showing P = NP.
Let M be a matroid with an underlying set of elements E, and let N be another matroid on underlying set F.
There are some standard ways to make new matroids out of old ones.
Let M be a matroid with an underlying set of elements E.
A matroid is regular if it can be represented by a totally unimodular matrix (a matrix whose square submatrices all have determinants equal to 0, 1, or −1). Tutte proved that the following three properties of a matroid are logically equivalent:
For this he used his difficult homotopy theorem. Simpler proofs have since been found.
Seymour's decomposition theorem states that all regular matroids can be built up in a simple way as the cliquesum of graphic matroids, their duals, and one special matroid. This theorem has major consequences for linear programming involving totally unimodular matrices.
A matroid that is representable over the twoelement field is called a binary matroid. Binary matroids include graphic and regular matroids. They have many of the nice properties of those types of matroid. Whitney and Tutte found famous characterizations. Addition of sets is symmetric difference. The following properties of a matroid M are equivalent:
The monograph of Recski compiled 8 equivalent definitions of binary matroids.
Suppose L is a list of matroids. The class Ex(L) of all matroids that do not contain as a minor any member of the list is said to be characterized by forbidden minors (or excluded minors). Some of the great theorems of matroid theory characterize natural classes of matroids by forbidden minors. Three examples due to Tutte:
It is easy to show that the matroids representable over a fixed field can be characterized by a list of forbidden minors. A famous outstanding problem (Rota's conjecture) is to prove that this list is finite for finite fields. This has been solved only for the fields of up to four elements (and the exact lists are known for those fields, but one cannot expect exact lists for larger fields). The problem is significant because there are matroid properties that can be characterized by forbidden minors but not by a finite list of them—for example, the property of being representable over the real numbers. (The nonexistence of any finite set of axioms for realrepresentable matroids is a famous theorem of Vamos (1978).)
The RobertsonSeymour Theorem, whose full proof runs to more than 500 pages, implies that every matroid property of graphic matroids characterized by a list of forbidden minors can be characterized by a finite list—in other words, if an infinite list L includes the forbidden minors for graphic matroids, then Ex(L) = Ex(L’) for some finite list L’.
If M is a finite matroid, we can define the dual matroid M* by taking the same underlying set and calling a set a basis in M* if and only if its complement is a basis in M. It is not difficult to verify that M* is a matroid and that the dual of M* is M.
The dual can be described equally well in terms of other ways to define a matroid. For instance:
A main result is the matroid version of Kuratowski's theorem: The dual of a graphic matroid M is a graphic matroid if and only if M is the matroid of a planar graph. In this case, the dual of M is the matroid of the dual graph of G.
A simpler result is that the dual of a vector matroid representable over a particular field F is also representable over F.
It is known that the dual of a transversal matroid is a strict gammoid and vice versa. See Box 15.2 in the monograph of Recski for the relations among gammoids, strict gammoids, transversal and fundamental transversal matroids
A weight function on a finite set E is a function w: E → R_{+} from E to the nonnegative real numbers. Such a weight function w can be extended to subsets S ⊆ E by defining
Suppose E is a finite set, F a nonempty family of subsets of E such that any subset of any element of F also belongs to F, and w: F → R_{+} a weight function on F. A greedy algorithm for (E, F, w) is any algorithm that attempts to construct a maximum weight element of F as follows:
The following two theorems establish a correspondence between matroids and sets (E, F) as defined above for which greedy algorithms do give maximum weight solutions.
The notion of matroid has been generalized to allow for other types of sets on which greedy algorithms give optimal solutions; see greedoid for more information.
The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. One of the difficulties is that there are many reasonable and useful definitions, none of which captures all the important aspects of finite matroid theory. For instance, it seems to be hard to have bases, circuits, and duality together in one notion of infinite matroids.
The simplest definition of an infinite matroid is to require finite rank; that is, the rank of E is finite. This theory is similar to that of finite matroids except for the failure of duality due to the fact that the dual of an infinite matroid of finite rank does not have finite rank. Finiterank matroids include any subsets of finitedimensional vector spaces and of field extensions of finite transcendence degree.
The next simplest infinite generalization is finitary matroids. A matroid is finitary if it has the property that
Equivalently, every dependent set contains a finite dependent set. Examples are linear dependence of arbitrary subsets of infinitedimensional vector spaces (but not infinite dependencies as in Hilbert and Banach spaces), and algebraic dependence in arbitrary subsets of field extensions of possibly infinite transcendence degree. Again, the class of finitary matroid is not selfdual, because the dual of a finitary matroid is not finitary. Finitary infinite matroids are studied in model theory, a branch of mathematical logic with strong ties to algebra.
There are two especially significant polynomials associated to a finite matroid M on the ground set E. Each is a matroid invariant, which means that isomorphic matroids have the same polynomial.
The characteristic polynomial of M (which is sometimes called the chromatic polynomial, although it does not count colorings), is defined to be
or equivalently (as long as the empty set is closed in M) as
When M is the cycle matroid of a graph G, the characteristic polynomial is a slight transformation of the chromatic polynomial, which is given by χ_{G} (λ) = λ^{c}p_{M(G)} (λ), where c is the number of connected components of G.
When M is the matroid of an arrangement A of linear hyperplanes in R^{n}, the characteristic polynomial of the arrangement is given by p_{A} (λ) = λ^{n−r(M)}p_{M(A)} (λ).
The Tutte polynomial of a matroid, T_{M} (x,y), generalizes the characteristic polynomial to two variables. This gives it more combinatorial interpretations, and also gives it the duality property
which implies a number of dualities between properties of M and properties of M *. One definition of the Tutte polynomial is
This expresses the Tutte polynomial as an evaluation of the coranknullity or rank generating polynomial,
Another definition is in terms of internal and external activities and a sum over bases. This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.
The Tutte polynomial T_{G} of a graph is the Tutte polynomial T_{M(G)} of its cycle matroid.
Two systems for calculations with matroids are Kingan's Oid and Hlineny's Macek.
"Oid" is an open source, interactive, extensible software system for experimenting with matroids.
"Macek" is a specialized software system with tools and routines for reasonably efficient combinatorial computations with representable matroids.
It is generally agreed that Hassler Whitney (1935) was the first to capture this abstraction of "independence". In his seminal paper, Whitney provided two axioms for independence, and defined any structure adhering to these axioms to be "matroids". (Although it was perhaps implied, he did not include an axiom requiring at least one subset to be independent.) His key observation was that these axioms provide an abstraction of "independence" that is common to both graphs and matrices. Because of this, many of the terms used in matroid theory resemble the terms for their analogous concepts in linear algebra or graph theory.
Almost immediately after Whitney first wrote about matroids, an important article was written by Saunders Mac Lane (1936) on the relation of matroids to projective geometry. A year later, Bartel van der Waerden (1937) noted similarities between algebraic and linear dependence in his classic textbook on Modern Algebra.
In the 1940s Richard Rado developed further theory under the name "independence systems" with an eye towards transversal theory, where his name for the subject is still sometimes used.
In the 1950s W. T. Tutte became the foremost figure in matroid theory, a position he retained for many years. His contributions were plentiful, including the characterization of binary, regular, and graphic matroids by excluded minors; the regularmatroid representability theorem; the theory of chain groups and their matroids; and the tools he used to prove many of his results, the "Path Theorem" and "Homotopy Theorem" (see, e.g., Tutte 1965), which are so complex that later theorists have gone to great trouble to eliminate the necessity of using them in proofs. (A fine example is A. M. H. Gerards' short proof (1989) of Tutte's characterization of regular matroids.)
Crapo (1969) and Brylawski (1972) generalized to matroids Tutte's "dichromate", a graphic polynomial now known as the Tutte polynomial (named by Crapo). Their work has recently been followed by a flood of papers—though not as many as on the Tutte polynomial of a graph.
In 1976 Dominic Welsh published the first comprehensive book on matroid theory.
Paul Seymour's decomposition theorem for regular matroids (1980) was the most significant and influential work of the late 1970s and the 1980s. Another fundamental contribution, by Kahn & Kung (1982), showed why projective geometries and Dowling geometries play such an important role in matroid theory.
By this time there were many other important contributors, but one should not omit to mention Geoff Whittle's extension to ternary matroids of Tutte's characterization of binary matroids that are representable over the rationals (Whittle 1995), perhaps the biggest single contribution of the 1990s. In the current decade the Matroid Minors Project of Geelen, Gerards, Whittle, and others, which attempts to duplicate for matroids that are representable over a finite field the success of the Robertson–Seymour Graph Minors Project (see Robertson–Seymour theorem), has produced substantial advances in the structure theory of matroids. Many others have also contributed to that part of matroid theory, which is presently flourishing.
Mathematicians who pioneered the study of matroids include the following:
Other major contributors include:
There is an online list of current researchers.
