Matroid

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice.

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. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory.[1][2]

There are many equivalent (cryptomorphic) ways to define a (finite) matroid.[3]

The first two properties define a combinatorial structure known as an independence system (or abstract simplicial complex).

A set whose closure equals itself is said to be closed, or a flat or subspace of the matroid.[5] A set is closed if it is maximal for its rank, meaning that the addition of any other element to the set would increase the rank. The closed sets of a matroid are characterized by a covering partition property:

Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. There are two ways to present the matroids defined in this way:

A regular matroid is a matroid that is representable over all possible fields. The Vámos matroid is the simplest example of a matroid that is not representable over any field.

A matroid that is equivalent to a matroid of this kind is called an algebraic matroid.[13] The problem of characterizing algebraic matroids is extremely difficult; little is known about it. The Vámos matroid provides an example of a matroid that is not algebraic.

If M is a finite matroid, we can define the orthogonal or 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.[14]

The dual can be described equally well in terms of other ways to define a matroid. For instance:

According to a 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.[15] The dual of a vector matroid representable over a particular field F is also representable over F. The dual of a transversal matroid is a strict gammoid and vice versa.

If M is a matroid with element set E, and S is a subset of E, the restriction of M to S, written M |S, is the matroid on the set S whose independent sets are the independent sets of M that are contained in S. Its circuits are the circuits of M that are contained in S and its rank function is that of M restricted to subsets of S. In linear algebra, this corresponds to restricting to the subspace generated by the vectors in S. Equivalently if T = MS this may be termed the deletion of T, written M\T or MT. The submatroids of M are precisely the results of a sequence of deletions: the order is irrelevant.[16][17]

A matroid N that is obtained from M by a sequence of restriction and contraction operations is called a minor of M.[17][20] We say M contains N as a minor. Many important families of matroids may be characterized by the minor-minimal matroids that do not belong to the family; these are called forbidden or excluded minors.[21]

Let M be a matroid with an underlying set of elements E, and let N be another matroid on an underlying set F. The direct sum of matroids M and N is the matroid whose underlying set is the disjoint union of E and F, and whose independent sets are the disjoint unions of an independent set of M with an independent set of N.

The union of M and N is the matroid whose underlying set is the union (not the disjoint union) of E and F, and whose independent sets are those subsets that are the union of an independent set in M and one in N. Usually the term "union" is applied when E = F, but that assumption is not essential. If E and F are disjoint, the union is the direct sum.

A weighted matroid is a matroid together with a function from its elements to the nonnegative real numbers. The weight of a subset of elements is defined to be the sum of the weights of the elements in the subset. The greedy algorithm can be used to find a maximum-weight basis of the matroid, by starting from the empty set and repeatedly adding one element at a time, at each step choosing a maximum-weight element among the elements whose addition would preserve the independence of the augmented set.[29] This algorithm does not need to know anything about the details of the matroid's definition, as long as it has access to the matroid through an independence oracle, a subroutine for testing whether a set is independent.

This optimization algorithm may be used to characterize matroids: if a family F of sets, closed under taking subsets, has the property that, no matter how the sets are weighted, the greedy algorithm finds a maximum-weight set in the family, then F must be the family of independent sets of a matroid.[30]

The notion of matroid has been generalized to allow for other types of sets on which a greedy algorithm gives optimal solutions; see greedoid and matroid embedding for more information.

The matroid partitioning problem is to partition the elements of a matroid into as few independent sets as possible, and the matroid packing problem is to find as many disjoint spanning sets as possible. Both can be solved in polynomial time, and can be generalized to the problem of computing the rank or finding an independent set in a matroid sum.

The intersection of two or more matroids is the family of sets that are simultaneously independent in each of the matroids. The problem of finding the largest set, or the maximum weighted set, in the intersection of two matroids can be found in polynomial time, and provides a solution to many other important combinatorial optimization problems. For instance, maximum matching in bipartite graphs can be expressed as a problem of intersecting two partition matroids. However, finding the largest set in an intersection of three or more matroids is NP-complete.

Two standalone systems for calculations with matroids are Kingan's and Hlineny's . Both of them are open sourced packages. "Oid" is an 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.

Both open source mathematics software systems SAGE and Macaulay2 contain matroid packages.

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,[31] although it does not count colorings), is defined to be

where μ denotes the Möbius function of the geometric lattice of the matroid and the sum is taken over all the flats A of the matroid.[32]

When M is the cycle matroid M(G) of a graph G, the characteristic polynomial is a slight transformation of the chromatic polynomial, which is given by χG (λ) = λcpM(G) (λ), where c is the number of connected components of G.

When M is the bond matroid M*(G) of a graph G, the characteristic polynomial equals the flow polynomial of G.

When M is the matroid M(A) of an arrangement A of linear hyperplanes in Rn (or Fn where F is any field), the characteristic polynomial of the arrangement is given by pA (λ) = λnr(M)pM(A) (λ).

The beta invariant of a matroid, introduced by Crapo (1967), may be expressed in terms of the characteristic polynomial p as an evaluation of the derivative[33]

The beta invariant is non-negative, and is zero if and only if M is disconnected, or empty, or a loop. Otherwise it depends only on the lattice of flats of M. If M has no loops and coloops then β(M) = β(M).[34]

The Tutte polynomial of a matroid, TM (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 corank-nullity or rank generating polynomial,[35]

From this definition it is easy to see that the characteristic polynomial is, up to a simple factor, an evaluation of TM, specifically,

Another definition is in terms of internal and external activities and a sum over bases, reflecting the fact that T(1,1) is the number of bases.[36] This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.

There is a further definition in terms of recursion by deletion and contraction.[37] The deletion-contraction identity is

An invariant of matroids (i.e., a function that takes the same value on isomorphic matroids) satisfying this recursion and the multiplicative condition

is said to be a Tutte-Grothendieck invariant.[35] The Tutte polynomial is the most general such invariant; that is, the Tutte polynomial is a Tutte-Grothendieck invariant and every such invariant is an evaluation of the Tutte polynomial.[31]

The Tutte polynomial TG  of a graph is the Tutte polynomial TM(G) of its cycle matroid.

The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. For a long time, one of the difficulties has been that there were many reasonable and useful definitions, none of which appeared to capture all the important aspects of finite matroid theory. For instance, it seemed 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. Finite-rank matroids include any subsets of finite-dimensional 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 infinite-dimensional 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 self-dual, 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.

In the late 1960s matroid theorists asked for a more general notion that shares the different aspects of finite matroids and generalizes their duality. Many notions of infinite matroids were defined in response to this challenge, but the question remained open. One of the approaches examined by D.A. Higgs became known as B-matroids and was studied by Higgs, Oxley and others in the 1960s and 1970s. According to a recent result by Bruhn, Diestel, and Kriesell et al. (2013), it solves the problem: Arriving at the same notion independently, they provided five equivalent systems of axiom—in terms of independence, bases, circuits, closure and rank. The duality of B-matroids generalizes dualities that can be observed in infinite graphs.

Matroid theory was introduced by Hassler Whitney (1935). It was also independently discovered by Takeo Nakasawa, whose work was forgotten for many years (Nishimura & Kuroda 2009).

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, B. L. 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 regular-matroid 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 "Tutte 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.)

Henry Crapo (1969) and Thomas Brylawski (1972) generalized to matroids Tutte's "dichromate", a graphic polynomial now known as the Tutte polynomial (named by Crapo). Their work has recently (especially in the 2000s) 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 period (since around 2000) the Matroid Minors Project of Jim 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 (in the first and second decades of the 21st century) is flourishing.

Mathematicians who pioneered the study of matroids include Takeo Nakasawa,[38] Saunders Mac Lane, Richard Rado, W. T. Tutte, B. L. van der Waerden, and Hassler Whitney. Other major contributors include Jack Edmonds, Jim Geelen, Eugene Lawler, László Lovász, Gian-Carlo Rota, P. D. Seymour, and Dominic Welsh.