Matroid minors are closely related to graph minors, and the restriction and contraction operations by which they are formed correspond to edge deletion and edge contraction operations in graphs.
Often, but not always, the set of forbidden matroids is finite, paralleling the Robertson–Seymour theorem which states that the set of forbidden minors of a minor-closed graph family is always finite.
[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 the real numbers have infinitely many forbidden minors.
If r denotes the rank function of the matroid, then the width of an e-separation is defined as r(A) + r(B) − r(M) + 1.
[5] Branchwidth is an important component of attempts to extend the theory of graph minors to matroids: although treewidth 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.
Another way of saying the same thing is that the partial order on graphic matroids formed by the minor operation is a well-quasi-ordering.
Robertson and Seymour conjectured that the matroids representable over any particular finite field are well-quasi-ordered.
[11] As a consequence, linear programs defined by totally unimodular matrices may be solved combinatorially by combining the solutions to a set of minimum spanning tree problems corresponding to the graphic and co-graphic parts of this decomposition.
By combining this result with the Robertson–Seymour theorem, it is possible to recognize the members of any minor-closed graph family in polynomial time.
[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.