2 1. INTRODUCTION Other authors who have studied families of binary matroids with no minors in some subset of {F7, F 7 , M(K3,3), M(K5), M (K3,3), M (K5)} include Wal- ton and Welsh [WW80], who examine the characteristic polynomials of ma- troids in such classes, and Kung [Kun86], who has considered the maximum size obtained by a simple rank-r matroid in one of these classes. Qin and Zhou [QZ04] have characterized the internally 4-connected binary matroids with no minor in {M(K3,3), M(K5), M (K3,3), M (K5)}. Moreover Zhou [Zho08] has also characterized the internally 4-connected binary matroids that have no M(K3,3)-minor, but which do have an M(K5)-minor. Finally we note that the classic result of Hall [Hal43] on graphs with no K3,3-minor leads to a char- acterization of the internally 4-connected binary matroids with no minor in {F7, F7 , M (K3,3), M (K5), M(K3,3)}, and Wagner’s [Wag37] theorem on the graphs with no K5-minor leads to a characterization of the internally 4-connected binary matroids with no minor in {F7, F7 , M (K3,3), M (K5), M(K5)}. The proof of Theorem 1.1 is unusual amongst results in matroid theory, in that we rely upon a computer to check certain facts. All these checks have been carried out using the software package Macek, developed by Petr Hlinˇ en´ y. In addition we have written software, which does not depend upon Macek, to provide us with an independent check of the same facts. The Macek package is available to download, along with supporting documen- tation. The current website is http://www.fi.muni.cz/~hlineny/MACEK. Thus the interested reader is able to download Macek and confirm that it verifies our assertions. Points in the proof where a computer check is required are marked by a marginal symbol and a number. The numbers provide a reference for the web- site of the second author (current url: http://www.maths.uwa.edu.au/~gordon), which contains a more detailed description of the steps taken to verify each asser- tion, and the intermediate data produced during that computer check. We emphasize that none of the computer tests relies upon an exhaustive search of all the matroids of a particular size or rank. The only tasks a program need perform to verify our checks are: determine whether two binary matroids are iso- morphic check whether a binary matroid has a particular minor and, generate all the single-element extensions and coextensions of a binary matroid. Whenever the proof requires a computer check, the text includes a complete description (inde- pendent of any particular piece of software) of the tasks that we ask the computer to perform. Hence a reader who is able to construct software with the capabilities listed above could provide another verification of our assertions. The article is organized as follows: In Chapter 2 we develop the basic definitions and results we will need to prove Theorem 1.1. In Chapter 3 we introduce the obius matroids and consider their properties in detail. Chapter 4 is concerned with showing that a minimal counterexample to Theo- rem 1.1 can be assumed to be vertically 4-connected. This chapter depends heavily upon the Δ-Y operation and its dual we make extensive use of results proved by Oxley, Semple, and Vertigan [OSV00]. The central idea of Chapter 4 is that if a binary matroid M with no M(K3,3)-minor is non-cographic and internally 4-connected but not vertically 4-connected, then by repeatedly performing Y operations, we can produce a vertically 4-connected non-cographic binary matroid
Previous Page Next Page