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 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 obius matroids form two infinite families of binary
matroids. Each 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 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 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
Previous Page Next Page