Branch width and well-quasi-ordering in matroids and graphs
by
Geoff Whittle
Victoria University of Wellington
Coauthors: Jim Geelen (Waterloo, Ontario), Bert Gerards (CWI Amsterdam)

As the culmination of a long series of difficult papers Robertson and Seymour prove the following fundamental theorem: Ïn any infinite set of graphs there is one that is a minor of another." In other words they prove that graphs are well-quasi-ordered. An important step in the proof is to show that graphs with bounded tree width are well-quasi-ordered. In this talk we consider an extension of the result to matroids. While tree width does not extend to matroids, "branch width" does. We prove that the matroids representable over a fixed finite field with bounded branch width are well-quasi-ordered. We also give a short direct proof that the graphs with bounded branch width are well-quasi-ordered. Because of the strong relationship between branch width and tree width, this gives a straightforward proof of Robertson and Seymour's result for graphs of bounded tree width.

Date received: August 9, 2000