Structure in minor-closed classes of matroids
Jim Geelen, Bert Gerards, Geoff Whittle · Cambridge University Press eBooks · 2013
This paper gives an informal introduction to structure theory for minor-closed classes of matroids representable over a fixed finite field. The early sections describe some historical results that give evidence that well-defined structure exists for members of such classes. In later sections we describe the fundamental classes and other features that necessarily appear in structure theory for minorclosed classes of matroids. We conclude with an informal statement of the structure theorem itself. This theorem generalises the Graph Minors Structure Theorem of Robertson and Seymour. Introduction For the last thirteen years we have been involved in a collaborative project to generalise the results of the Graph Minors Project of Robertson and Seymour to matroids representable over finite fields. The banner theorems of the Graph Minors Project are that graphs are well-quasi-ordered under the minor order [34] (that is, in any infinite set of graphs there is one that is isomorphic to a minor of another) and that for each minor-closed class of graphs there is a polynomial-time algorithm for recognising membership of the class [32]. We are well on track to extend these theorems to the class of F-representable matroids for any finite field F. It is important to point out here that day-to-day work along this track does not concern well-quasi-ordering or minor testing. The actual task and true challenge is to gain insight into the structure of members of proper minor-closed classes of graphs or matroids. The well-quasi-ordering and minor-testing results are consequences – not necessarily easy ones – of the structure that is uncovered. Ironically, while one may begin studying structure with the purpose of obtaining marketable results, in the end it is probably the structural theorems themselves that are the most satisfying aspect of a project like this. To acquire that structural insight is the bulk of the work and the theorems that in the end describe the entire structure are the main deliveries of a project like this.