Regular matroid
Template:Short description 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". One of the ways of constructing a matroid is to select a finite set of vectors in a vector space, and to define a subset of the vectors to be independent in the matroid when it is linearly independent in the vector space. Every family of sets constructed in this way is a matroid, but not every matroid can be constructed in this way, and the vector spaces over different fields lead to different sets of matroids that can be constructed from them.
A matroid is regular when, for every field , can be represented by a system of vectors over .[1][2]
Properties
If a matroid is regular, so is its dual matroid,[1] and so is every one of its minors.[3] Every direct sum of regular matroids remains regular.[4]
Every graphic matroid (and every co-graphic matroid) is regular.[5] Conversely, every regular matroid may be constructed by combining graphic matroids, co-graphic matroids, and a certain ten-element matroid that is neither graphic nor co-graphic, using an operation for combining matroids that generalizes the clique-sum operation on graphs.[6]
The number of bases in a regular matroid may be computed as the determinant of an associated matrix, generalizing Kirchhoff's matrix-tree theorem for graphic matroids.[7]
Characterizations
The uniform matroid (the four-point line) is not regular: it cannot be realized over the two-element finite field GF(2), so it is not a binary matroid, although it can be realized over all other fields. The matroid of the Fano plane (a rank-three matroid in which seven of the triples of points are dependent) and its dual are also not regular: they can be realized over GF(2), and over all fields of characteristic two, but not over any other fields than those. As Template:Harvtxt showed, these three examples are fundamental to the theory of regular matroids: every non-regular matroid has at least one of these three as a minor. Thus, the regular matroids are exactly the matroids that do not have one of the three forbidden minors , the Fano plane, or its dual.[8]
If a matroid is regular, it must clearly be realizable over the two fields GF(2) and GF(3). The converse is true: every matroid that is realizable over both of these two fields is regular. The result follows from a forbidden minor characterization of the matroids realizable over these fields, part of a family of results codified by Rota's conjecture.[9]
The regular matroids are the matroids that can be defined from a totally unimodular matrix, a matrix in which every square submatrix has determinant 0, 1, or −1. The vectors realizing the matroid may be taken as the rows of the matrix. For this reason, regular matroids are sometimes also called unimodular matroids.[10] The equivalence of regular matroids and unimodular matrices, and their characterization by forbidden minors, are deep results of W. T. Tutte, originally proved by him using the Tutte homotopy theorem.[8] Template:Harvtxt later published an alternative and simpler proof of the characterization of unimodular matrices by forbidden minors.[11]
Algorithms
There is a polynomial time algorithm for testing whether a matroid is regular, given access to the matroid through an independence oracle.[12]
References
- ↑ 1.0 1.1 Template:Citation.
- ↑ Template:Citation.
- ↑ Template:Harvtxt, p. 112.
- ↑ Template:Harvtxt, p. 131.
- ↑ Template:Citation.
- ↑ Template:Citation.
- ↑ Template:Citation.
- ↑ 8.0 8.1 Template:Citation.
- ↑ Template:Citation.
- ↑ Template:Harvtxt, p. 20.
- ↑ Template:Citation.
- ↑ Template:Citation.