CHAPTER 2
Preliminaries
In this chapter we define basic ideas and develop the fundamental tools we will
need to prove our main result. Terminology and notation will generally follow that
of Oxley [Oxl92]. A triangle is a three-element circuit and a triad is a three-element
cocircuit. We denote the simple matroid canonically associated with a matroid M
by si(M), and we similarly denote the canonically associated cosimple matroid by
co(M). Suppose that {M1, . . . , Mt} is a collection of binary matroids. We denote
the class of binary matroids with no minor isomorphic to one of the matroids in
{M1, . . . , Mt} by EX (M1, . . . , Mt).
2.1. Connectivity
Suppose M is a matroid on the ground set E. The function λM , known as
the connectivity function of M, takes subsets of E to non-negative integers. If X
is a subset of E, then λM (X) (or λ(X) where there is no ambiguity) is defined to
be rM (X) + rM (E X) r(M). Note that λ is a symmetric function: that is,
λ(X) = λ(E X). It is well known (and easy to confirm) that the function λM is
submodular, which is to say that λM (X) + λM (Y ) λM (X Y ) + λM (X Y ) for
all subsets X and Y of E(M). Moreover, if N is a minor of M using the subset X,
then λN (X) λM (X).
A k-separation is a partition (X, Y ) of E such that min{|X|, |Y |} k and
λ(X) = λ(Y ) k. The subset X E is a k-separator if (X, E X) is a k-separa-
tion. (Note that this definition of k-separators differs from that used in [OSW04].)
A k-separation (X, Y ) is exact if λ(X) = λ(Y ) = k 1. A vertical k-separation is
a k-separation (X, Y ) such that min{r(X), r(Y )} k, and a subset X E is a
vertical k-separator if (X, E X) is a vertical k-separation.
A matroid is n-connected if it has no k-separations where k n. It is vertically
n-connected if it has no vertical k-separations where k n. It is (n, k)-connected
if it is (n 1)-connected and whenever (X, Y ) is an (n 1)-separation, then either
|X| k or |Y | k.
In addition, we shall say that a matroid M is almost vertically 4-connected if
it is vertically 3-connected, and whenever (X, Y ) is a vertical 3-separation of M,
then there exists a triad T such that either T X and X clM (T ), or T Y and
Y clM (T ).
We shall use the notion of (n, k)-connectivity only in the case n = 4. A
(4, 3)-connected matroid is internally 4-connected.
The next results collect some easily-confirmed properties of the different types
of connectivity.
Proposition 2.1. (i) A simple binary vertically 4-connected matroid is in-
ternally 4-connected.
5
Previous Page Next Page