In the mathematical theory of

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 ...

s, a minor of a matroid ''M'' is another matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations. Matroid minors are closely related to

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

s, 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.

Definitions

If ''M'' is a matroid on the set ''E'' and ''S'' is a subset of ''E'', then 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''. If ''T'' is an independent subset of ''E'', the contraction of ''M'' by ''T'', written ''M''/''T'', is the matroid on the underlying set ''E − T'' whose independent sets are the sets whose union with ''T'' is independent in ''M''. This definition may be extended to arbitrary ''T'' by choosing a basis for ''T'' and defining a set to be independent in the contraction if its union with this basis remains independent in ''M''. The rank function of the contraction is

r'(A) = r(A \cup T) - r(T).

A matroid ''N'' is a minor of a matroid ''M'' if it can be constructed from ''M'' by restriction and contraction operations. In terms of the

geometric lattice In the mathematics of matroids and lattices, a geometric lattice is a finite atomistic semimodular lattice, and a matroid lattice is an atomistic semimodular lattice without the assumption of finiteness. Geometric lattices and matroid lattices, r ...

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.

Forbidden matroid characterizations

Many important families of matroids are closed under the operation of taking minors: if a matroid ''M'' belongs to the family, then every minor of ''M'' 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 the

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is c ...

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 the

regular matroid In mathematics, a regular matroid is a matroid that can be represented over all fields. Definition A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". On ...

s, matroids that are representable over all fields. Equivalently a matroid is regular if it can be represented by a

totally unimodular matrix In mathematics, a unimodular matrix ''M'' is a square matrix, square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible matrix, invertible over the integers: there is an integer matrix ''N'' th ...

(a matrix whose square submatrices all have determinants equal to 0, 1, or −1). proved that a matroid is regular if and only if it does not have one of three forbidden minors: the

uniform matroid In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...

U^2_4

(the four-point line), the

Fano plane In finite geometry, the Fano plane (after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and lines ...

, or the

dual matroid In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it... Matroid duals go back to the original paper by Hassler ...

of the Fano plane. For this he used his difficult homotopy theorem. Simpler proofs have since been found. The

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called ...

s, 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 graphs ''K''₅ and ''K''_3,3 that by Wagner's theorem are forbidden minors for the planar graphs. The

binary matroid In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).. That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent i ...

s, matroids representable over the two-element

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...

, 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. A full proof of this conjecture has been announced by Geelen, Gerards, and Whittle; it has not appeared. However, the matroids that can be represented over the

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...

s have infinitely many forbidden minors.

Branchwidth

Branch-decompositions of matroids may be defined analogously to their definition for graphs. A branch-decomposition of a matroid is a hierarchical 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. If ''r'' denotes the rank function of the matroid, then the width of an e-separation is defined as . 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 corresponding

may differ: for instance, the three-edge

path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

and the three-edge star have different branchwidths, 2 and 1 respectively, but they both induce the same graphic matroid with branchwidth 1. However, for graphs that are not trees, the branchwidth of the graph is equal to the branchwidth of its associated graphic matroid. The branchwidth of a matroid always equals the branchwidth of its dual.. Branchwidth is an important component of attempts to extend the theory of graph minors to matroids: although

treewidth In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...

can also be generalized to matroids, and plays a bigger role than branchwidth in the theory of graph minors, branchwidth has more convenient properties in the matroid setting.. 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.

Well-quasi-ordering

The

implies that every matroid property of ''graphic'' matroids characterized by a list of forbidden minors can be characterized by a finite list. Another way of saying the same thing is that the

partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...

on graphic matroids formed by the minor operation is a

well-quasi-ordering In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x_0, x_1, x_2, \ldots from X contains an increasing pair x_i \leq x_j with i x_2> \cdots) nor infinite sequenc ...

. 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 particular

are well-quasi-ordered. So far this has been proven only for the matroids of bounded branchwidth.

Matroid decompositions

The

graph structure theorem In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seven ...

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 by

clique-sum In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs ''G'' and ''H'' each contain cliques of equal size, th ...

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.. As a consequence,

linear program Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming i ...

s defined by totally unimodular matrices may be solved combinatorially by combining the solutions to a set of

minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

problems corresponding to the graphic and co-graphic parts of this decomposition.

Algorithms and complexity

One of the important components of graph minor theory is the existence of an algorithm for testing whether a graph ''H'' is a minor of another graph ''G'', taking an amount of time that is polynomial in ''G'' for any fixed choice of ''H'' (and more strongly

fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...

if the size of ''H'' 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 in polynomial 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 the

matroid oracle In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or ...

model, the only minors that can be recognized in polynomial time are the

s with rank or corank one. 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.

Notes

References

*. *. *. *. *. *. * *. Addendum and corrigendum: . *. *. *. *. *. *. *. {{refend Graph minor theory Minor