Matroids

How to contact me.
Back to the Graph Theory Index
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r', Transversal Matroid.

Matroids (Notes from a previous class)

There are several definitions of matroids We shall examine some of these with an eye to showing their equivalence. We have in class already seen a few applications, including that fact that matroids are effectively those structures on which greedy algorithms work. To keep the definitions separate, we shall refer to the variants as C-matroids, B-matroids, r-matroids, s-matroids, etc. The theorems will show that we are really talking about the same types of objects.


Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
Definition. An I-matroid is a finite set S and a collection I of subsets of S (called indepedent sets) such that axioms (I1)-(I3) are satisfied.
(I1) { } ∈ I;
(I2) if X ∈ I and Y ⊆ X, then Y ∈ I; and
(I3) if U,V ∈ I with |U| = |V|+1, then there is an x ∈ U \ V such that V ∪ {x} ∈ I.

In class, I gave (I1), (I2), (I3)':
(I3)' if U,V ∈ I with |U| > |V|, then there is an x ∈ U \ V such that V ∪ {x} ∈ I.

It is immediately obvious that (I1), (I2), (I3)' are equivalent to (I1), (I2), (I3). There is a third definition involving
independence.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
The other structure we studied was:

Definition. A G-matroid M=(S,F) is a finite set S and a non-empty collection F of subsets of S satisfying the following two conditions:
(G1) if X ∈ F and Y ⊆X, then Y ∈ F; and
(G2) for any function w from S to the set of non-negative real numbers, the greedy algorithm applied to (F,w) returns a maximum weight element of F.


We showed, in class, that (G1), (G2) are equivalent to (I1), (I2), (I3). Thus we have the following theorem.

Theorem. An I-matroid is a G-matroid, and conversely.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
We now introduce some of the other parameters. A base of a matroid M=(S,I) is a maximal independent set. We use B(M) or B for the set of bases of M.

Definition. A B-matroid M=(S,B) is a finite set S and a non-empty collection of subsets B of S satisfying:
(B1) If B1, B2 ∈ B and x ∈ B1 \ B2, then there is some y ∈ B2 \ B1 such that (B1 \ {x}) ∪ {y} ∈ B.
Theorem. An I-matroid M=(S,I) is a B-matroid.

Proof. For the collection B we use the collection of bases of M. (This is obviously non-empty.)

If B1,B2 ∈ B and x ∈ B1 \ B2, then B1 \ {x} ∈ I and B2 ∈ I and |B1 \ {x}|=|B2| − 1. Hence, by axiom (I3) there is a y ∈ B2 \ (B1\{x}) = B2 \ B1 such that (B1\{x}) ∪ {y} ∈ I. But, |(B1 \ {x}) ∪ {y}|=|B2|. If (B1 \ {x}) ∪ {y} is not maximal, then it is a subset of some base B3 with |B3| > |B2| and an application of (I3) shows that B2 can be augmented, contradicting the maximality of B2. Hence, (B1 \ {x}) ∪ {y} is maximal, and thus (B1 \ {x}) ∪ {y} ∈ B.


Lemma. All bases in a B-matroid have the same cardinality.

Proof.. Let B1,B2 ∈ B with |B1| ≠ |B2|, but, subject to this, with |B1 ∩ B2| as large as possible. Suppose that there is some x ∈ B1 \ B2. Then by (B1) there is an element y ∈ B2 \ B1 such that B3 = (B1 \ {x}) ∪ {y} ∈ B. But, |B3| = |B1| ≠ |B2| and |B3 ∩ B2| > |B1 ∩ B2|, which is a contradiction. Thus, B1 \ B2 = { }. Similarly, B2 \ B1 = { } . Therefore, |B1| = |B2|, contradicting the assumption that |B1| ≠ |B2|.
Theorem. A B-matroid M=(S,I) is an I-matroid.

Proof. We define I in the natural way: I is the collection of all subsets of elements of B. It is obvious that (I1) and (I2) are satisfied, and we need only prove (I3). Let U,V ∈ I with |U| = |V| + 1. Then, U is a subset of some B2 in B and V is a subset of some B1 in B, where we choose |B1 ∩ B2| as large as possible.
If B1=B2, then any y ∈ U \ V will satisfy V ∪ {y} ∈ I.

Thus, we assume that B1 ≠ B2. Let x ∈ B1 \ V. Suppose that x ∉ B2. Then, there is some y ∈ B2 \ B1 such that B3 = (B1 \ {x}) ∪ {y} ∈ B. However, V ⊆ B3, U ⊆ B2 and |B3 ∩ B2| > |B1 ∩ B2|, violating the choice of B1 and B2. Hence, B1 \ V is a subset of B2. Since U ⊆ B2, and |B1| = |B2| (from the Lemma), we derive:

|U ∩ (B1 \ V)| = |U| + |B1 \ V| − |U ∪ (B1 \ V) | ≥ |V| + 1 + |B1 \ V| − |B2| = |B1| + 1 - |B2| = 1.

Let y ∈ U ∩ (B1 \ V) ⊆ U \ V, then V ∪ {y} ⊆ B1 ∈ I. Therefore, (I3) is satisfied and (S,I) is an I-matroid.
Exercise. Let M=(S,I) be an I-matroid. Define B as above. In the proof of the theorem, we constructed another set which we might call I(B). Show that I=I(B), thus the process of converting an I-matroid to a B-matroid and then back to an I-matroid actually returns us to the original matroid. (The reader should do a similar verification for each of the theorems showing equivalency.)
Theorem. Suppose that M=(S,B) is a B-matroid. Then,

(B2) If B1, B2 ∈ B and y ∈ B2 \ B1, then there is an x ∈ B1 \ B2 such that (B1 \ {x}) ∪ {y} ∈ B.

Proof. Since M is a B-matroid, the collection I of subsets of elements of B is the collection of independent sets of an I'-matroid. Therefore {y} ⊆ B2 ∈ I, {y} ∈ I, and since B1 is an independent set, repeated use of axiom (I3)' yields an independent set K with y ∈ K ⊆ B1 ∪ {y}, and with |K| = |B1|. Thus, K must be a maximal independent set, and hence, K is a base. But K = (B1 \ {x}) ∪ {y}, for some x ∈ B1, completing the proof.


Example. We list all of the non-isomorphic matroids on at most 4 elements. We do this by listing the possible choices for B.

Suppose S is the empty set.
Then the only possible base is:
B1={{ }}.

Suppose S={a}.
The choices for B are
(1) B1={{a}} and
(2) B2={{ }}.

Suppose S={a,b}.
The choices for B are
(1) B1={{a,b}},
(2) B2={{a},{b}},
(3) B3={{a}} and
(4) B4={{ }}.

Suppose S={a,b,c}.
The choices for B are
(1) B1={{a,b,c}},
(2) B2={{a,b},{a,c},{b,c}},
(3) B3={{a,b},{a,c},},
(4) B4={{a,b}},
(5) B5={{a},{b},{c},},
(6) B6={{a},{b}},
(7) B7={{a}}, and
(8) B8={{ }}.

Suppose S={a,b,c,d}.
The choices for B are
(1) B1={{a,b,c,d}},
(2) B2={{a,b,c},{a,b,d},{a,c,d},{b,c,d}},
(3) B3={{a,b,c},{a,b,d},{a,c,d}},
(4) B4={{a,b,c},{a,b,d}},
(5) B5={{a,b,c}},
(6) B6={{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}},
(7) B7={{a,b},{a,c},{a,d},{b,c},{b,d}},
(8) B8={{a,c},{a,d},{b,c},{b,d}},
(9) B9={{a,b},{a,c},{b,c}},
(10) B10={{a,b},{a,c},{a,d}},
(11) B11={{a,b},{a,c}},
(12) B12={{a,b}},
(13) B13={{a},{b},{c},{d}},
(14) B14={{a},{b},{c}},
(15) B15={{a},{b}},
(16) B16={{a}}, and
(17) B17={{ }}.
Exercise. Let G be a graph and recall that a forest F of G is an acyclic subgraph of G. Prove that the collection I of edge sets of forests of G is the collection of independent sets of a matroid and that the maximal spanning forests of G are bases of the matroid.
Definition. A B-matroid M=(S,B) is graphic if there exists a graph G with edge set S such that B is the collection of maximal edge sets of G which do not support a cycle of G.
Definition. The dual of a B-matroid M=(S,B) is the structure M*=(S,B*), where B*={S \ X: X ∈ B}. By (B2), M* is, in fact, a matroid. We will also show (later) that the matroid associated with the dual of a planar graph is the dual of the matroid of the graph, thereby justifying the name.
Definition. A cographic matroid is the dual of a graphic matroid.
All of the matroids for |S| < 4 are graphic. For |S| = 4, all but one are graphic. The matroid, U4,2, determined by the sixth basis, B6, in the example, is neither graphic nor cographic. We will also see that a matroid is both graphic and cographic if and only if it is the matroid of a planar graph.

All of the matroids with |S| ≤ 4 are
transversal.
Exercise. Let |S|=n. Let B be a non-empty collection of subsets of S each of cardinality n-1. Prove that (S,B) is a matroid.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
The rank function of a matroid M=(S,I) is a function r from the set of subsets of S to the set of integers, defined by

r(A)=max{|X|:X a subset of A and X in I}, for every subset A of S.

The rank of the matroid M, denoted r(M), is the rank of S.
Definition. An r-matroid M=(S,r) is a finite set S and a function r from the set of subsets of S to the set of integers such that for every subset X of S and every y,z in S, the following three conditions are satisfied:

(R1) r({ })=0;
(R2) r(X) <= r(X union {y}) <= r(X)+1; and
(R3) if r(X union {y})=r(X union {z})=r(X), then r(X union {y,z})=r(X).
Theorem. An I-matroid is an r-matroid.

Proof. We take r(A)=max{|X|:X a subset of A and X in I}, for every subset A of S, as defined previously. Let X be a subset of S and let y,z be elements of S.

(R1): The only independent subset of { } is { }. Therefore, r({ })=0.

(R2): Let U be a subset of X such that U is in I and |U|=r(X). Then U is a subset of X union {y}. Hence, r(X union {y}) >= |U|=r(X). Now let V be a subset of X union {y} such that V is in I and |V|=r(X union {y}). Then V1=V\{y} is a subset of X and V1 is in I. Therefore, r(X)+1 >= |V1| +1 >= |V| = r(X union {y}).

(R3): Suppose that r(X union {y}) = r(X union {z}) = r(X) From (R2), which we have just proved, we know that r(X union {y,z}) >= r(X union {y}) = r(X). Thus, r(X union {y,z}) >= r(X).

Suppose that r(X union {y,z}) > r(X). Let U be a subset of X union {y,z} such that U is in I and |U| = r(X union {y,z}) and let V be a subset of X such that V is in I and |V|=r(X). Then, |U|>|V|. By (I3)', there is an element b in U\V, which is a subset of X union {y,z}, such that V union {b} is in I. However, b is not in X, since this would force V union {b} to be a subset of X, Therefore, b=y or b=z. If b=y, then V union {b} is a subset of X union {y} and |V| + 1 = |V union {b}| <= r(X union {y})=r(X)=|V|. Hence, b cannot be y. Similarly, b cannot be z. This is a contradiction.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
Lemma. Let M=(S,r) be an r-matroid. Let X be a subset of S. Then r(X) <= |X|.

Proof. Let k=|X| and let X={x1,x2,...,xk}. Let X0={ } and Xi={x1,x2,...,xi} for 1 <= i <= k. Then r(X0)=0 and r(Xi) <= r(Xi\{xi})+1 for 1 <= i <= k. It follows, by induction, that r(Xi) <= i. Therefore, r(X) = r(Xk) <= k = |X|.
Lemma. Let M=(S,r) be an r-matroid. Let X be a subset of Y. Then r(X) <= r(Y) <= r(X) + |Y\X|.

Proof. Let k=|Y\X| and let Y\X={x1,x2,...,xk}. Let X0=X and Xi=X union {x1,...,xi} for a <= i <= k. Then r(Xi-1) <= r(Xi) <= r(Xi-1)+1 for a <= i <= k. It follows, by induction, that r(X) <= r(Xi) <= r(X)+i. Therefore, r(X) <= r(Y) <= r(X)+|Y\X|.
Theorem. An r-matroid is an I-matroid.

Proof. Let I={A: A is a subset of S and |A|=r(A)}.

(I1): Since r({ })=0=|{ }|, it follows that { } is in I.

(I2): Let X be in I. Then r(X)=|X|. Suppose that Y is a subset of X but that Y is not in I and, subject to this, assume that Y is as large as possible. Now, X\Y cannot be { }. Let x be an element of X\Y. Then Y union x is in I. Hence, r(Y)+1 < |Y|+1 = |Y union {x}| = r(Y union {x}) =r(Y)+1.

(I3): Let U,V be sets in I with |U|=|V|+1. Suppose that r(V union {y}) = r(V) for every element y of U\V. Let U\V = Y = {y1,y2,...,yk}.

I sketch the remainder of the argument. Prove, inductively, that r(V union Y') = r(V), for each subset Y' of Y. For |Y'|=1, this is just k(k-1)/2 applications of (R3). Now let X be an i-1 element extension of V, the previous inductive step shows that r(X union {y})=r(X union {z})=r(X), for each choice of y,z in Y/X, since these are just i element extensions. By (R3), r(X union {y,z})=r(X). This proves that all i+1 element extensions have rank R(V). But r(V union Y >= r(U) > r(V) provides the contradiction.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
Definition. An r'-matroid M=(S,r') is a finite set S and a function r' from the set of subsets of S to the set of integers such that for every pair of subsets X,Y of S the following three conditions are satisfied.

(R1)' 0 <= r'(X) <= |X|;
(R2)' if X is a subset of Y, then r'(X) <= r'(Y); and
(R3)' r'(X union Y) + r'(X intersect Y) <= r'(X) + r'(Y).


Theorem. An r-matroid M=(S,r) is an r'-matroid.

Proof.

We set r'=r.

(R1)' Previous
Lemma.

(R2)' Previous Lemma.

(R3)' Note that M is an I-matroid, and thus we may also use properties (I1), (I2), (I3). Let X,Y be subsets of S. Choose an independent set U in X intersect Y, such that U is as large as possible. Now, choose an independent set U union V in X, such that U union V is as large as possible. Finally, choose an independent set U union V union W in X union Y, such that U union V union W is as large as possible. Then, r(X intersect Y) = |U|, r(X) = |U union V|, r(X union Y) = |U union V union W|, and r(Y) >= |U union W|.

Therefore, r(Y) >= |U union W| = |U union V union W| + |U| - |U union V| = r(X union Y) + r(X intersect Y) - r(X). This completes the proof.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
A subset A of S is closed or a flat or a subspace of M if for all elements x of S\A, r(A union {x}) = 1+r(A). If x is an element of S and A is a subset of S and r(A union {x}) = r(A) we say that x depends on A and write x ~ A. For a subset A of S, let σ(A) = {x : x ~ A}. We call σ(A) the closure of A.

Definition. A σ-matroid M=(S,σ) is a finite set S and a function σ:2S→2S such that for every pair of subsets X,Y ⊆ S and for every pair of elements x,y ∈ S the following four conditions are satisfied.

(S1) X ⊆ S(X);
(S2) if Y ⊆ X, then σ(Y) ⊆ σ(X);
(S3) σ(X)=σ(σ(X)); and
(S4) if y ∉ σ(X) and y ∈ σ(X ∪ {x}), then x ∈ σ(X ∪ {y}).

Theorem. A σ-matroid is an I-matroid, and conversely.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
Definition. A circuit of a matroid M=(S,r) is a subset of S such that r(X) < |X|, but r(Y)=|Y|, for every subset Y of X.

Definition. A C-matroid M=(S,C) is a finite set S and a collection of subsets C of S such that the following two conditions are satisfied.

(C1) if X and Y are in C and X is a subset of Y, then then X=Y; and
(C2) if X and Y are distinct elements of C and z is an element of X intersect Y, then there exists an element Z in C such that z is not in Z and Z is a subset of X union Y.
Theorem. A C-matroid is an I-matroid, and conversely.


Example (Transversal Matroids). Let G be a bipartite graph with bipartition (X,Y). We say a vertex x ∈ X is saturated by a matching M if x is incident with some edge of M. Let F(M) denote the set of all vertices of X saturated by M. We will call F(M) transversal-independent. Let J denote the set of all transversal-independent subsets of X. It is obvious that (X,J) satisfies axioms (I1) and (I2).

To prove (I3), let A,B ∈ J, with |A| < |B|. As above, let MC be a matching such that F(MC) = C, for C = A,B. Now, let H be the graph with vertex set V(G) and edge set MA ∪ MB. Using one iteration of the standard augmenting-path proof of Hall's theorem, starting with the matching MA, results in a matching M with |M| = |MA| + 1 and with F(M) = F(A) ∪ {f}, for some f ∈ X − A. But, the only vertices of X with positive degree in H lie in A ∪ B and, hence, f ∈ B − A. Thus, (I3) is satisfied.

Exercise. The reader is invited to verify that all matroids on five or fewer elements are transversal-matroids.

Exercise. Find a matroid that is not a transversal-matroid. (Hint: the number of elements is not less than six.)

Exercise. Find a matroid that is neither a graphic matroid nor a transversal-matroid.

For the next result, N(Z) denotes the set of neighbours of Z in the graph under discussion. The sequence of Lemmas is suggested in the text by Gordon and McNulty. (I'm neither looking up original sources, nor claiming that their proof is not original.)

Lemma. Let M=(X,I) be a transversal matroid derived from the bipartite graph G with bipartition (X,Y). Suppose that C is a circuit of M. Then, |N(C)| = |C| − 1 = r(C).

Proof. (We already know that r(C) = |C| − 1.) If Z ⊆ C and Z ≠ C, then Z is independent and there is a matching of G saturating Z. Hence, |N(Z)| ≥ |Z|. The special case |C \ Z| = 1 yields |N(C)| ≥ |N(Z)| ≥ |Z| = |C| − 1. On the other hand, if |N(C)| ≥ |C| as well, then the subgraph G' of G induced by C ∪ Y would satisfy the conditions of Hall's theorem, G' would have a matching saturating C, and that matching would saturate C in G. Thus, |N(C)| ≤ |C| − 1 and, hence, |N(C)| = |C| − 1.

Lemma. Let M=(X,I) be a transversal matroid derived from the bipartite graph G with bipartition (X,Y). Suppose that B is a base of M. Let F be a matching of G saturating B, and let W denote the set of vertices of Y saturated by F. Then, for any x ∈ X \ B, N(x) ⊆ W.

Proof. Let C be a circuit in B ∪ {x}. Note that x ∈ C. Let F' be the subset of F saturating C \ {x} and let Z denote the set of vertices of Y saturated by F'. Hence, N(C) ⊇ N(C \ {x}) ⊇ Z. Thus, |C| − 1 = |N(C)| ≥ |N(C \ {x})| ≥ |Z| = |C| − 1. This forces N(x) ⊆ N(C) = N(C \ {x}) = Z ⊆ W.

Lemma. Let M=(X,I) be a transversal matroid derived from the bipartite graph G with bipartition (X,Y). Suppose that M has no coloops (isthmuses) and that B is a base of M. Let F be a matching of G saturating B, and let W denote the set of vertices of Y saturated by F. Then, for any x ∈ B, N(x) ⊆ W.

Proof. Since x is not a coloop, x is in some circuit C of M. We may assume that we have chosen C so that |C \ B| is as as small as possible.

Let x' ∈ C \ B. Then, B ∪ {x'} contains a circuit C'. If x ∈ C', then |C' \ B| = and we have the circuit we want. So, suppose that x ∉ C'. Now, x' ∈ C ∩ C' and x ∉ C'. By an extension of (C2), there is a circuit C'' ⊆ (C ∩ C') \ {x'} with x ∈ C''. But, C \ B ⊆ (C \ B) \ {x'}, violating the choice of C. Hence, x is in a basic (fundamental) circuit C of M, with respect to the base B. That is, C ⊆ B ∪ {x'}, |N(C)| = |C| − 1, and C \ {x} is independent. Let F' be the subset of F saturating C \ {x'} and let W' denote the subset of Y saturated by F'. But now, N(x) ⊆ N(C − {x'}) ⊆ W' ⊆ W.

Lemma. Let M=(X,I) be a transversal matroid derived from the bipartite graph G with bipartition (X,Y). Suppose that M has no coloops (isthmuses) and that B is a base of M. Let F be a matching of G saturating B, and let W denote the set of vertices of Y saturated by F. Then, for any x ∈ X, N(x) ⊆ W. Thus, N(X) = W, and |N(X)| = |W| = r(X).

Proof. See the two previous lemmata.

Theorem. Let M=(X,I) be a transversal matroid. There is some bipartite graph G with bipartition (X,Y), where |Y| = r(X), such that the transversal matroid of G is M.

Proof. If M has no coloops, this is the result of the previous lemma. Any representation has |Y| = r(X).

If M has coloops, delete them. Find any representation of the new transversal matroid, and add back one disjoint copy of K2 for each coloop of M.




Edmonds-Fulkerson Matching Matroids. Let G be a graph. Let T denote the set of matchings of G. For a matching F, let VF denote the set of vertices saturated by F. Let S = V(G) and let I = {K ⊆ VF : F ∈ T}. Then, M(S,I) is a matroid.

Before starting the proof, we give a definition of matroid favoured by Edmonds.

Definition. An I"-matroid M=(S,I) is a finite set S and a collection of independent subsets I of S satisfying the following three conditions:

(I1) { } ∈ I;
(I2) if X ⊆ Y and Y ∈ I, then X ∈ I; and
(I3)" for every A ⊆ S, all maximal independent subsets of A have the same cardinality.

This is equivalent to the standard definition of a matroid in terms of independent sets.
Proof of equivalence.

Proof that the Edmonds-Fulkerson matching matroid is a matroid. Properties (I1) and (I2) are trivially satisfied.

To prove (I3)", let A ⊆ S and let X,Y be maximal independent subsets of A. For any Z ⊆ S, let FZ denote a matching that saturates the vertices of Z, and possible other vertices as well. Consider the subgraph N of G with V(N) = V(G) and E(N) = FX Δ FY. Then, N is a disjoint union of paths and even cycles. The endvertices of the paths in Nwhich are also vertices of A is the set X Δ Y. Suppose that |X| > |Y|. Then, |X \ Y| > |Y \ X|. Thus, there is a path P in N with one end v in X \ Y and the other end not in Y \ X. Let K = FY Δ E(P). Then, K is a matching which saturates Y ∪ {v} ⊆ A, violating the choice of Y. Hence, |X| ≤ |Y|. Similarly, |Y| ≤ |X| and , |X| = |Y|, proving (I3)".




Representable Matroids. A matroid M(S,I) is representable if there is a field F, a matrix A with entries from F, with M'(S',I') the matroid determined by the columns of A under linear independence, and a bijection f:S→S' such that X ∈ I ⇔ f(X) ∈ I'.

For example, if G is an undirected graph, then the circuit matroid of G is representable, since the incidence matrix of G (with each loop represented by a column of zeroes) is a matrix A over the field of two elements, with a set of columns of A independent preceisely when the corresponding set of edges is independent in the circuit matroid.

A more interesting example is provided by transversal matroids.

Lemma. Suppose that A is an n × m matrix with entries from a field F with |F| ≥ n + 1 and with at least one non-zero entry in each row of A. Then, there is a vector Z=(z1,...,zm) ∈ Fm such that every entry of AZ is non-zero.

Proof. Denote the entry in row i, column of A by ai,j. We proceed iteratively. At each stage, Z(k) will be a vector such that AZ(k) has a non-zero entry in every entry corresponding to a row with a non-zero entry in one of the first k columns. We may start with any Z(0), but for definiteness, let us start with Z(0) = (0,...,0).

Given Z(k-1), we contruct Z(k) by replacing the element in position k of Z(k-1) by a variable zkF. Now, AZ(k) = W + zkQ, for some vectors W,Q ∈ Fm. Let wi denote the ith coördinate of W + zkQ. Note that if ai,k = 0, then the value of wi does not depend of zk. On the other hand, if ai,k ≠ 0, then we need to avoid the one value of zk which would make wi = 0. This imposes at most n forbidden values for zk. But, |F| ≥ n + 1. Hence, there is a choice for zk so that for every i, 1 ≤ i ≤ n, wi ≠ 0 if ai,j ≠ 0. Arbitrarily pick one of these allowable values for zk, and then Z(k) has the desired property.

Proof that Transversal Matroids are Representable. Let M be a transversal matroid and let G be a bipartite graph, with bipartition (X,Y) whose transversal matroid (on the set X) is isomorphic to M. Arbitrarily order the elements of X and Y and let A = (ai,j) be the |Y| × |X| matrix such that ai,j = 0 if there is no edge from yi to xj and ai,j = zi,j if there is an edge from yi to xj, where zi,jF is a variable whose value is to be determined later.

We now assign the values for the variables zi,j beginning with those in column one, and proceeding from one column to the next.

Assume the values for zi,j have been set for each column j, j < k. Let K ⊆ X such that k ∈ K ⊆ {1,2,...,k} and let R = {xj : j ∈ K}. If R is a minimal dependent set in M, then |N(R)| = |R| − 1 and the submatrix of A consisting of the columns indexed by K has |R| columns and at most |R| − 1 non-zero rows. Thus, the columns indexed by K are dependent as vectors with entries in any field. If R is an independent set in M, then the set of columns R' indexed by K' = K \ {k} is independent. Some |R'| × |R'| submatrix of A in the columns indexed by K' has non-zero determinant over F. Hence, by column expansion, some |R| × |R| submatrix T of the columns indexed by K has determinant of T equal to a linear combination of the variables z1,k,z2,k,...,z|Y|,k, with at least one of the coefficients non-zero. We obtain one such linear combination for each independent set containing xk, (and no xj with j > k) and there can be at most 2k−1 such sets. By the lemma, there is a choice for z1,k,z2,k,...,z|Y|,kF, for k ≤ n if |F| > 2n−1. Hence, any transversal matroid is representable with respect to any sufficiently large field.

The Edmonds-Fulkerson matching matroids are transversal matroids and are therefore representable. (The following gives you the main ideas from the Edonds-Fulkerson paper.)

The following theorem, which we state without proof, is a generalization of Tutte's perfect matching theorem.

Edmonds's Matching Structural Theorem (Paths, Trees and Flowers; Transversals and Matroid Partitions). Let G be a graph. Let J denote the set of vertices which are incident with every maximum cardinality matching of G. Let the connected components of G − J be H1,H2,...,Hq. Let U = J ∩ N(V(G) − J). Then, |V(Hi )| = 2ri + 1, for some integer ri, 1 ≤ i ≤ q. Every maximum cardinality matching contains ri edges in Hi, and contains an edge joining u to V(G) − J for every u ∈ Q.

We now construct a bipartite graph B, with bipartition (X,Y), as follows. Let X = V(G). Let Y be the disjoint unions of sets Y1,...Yq,J', where
(i) |Yi| = |V(Hi ) − 1 and each vertex of Hi is adjacent in B to each vertex of Yi
(ii) J' = {a' : a∈ J} and if there is an edge from a to Hi in G, there is an edge from a' to each vertex of Hi in B; and
(iii) if there is no edge from a ∈ J to any Hi in G, there is an edge from a' to a in B.

The bipartite graph B gives us a transversal matroid on X. (We leave it to the reader to convince himself or herself that the transversal matroid is the same as the matching matroid.)

Something in the other direction is also true: a transversal matroid for a graph G with bipartition (X,Y) is a restriction of matching matroid of G to the elements in X.


Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA

Office: Room 237, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
URL: http://www.math.fau.edu/locke/matroid2.htm


Last modified March 19, 2014, by S.C. Locke.