CHAPTER 1

Introduction

The Fano plane, the cycle matroids of the Kuratowski graphs, and their du-

als, are of fundamental importance in the study of binary matroids. The famous

excluded-minor characterizations of Tutte [Tut58] show that the classes of regular,

graphic, and cographic matroids are all obtained by taking the binary matroids

with no minors in some subset of the family

{F7, F7

∗,

M(K3,3), M(K5), M

∗(K3,3),

M

∗(K5)}.

It is natural to consider other classes of binary matroids produced by excluding

some subset of this family. A number of authors have investigated such classes of

binary matroids. We examine the binary matroids with no minor isomorphic to

M(K3,3), and completely characterize the internally 4-connected members of this

class.

Theorem 1.1. An internally 4-connected binary matroid has no M(K3,3)-mi-

nor if and only if it is either:

(i) cographic;

(ii) isomorphic to a triangular or triadic M¨ obius matroid; or,

(iii) isomorphic to one of 18 sporadic matroids of rank at most 11 listed in Appen-

dix B.

The triangular and triadic M¨ obius matroids form two infinite families of binary

matroids. Each M¨ obius matroid is a single-element extension of a cographic ma-

troid; in particular, a single-element extension of the bond matroid of a cubic or

quartic M¨ obius ladder. For every integer r ≥ 3 there is a unique triangular M¨obius

matroid of rank r, denoted by Δr, and for every even integer r ≥ 4 there is a unique

triadic M¨ obius matroid of rank r, denoted by Υr. We describe these matroids in

detail in Chapter 3.

Seymour’s decomposition theorem for regular matroids is one of the most fun-

damental results in matroid theory, and was the first structural decomposition theo-

rem proved for a class of matroids. The following characterization of the internally

4-connected regular matroids is an immediate consequence of the decomposition

theorem.

Theorem 1.2 (Seymour [Sey80]). An internally 4-connected regular matroid

is either graphic, cographic, or isomorphic to a particular sporadic matroid (R10).

Our theorem, and its proof, bears some similarity to Seymour’s theorem. Just

as Seymour’s theorem leads to a polynomial-time algorithm for deciding whether a

binary matroid (represented by a matrix over GF(2)) has a minor isomorphic to F7

or F7 ∗, our characterization leads to a polynomial-time algorithm (to be discussed

in a subsequent article) for deciding whether a represented binary matroid has an

M(K3,3)-minor.

1