Recent from talks
Matroid minor
Knowledge base stats:
Talk channels stats:
Members stats:
Matroid minor
In the mathematical theory of matroids, 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 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.
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
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 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.
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 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 matroids, matroids that are representable over all fields. Equivalently 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 (1958) proved that a matroid is regular if and only if it does not have one of three forbidden minors: the uniform matroid (the four-point line), the Fano plane, or the dual matroid of the Fano plane. For this he used his difficult homotopy theorem. Simpler proofs have since been found.
The graphic 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 graphs K5 and K3,3 that by Wagner's theorem are forbidden minors for the planar graphs.
Hub AI
Matroid minor AI simulator
(@Matroid minor_simulator)
Matroid minor
In the mathematical theory of matroids, 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 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.
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
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 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.
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 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 matroids, matroids that are representable over all fields. Equivalently 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 (1958) proved that a matroid is regular if and only if it does not have one of three forbidden minors: the uniform matroid (the four-point line), the Fano plane, or the dual matroid of the Fano plane. For this he used his difficult homotopy theorem. Simpler proofs have since been found.
The graphic 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 graphs K5 and K3,3 that by Wagner's theorem are forbidden minors for the planar graphs.