2.3. BLOCKING SEQUENCES 7

in B to an element in E(M) − B. If x ∈ B and y ∈ E(M) − B, then x and y

are joined by an edge if and only if x is in the unique circuit contained in B ∪ y.

Equivalently, GB(M) is the bipartite graph represented by the bipartite adjacency

matrix A, where M is represented over GF(2) by the matrix [Ir|A] (assuming that

the columns of Ir are labeled with the elements of B while the columns of A are

labeled by the elements of E(M) − B). Thus a labeled fundamental graph of a

binary matroid completely determines that matroid. By convention, the elements

of B are represented by solid vertices in drawings of GB(M), while the elements of

E(M) − B are represented by hollow vertices.

Suppose that M is a binary matroid on the ground set E and B is a basis of M.

Suppose also that X ⊆ B and Y ⊆ E − B. It is easy to see that the fundamental

graph GB−X (M/X\Y ) is equal to the subgraph of GB(M) induced by E −(X ∪Y ).

If x ∈ B and y ∈ E − B and x and y are adjacent in GB(M), then the funda-

mental graph G(B−x)∪y(M) is obtained by pivoting on the edge xy. In particular,

if

NG(u) = {v ∈ V (G) − u | v is adjacent to u}

is the set of neighbors of u in the graph G, then G(B−x)∪y(M) is obtained from

GB(M) by replacing every edge between NGB

(M)

(x) and NGB

(M)

(y) with a non-

edge, every non-edge between NGB

(M)

(x) and NGB

(M)

(y) with an edge, and then

switching the labels on x and y.

2.3. Blocking sequences

Suppose that B is a basis of the matroid M and let X be a subset of E(M).

Define M[X, B] to be the minor of M on the set X produced by contracting B −X

and deleting E(M) − (B ∪ X). Let X and Y be disjoint subsets of E(M). It is

easy to verify that λM[X∪Y,

B]

(X) is equal to the parameter λB(X, Y ), defined by

Geelen, Gerards, and Kapoor [GGK00].

Suppose (X, Y ) is a k-separation of M[X∪Y, B]. A blocking sequence of (X, Y )

is a sequence e1, . . . , et of elements from E(M) − (X ∪ Y ) such that:

(i) (X, Y ∪ e1) is not a k-separation of M[X ∪ Y ∪ e1, B];

(ii) (X ∪ ei, Y ∪ ei+1) is not a k-separation of M[X ∪ Y ∪ {ei, ei+1}, B] for 1 ≤

i ≤ t − 1;

(iii) (X ∪ et, Y ) is not a k-separation of M[X ∪ Y ∪ et, B]; and,

(iv) no proper subsequence of e1, . . . , et satisfies conditions (i)–(iii).

Blocking sequences were developed by Truemper [Tru86], and by Bouchet,

Cunningham, and Geelen [BCG98]. They were later employed by Geelen, Ger-

ards, and Kapoor in their characterization of the excluded-minors for GF(4)-repre-

sentability [GGK00].

Let (X, Y ) be a k-separation of M[X ∪ Y, B]. We say that (X, Y ) induces a

k-separation of M if there is a k-separation (X , Y ) of M such that X ⊆ X and

Y ⊆ Y .

Lemma 2.8. [GGK00, Theorem 4.14] Suppose that B is a basis of the matroid

M and that (X, Y ) is an exact k-separation of M[X ∪ Y, B]. Then (X, Y ) fails to

induce a k-separation of M if and only if there is a blocking sequence of (X, Y ).

Halfan and Zhou use Proposition 4.15 (i) and (iii) of [GGK00] to prove the

following result ([Hal02, Proposition 4.5 (3)] and [Zho04, Lemma 3.5 (3)] respec-

tively).