Structure and representability of graphs, matrices and matroids

Project code: Matroid
Research group: Algorithms, Combinatorics and Optimization (PNA1)

Start: 1999-10-17
End: 2011-12-31

Project coordination: Bert Gerards

This is a program of research aimed at extending the results and techniques of the Graph Minors Project of Robertson and Seymour to matrices and matroids.

At the moment the structure of minor-closed classes of matroids over a fixed finite field is investigated. This requires a peculiar synthesis of graphs, topology, connectivity, and algebra.

The structure theory is expected to help in the next stages of the project: proving Rota's conjecture that for every field there are only finitely many excluded minors for representability over that field, and proving Robertson and Seymour's Well-Quasi Ordering Conjecture that for any finite field any infinite list of matroids representable over that field contains to members such that one is a minor of the other.
In addition it is expected the theory will help to find an efficient algorithm for recognizing a fixed minor-closed property over a fixed finite field. 

Cooperation

Jim Geelen (University in Waterloo, Ontario, Canada) and Geoff Whittle (Victoria University, Wellington, New Zealand)