Regular matroid

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 $M$ is regular when, for every field $F$, $M$ can be represented by a system of vectors over $F$.{{citation

| last = Fujishige | first = Satoru

| isbn = 9780444520869

| page = 24

| publisher = Elsevier

| series = Annals of Discrete Mathematics

| title = Submodular Functions and Optimization

| year = 2005}}.{{citation

| last = Oxley | first = James G. | authorlink = James Oxley

| isbn = 9780199202508

| page = 209

| publisher = Oxford University Press

| series = Oxford Graduate Texts in Mathematics

| title = Matroid Theory

| volume = 3

| year = 2006}}.

If a matroid is regular, so is its dual matroid, and so is every one of its minors.{{harvtxt|Oxley|2006}}, p. 112. Every direct sum of regular matroids remains regular.{{harvtxt|Oxley|2006}}, p. 131.

Every graphic matroid (and every co-graphic matroid) is regular.{{citation

| last = Tutte | first = W. T.

| journal = Journal of Research of the National Bureau of Standards

| mr = 0179781

| pages = 1–47

| title = Lectures on matroids

| url = http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66650

| volume = 69B

| year = 1965

| doi=10.6028/jres.069b.001| doi-access = free

}}. 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.{{citation

| last = Seymour | first = P. D. | authorlink = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(80)90075-1

| issue = 3

| journal = Journal of Combinatorial Theory

| mr = 579077

| pages = 305–359

| series = Series B

| title = Decomposition of regular matroids

| volume = 28

| year = 1980| hdl = 10338.dmlcz/101946

| hdl-access = free

}}.

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

| last = Maurer | first = Stephen B.

| issue = 1

| journal = SIAM Journal on Applied Mathematics

| mr = 0392635

| pages = 143–148

| title = Matrix generalizations of some theorems on trees, cycles and cocycles in graphs

| volume = 30

| year = 1976

| doi=10.1137/0130017}}.

The uniform matroid $U\{\}^2\_4$ (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 {{harvtxt|Tutte|1958}} 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 $U\{\}^2\_4$, the Fano plane, or its dual.{{citation

| last = Tutte | first = W. T. | authorlink = W. T. Tutte

| journal = Transactions of the American Mathematical Society

| mr = 0101526

| pages = 144–174

| title = A homotopy theorem for matroids. I, II

| volume = 88

| issue = 1 | year = 1958

| doi=10.2307/1993244| jstor = 1993244 }}.

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

| last = Seymour | first = P. D. | authorlink = Paul Seymour (mathematician)

| doi = 10.1016/0095-8956(79)90055-8

| issue = 2

| journal = Journal of Combinatorial Theory

| mr = 532586

| pages = 159–173

| series = Series B

| title = Matroid representation over GF(3)

| volume = 26

| year = 1979| doi-access = free

}}.

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.{{harvtxt|Oxley|2006}}, p. 20. 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. {{harvtxt|Gerards|1989}} later published an alternative and simpler proof of the characterization of unimodular matrices by forbidden minors.{{citation|last=Gerards|first=A. M. H.|year=1989|title=A short proof of Tutte's characterization of totally unimodular matrices|journal=Linear Algebra and Its Applications|volume=114/115|pages=207–212|doi=10.1016/0024-3795(89)90461-8|doi-access=free}}.

There is a polynomial time algorithm for testing whether a matroid is regular, given access to the matroid through an independence oracle.{{citation

| last = Truemper | first = K.

| issue = 3

| journal = European Journal of Combinatorics

| mr = 679212

| pages = 275–291

| title = On the efficiency of representability tests for matroids

| volume = 3

| year = 1982

| doi=10.1016/s0195-6698(82)80039-5| doi-access = free

}}.

{{reflist|colwidth=30em}}

Category:Matroid theory