Rota's Conjecture
   HOME

TheInfoList



OR:

Rota's excluded minors conjecture is one of a number of conjectures made by the mathematician
Gian-Carlo Rota Gian-Carlo Rota (April 27, 1932 – April 18, 1999) was an Italian-American mathematician and philosopher. He spent most of his career at the Massachusetts Institute of Technology, where he worked in combinatorics, functional analysis, proba ...
. It is considered an important problem by some members of the structural combinatorics community. Rota
conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
d in 1971 that, for every
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, the family of
matroid In combinatorics, 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 Axiomatic system, axiomatically, the most significant being in terms ...
s that can be represented over that field has only finitely many excluded minors. A proof of the conjecture was announced, but not published, in 2014 by Geelen, Gerards, and Whittle.


Statement of the conjecture

If S is a set of points in a
vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
defined over a field F, then the linearly independent subsets of S form the independent sets of a
matroid In combinatorics, 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 Axiomatic system, axiomatically, the most significant being in terms ...
M; S is said to be a
representation Representation may refer to: Law and politics *Representation (politics), political activities undertaken by elected representatives, as well as other theories ** Representative democracy, type of democracy in which elected officials represent a ...
of any matroid isomorphic to M. Not every matroid has a representation over every field, for instance, the
Fano plane In finite geometry, the Fano plane (named 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 ...
is representable only over fields of characteristic two. Other matroids are representable over no fields at all. The matroids that are representable over a particular field form a proper subclass of all matroids. A
minor Minor may refer to: Common meanings * Minor (law), a person not under the age of certain legal activities. * Academic minor, a secondary field of study in undergraduate education Mathematics * Minor (graph theory), a relation of one graph to an ...
of a matroid is another matroid formed by a sequence of two operations: deletion and contraction. In the case of points from a vector space, deleting a point is simply the removal of that point from S; contraction is a dual operation in which a point is removed and the remaining points are projected a
hyperplane In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...
that does not contain the removed points. It follows from this if a matroid is representable over a field, then so are all its minors. A matroid that is not representable over F, and is minor- minimal with that property, is called an "excluded minor"; a matroid M is representable over F
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
it does not contain one of the forbidden minors. For representability 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 duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
s, there are infinitely many forbidden minors. Rota's conjecture is that, for every finite field F, there is only a finite number of forbidden minors.


Partial results

W. T. Tutte William Thomas Tutte (; 14 May 1917 – 2 May 2002) was an English and Canadian code breaker and mathematician. During the Second World War, he made a fundamental advance in cryptanalysis of the Lorenz cipher, a major Nazi German cipher system ...
proved that 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 if ...
s (matroids representable over the field of two elements) have a single forbidden minor, 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 symme ...
U^2_4 (geometrically, a line with four points on it). 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^2_5, its
dual matroid Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a ...
U^3_5 (five points in
general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that a ...
in three dimensions), the Fano plane, or the dual of the Fano plane. Thus, Rota's conjecture is true in this case as well.. As a consequence of this result and of the forbidden minor characterization by 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. There are seven forbidden minors for the matroids representable over GF(4). They are: *The six-point line U^2_6. *The dual U^4_6 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 An equilateral triangle is a triangle in which all three sides have the same length, and all three angles are equal. Because of these properties, the equilateral triangle is a regular polygon, occasionally known as the regular triangle. It is the ...
in the
Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...
. This configuration is one of two known sets of planar points with fewer than n/2 two-point lines. *The dual of the non-Fano matroid. *The eight-point matroid of a
square antiprism In geometry, the square antiprism is the second in an infinite family of antiprisms formed by an even number, even-numbered sequence of triangle sides closed by two polygon caps. It is also known as an ''anticube''. If all its faces are regular ...
. *The matroid obtained by relaxing the unique pair of disjoint circuit-hyperplanes of the square antiprism. This result won the 2003
Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...
for its authors Jim Geelen, A. M. H. Gerards, and A. Kapoor. For GF(5), several forbidden minors on up to 12 elements are known, but it is not known whether the list is complete.


Reported proof

Geoff Whittle announced during a 2013 visit to the UK that he, Jim Geelen, and Bert Gerards had solved Rota's conjecture. The collaboration involved intense visits where the researchers sat in a room together, all day every day, in front of a whiteboard. It would take them years to write up their research in its entirety and publish it. An outline of the proof appeared 2014 in the ''Notices of the American Mathematical Society''. Only one paper by the same authors, related to this conjecture, has subsequently appeared.


See also

*
Rota's basis conjecture In linear algebra and matroid, matroid theory, Rota's basis conjecture is an unproven conjecture concerning rearrangements of Basis (linear algebra), bases, named after Gian-Carlo Rota. It states that, if ''X'' is either a vector space of dimension ...
, a different conjecture by Rota about linear algebra and matroids


References

{{reflist, colwidth=30em Matroid theory Conjectures