Rota's conjecture

From Wikipedia, the free encyclopedia

Mathematician Gian-Carlo Rota conjectured in 1971 that, for every finite field, the family of matroids that can be represented over that field has finitely many forbidden minors.[1] Rota's conjecture is now known to be true for fields of four or fewer elements, but remains unproven for larger fields.

Statement of the conjecture

If S is a set of points in a vector space defined over a field F, then the linearly independent subsets of S form the independent sets of a matroid M; S is said to be a representation of any matroid isomorphic to M. Not every matroid has a representation over every field; for instance, the Fano plane (a matroid with seven elements in which a set of up to three points is independent if it does not form one of seven three-point lines) is representable only over fields of characteristic two. Therefore, the matroids that are representable over a field F form a proper subclass of all matroids.

A minor of a matroid is another matroid formed by two operations: restriction and contraction. In the case of points from a vector space, restriction is simply the removal of some of the points from S; contraction is a dual operation in which points are removed and the remaining space is projected into a space complementary to the span of the removed points. Thus, minors preserve representability. A matroid that is not representable over F, and is minor-minimal with that property, is called a "forbidden minor"; a matroid M is representable over F if and only if it does not contain one of the forbidden minors.

For representability over the real numbers, there are infinitely many forbidden minors.[2] Rota's conjecture is that, for every finite field F, there are only a finite number of forbidden minors.

Partial results

W. T. Tutte proved that the binary matroids (matroids representable over the field of two elements) have a single forbidden minor, the uniform matroid U{}_{4}^{2} (geometrically, a line with four points on it).[3][4]

A matroid is representable over the ternary field GF(3) if and only if it does not have one or more of the following four matroids as minors: a five-point line U{}_{5}^{2}, its dual matroid U{}_{5}^{3} (five points in general position in three dimensions), the Fano plane, or the dual of the Fano plane. Thus, Rota's conjecture is true in this case as well.[5][6] As a consequence of this result and of the forbidden minor characterization by Tutte (1958) of the regular matroids (matroids that can be represented over all fields) it follows that a matroid is regular if and only if it is both binary and ternary.[6]

There are seven forbidden minors for the matroids representable over GF(4).[7] They are:

  • The six-point line U{}_{6}^{2}.
  • The dual U{}_{6}^{4} to the six-point line, six points in general position in four dimensions.
  • A self-dual six-point rank-three matroid with a single three-point line.
  • The non-Fano matroid formed by the seven points at the vertices, edge midpoints, and centroid of an equilateral triangle in the Euclidean plane. This configuration is one of two known sets of planar points with fewer than n/2 two-point lines.[8]
  • The dual of the non-Fano matroid,
  • The eight-point matroid of a square antiprism, and the dual of the antiprism matroid.

This result won the 2003 Fulkerson Prize for its authors Jim Geelen, A. M. H. Gerards, and A. Kapoor.[9]

For GF(5), several forbidden minors on up to 12 elements are known,[10] but it is not known whether the list is complete.

Reported proof

Geoff Whittle announced recently during a visit to the UK that he, Jim Geelen, and Bert Gerards have solved Rota's Conjecture. It will take them some years to write up their research in its entirety and publish it.[11] [12]


See also

References

  1. ↑ Rota, Gian-Carlo (1971), "Combinatorial theory, old and new", Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Paris: Gauthier-Villars, pp. 229–233, MR 0505646 .
  2. ↑ Vámos, P. (1978), "The missing axiom of matroid theory is lost forever", Journal of the London Mathematical Society, Second Series 18 (3): 403–408, doi:10.1112/jlms/s2-18.3.403, MR 518224 .
  3. ↑ Tutte, W. T. (1958), "A homotopy theorem for matroids. I, II", Transactions of the American Mathematical Society 88: 144–174, MR 0101526 .
  4. ↑ Tutte, W. T. (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards 69B: 1–47, MR 0179781 . See in particular section 5.3, "Characterization of binary matroids", p.17.
  5. ↑ Bixby, Robert E. (1979), "On Reid's characterization of the ternary matroids", Journal of Combinatorial Theory, Series B 26 (2): 174–204, doi:10.1016/0095-8956(79)90056-X, MR 532587 . Bixby attributes this characterization of ternary matroids to Ralph Reid.
  6. ↑ 6.0 6.1 Seymour, P. D. (1979), "Matroid representation over GF(3)", Journal of Combinatorial Theory, Series B 26 (2): 159–173, doi:10.1016/0095-8956(79)90055-8, MR 532586 .
  7. ↑ Geelen, J. F.; Gerards, A. M. H.; Kapoor, A. (2000), "The excluded minors for GF(4)-representable matroids", Journal of Combinatorial Theory, Series B 79 (2): 247–299, doi:10.1006/jctb.2000.1963, MR 1769191 .
  8. ↑ Kelly, L. M.; Moser, W. O. J. (1958), "On the number of ordinary lines determined by n points", Canad. J. Math. 10: 210–219, doi:10.4153/CJM-1958-024-6 .
  9. ↑ 2003 Fulkerson Prize citation, retrieved 2012-08-18.
  10. ↑ Betten, A.; Kingan, R. J.; Kingan, S. R. (2007), "A note on GF(5)-representable matroids", MATCH Communications in Mathematical and in Computer Chemistry 58 (2): 511–521, MR 2357372 .
  11. ↑ Rota's Conjecture: Researcher solves 40-year-old math problem PhysOrg, August 15, 2013.
  12. ↑ CWI researcher proves famous Rota’s Conjecture CWI, August 22, 2013.
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.