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).
Previous Page Next Page