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