Binary Matroid Minors

The graph minors project is a sequence of extraordinary theorems proved by Neil Robertson and Paul Seymour in the 1980s. The banner theorem of that project is that every minor-closed family of graphs is characterized by a finite set of excluded minors. The project also has a number of remarkable algorithmic consequences, for example, the membership testing problem can be efficiently solved for any minor-closed class of graphs. Much of the work in the graph minors project goes into proving a technical theorem that constructively characterizes all minor-closed classes of graphs.

The graph minors project can be interpreted in the context of matroid theory by considering the class of graphic matroids. Over the past decade, in joint work with Bert Gerards and Geoff Whittle, we have extended much of the graph minors project from the class of graphic matroids to the class of binary matroids.

This talk will be introductory, no prior knowledge of matroid theory is assumed. We give a broad overview of the results and focus on potential applications to graph theory, coding theory, and quantum computing.

Jim Geelen, University of Waterloo, Canada

Donate · Contact Us · Site Map · Join SIAM · My Account
Facebook Twitter Youtube linkedin google+