In the mathematical theory ofmatroids, aminor of a matroidM is another matroidN that is obtained fromM by a sequence of restriction and contraction operations. Matroid minors are closely related tograph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs. The theory of matroid minors leads to structural decompositions of matroids, and characterizations of matroid families by forbidden minors, analogous to the corresponding theory in graphs.

IfM is a matroid on the setE andS is a subset ofE, then the restriction ofM toS, writtenM |S, is the matroid on the setS whose independent sets are the independent sets ofM that are contained inS. Its circuits are the circuits ofM that are contained inS and itsrank function is that ofM restricted to subsets ofS.

IfT is an independent subset ofE, the contraction ofM byT, writtenM/T, is the matroid on the underlying setE − T whose independent sets are the sets whose union withT is independent inM. This definition may be extended to arbitraryT by choosing a basis forT and defining a set to be independent in the contraction if its union with this basis remains independent inM. The rank function of the contraction is${\displaystyle r^{\prime }(A)=r(A\cup T)-r(T).}$

A matroidN is a minor of a matroidM if it can be constructed fromM by restriction and contraction operations.

In terms of thegeometric lattice formed by the flats of a matroid, taking a minor of a matroid corresponds to taking an interval of the lattice, the part of the lattice lying between a given lower bound and upper bound element.^[1]

Many important families of matroids are closed under the operation of taking minors: if a matroidM belongs to the family, then every minor ofM also belongs to the family. In this case, the family may be characterized by its set of "forbidden matroids", the minor-minimal matroids that do not belong to the family. A matroid belongs to the family if and only if it does not have a forbidden matroid as a minor. Often, but not always, the set of forbidden matroids is finite, paralleling theRobertson–Seymour theorem which states that the set of forbidden minors of a minor-closed graph family is always finite.

An example of this phenomenon is given by theregular matroids, matroids that are representable over all fields. Equivalently a matroid is regular if it can be represented by atotally unimodular matrix (a matrix whose square submatrices all have determinants equal to 0, 1, or −1).Tutte (1958) proved that a matroid is regular if and only if it does not have one of three forbidden minors: theuniform matroid${\displaystyle U{}_4^2}$ (the four-point line), theFano plane, or thedual matroid of the Fano plane. For this he used his difficulthomotopy theorem. Simpler proofs have since been found.

Thegraphic matroids, matroids whose independent sets are the forest subgraphs of a graph, have five forbidden minors: the three for the regular matroids, and the two duals of the graphic matroids for the graphsK₅ andK_3,3 that byWagner's theorem are forbidden minors for theplanar graphs.

Thebinary matroids, matroids representable over the two-elementfinite field, include both graphic and regular matroids. Tutte again showed that these matroids have a forbidden minor characterization: they are the matroids that do not have the four-point line as a minor.Rota conjectured that, for any finite field, the matroids representable over that field have finitely many forbidden minors.^[2] A proof of this conjecture was announced, but not published, by Geelen, Gerards, and Whittle in 2014.^[3] The matroids that can be represented over thereal numbers have infinitely many forbidden minors.^[4]

Branch-decompositions of matroids may be defined analogously to their definition for graphs.A branch-decomposition of a matroid is ahierarchical clustering of the matroid elements, represented as an unrooted binary tree with the elements of the matroid at its leaves. Removing any edge of this tree partitions the matroids into two disjoint subsets; such a partition is called an e-separation. Ifr denotes the rank function of the matroid, then the width of an e-separation is defined asr(A) +r(B) −r(M) + 1. The width of a decomposition is the maximum width of any of its e-separations, and the branchwidth of a matroid is the minimum width of any of its branch-decompositions.

The branchwidth of a graph and the branchwidth of the correspondinggraphic matroid may differ: for instance, the three-edgepath graph and the three-edgestar have different branchwidths, 2 and 1 respectively, but they both induce the same graphic matroid with branchwidth 1.^[5] However, for graphs that are not trees, the branchwidth of the graph is equal to the branchwidth of its associated graphic matroid.^[6] The branchwidth of a matroid always equals the branchwidth of its dual.^[5]

Branchwidth is an important component of attempts to extend the theory of graph minors to matroids: althoughtreewidth can also be generalized to matroids,^[7] and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting.^[8]If a minor-closed family of matroids representable over a finite field does not include the graphic matroids of all planar graphs, then there is a constant bound on the branchwidth of the matroids in the family, generalizing similar results for minor-closed graph families.^[9]

TheRobertson–Seymour theorem implies that every matroid property ofgraphic matroids characterized by a list of forbidden minors can be characterized by a finite list. Another way of saying the same thing is that thepartial order on graphic matroids formed by the minor operation is awell-quasi-ordering. However, the example of the real-representable matroids, which have infinitely many forbidden minors, shows that the minor ordering is not a well-quasi-ordering on all matroids.

Robertson and Seymour conjectured that the matroids representable over any particularfinite field are well-quasi-ordered. So far this has been proven only for the matroids of bounded branchwidth.^[10]

Thegraph structure theorem is an important tool in the theory of graph minors, according to which the graphs in any minor-closed family can be built up from simpler graphs byclique-sum operations. Some analogous results are also known in matroid theory. In particular,Seymour's decomposition theorem states that all regular matroids can be built up in a simple way as the clique-sum of graphic matroids, their duals, and one special 10-element matroid.^[11] As a consequence,linear programs defined by totally unimodular matrices may be solved combinatorially by combining the solutions to a set ofminimum spanning tree problems corresponding to the graphic and co-graphic parts of this decomposition.

One of the important components of graph minor theory is the existence of an algorithm for testing whether a graphH is a minor of another graphG, taking an amount of time that is polynomial inG for any fixed choice ofH (and more stronglyfixed-parameter tractable if the size ofH is allowed to vary). By combining this result with the Robertson–Seymour theorem, it is possible to recognize the members of any minor-closed graph family inpolynomial time. Correspondingly, in matroid theory, it would be desirable to develop efficient algorithms for recognizing whether a given fixed matroid is a minor of an input matroid. Unfortunately, such a strong result is not possible: in thematroid oracle model, the only minors that can be recognized in polynomial time are theuniform matroids with rank or corank one.^[12] However, if the problem is restricted to the matroids that are representable over some fixed finite field (and represented as a matrix over that field) then, as in the graph case, it is conjectured to be possible to recognize the matroids that contain any fixed minor in polynomial time.^[8]

• Graph minor theory
• Matroid theory

• Articles with short description
• Short description is different from Wikidata