Matroids

Base B, Circuit C, Closure s, Greedy G, Independence I, Rank r, Rank r'.

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 s, 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 (I1)-(I3) are satisfied.
(I1) the empty set is in I;
(I2) if X is in I and Y is a subset of X, then Y is in I; and
(I3) if U and V are in I with |U|=|V|+1, then there is an x in U\V such that V union {x} is in I.

In class, I gave (I1), (I2), (I3)':
(I3)' if U and V are in I with |U|>|V|+1, then there is an x in U-V such that V union {x} is in 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 s, 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 is in F and Y is a subset of X, then Y is in 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 s, 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 B₁ and B₂ are in B and x is in B₁\B₂, then there is an element y in B₂\B₁ such that (B₁\{x}) union {y} is in 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. If B₁ and B₂ are in B and x is in B_1\B2, then B₁\{x} is in I and B₂ is in I |B₁\{x}|=|B₂|-1. Hence, by axiom (I3) there is a y in B₂\(B₁\{x}) = B₂\B₁ such that (B₁\{x}) union {y} is in I. But, |(B₁\{x}) union {y}|=|B₂|. If (B₁\{x}) union {y} is not maximal, then it is a subset of some base B₃ with |B₃|>|B₂| and an application of (I3) shows that B₂ can be augmented, contradicting the maximality of B₂. Hence, (B₁\{x}) union {y} is maximal, and thus (B₁\{x}) union {y} is in B.

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

Proof.. Let B₁ and B₂ be elements of B with different cardinalities, but, subject to this, with intersection as large as possible. Suppose that there is some element x in B₁\B₂. Then by (B1) there is an element y in B₂\B₁ such that B₃=(B₁\{x}) union {y} is in B. But, |B₃|=|B₁| is not equal to |B₂| and B₃ intersection B₂ is larger than B₁ intersection B₂, which is a contradiction. Thus, B₁\B₂ is empty. Similarly, B₂\B₁ is empty. Therefore, |B₁|=|B₂|, contradicting the assumption that these two bases have different cardinalities.

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 and V be elements of I with |U|=|V|+1. Then, U is a subset of some B₂ in B and V is a subset of some B₁ in B, where we choose B₁ intersect B₂ as large as possible.
If B₁=B₂, then any y in U\V will satisfy V union {y} in I. (We don't really use this, do we?)
Thus, we assume that B₁ and B₂ are distinct. Let x be an element of B₁\V. Suppose that x is not in B₂. Then, there is an element y in B₂\B₁ such that B₃=(B₁\{x}) union {y} is in B. However, V is a subset of of B₃, U is a subset of B₂ and the intersection of B₃ and B₂ is larger than the intersection of B₁ and B₂, violating the choice of B₁ and B₂. Hence, B₁\V is a subset of B₂. Since U is also a subset of B₂, and |B₁| =|B₂| (from the Lemma), we derive:

|U intersect (B₁\V)| = |U| + |B_1\V| - |U union (B₁\V) | >= |V| + 1 + |B₁\V| - |B₂| = |B₁| + 1 - |B₂| =1.

Let y be an element of U intersect (B₁\V), which is a subset of U\V, then V union {y} is a subset of B₁ and is thus in 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 B₁ and B₂ are in B and y in B₂\B₁, then there is an x is in B₁\B₂ such that (B₁\{x}) union {y} is in 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} is an independent set, and since B₁ is an independent set, repeated use of axiom (I3)' yields an independent set K containing {y} and contained in B₁, with |K| = |B₁|. Thus, K must be a maximal independent set, and hence, K is a base. But K = (B₁\{x}) union {y}, for some element x of B₁, 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:
B₁={ }.

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

Suppose S={a,b}.
The choices for B are
(1) B₁={{a,b}},
(2) B₂={{a},{b}},
(3) B₃={{a}} and
(4) B₄={{ }}.

Suppose S={a,b,c}.
The choices for B are
(1) B₁={{a,b,c}}, (2) B₂={{a,b},{a,c},{b,c}},
(3) B₃={{a,b},{a,c},},
(4) B₄={{a,b}},
(5) B₅={{a},{b},{c},},
(6) B₆={{a},{b}},
(7) B₇={{a}}, and
(8) B₈={{ }}.

Suppose S={a,b,c,d}.
The choices for B are
(1) B₁={{a,b,c,d}},
(2) B₂={{a,b,c},{a,b,d},{a,c,d},{b,c,d}},
(3) B₃={{a,b,c},{a,b,d},{a,c,d}},
(4) B₄={{a,b,c},{a,b,d}},
(5) B₅={{a,b,c}},
(6) B₆={{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}},
(7) B₇={{a,b},{a,c},{a,d},{b,c},{b,d}},
(8) B₈={{a,c},{a,d},{b,c},{b,d}},
(9) B₉={{a,b},{a,c},{b,c}},
(10) B₁₀={{a,b},{a,c},{a,d}},
(11) B₁₁={{a,b},{a,c}},
(12) B₁₂={{a,b}},
(13) B₁₃={{a},{b},{c},{d}},
(14) B₁₄={{a},{b},{c}},
(15) B₁₅={{a},{b}},
(16) B₁₆={{a}}, and
(17) B₁₇={{ }}.

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 in 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, U_4,2, determined by the sixth basis, B₆, 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.

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 s, 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 V₁=V\{y} is a subset of X and V₁ is in I. Therefore, r(X)+1 >= |V₁| +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 s, 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={x₁,x₂,...,x_k}. Let X₀={ } and X_i={x₁,x₂,...,x_i} for 1 <= i <= k. Then r(X₀)=0 and r(X_i) <= r(X_i\{x_i})+1 for 1 <= i <= k. It follows, by induction, that r(X_i) <= i. Therefore, r(X) = r(X_k) <= 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={x₁,x₂,...,x_k}. Let X₀=X and X_i=X union {x₁,...,x_i} for a <= i <= k. Then r(X_i-1) <= r(X_i) <= r(X_i-1)+1 for a <= i <= k. It follows, by induction, that r(X) <= r(X_i) <= 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 = {y₁,y₂,...,y_k}.

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 s, 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 s, 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 s(A) = {x : x ~ A}. We call s(A) the closure of A.

Definition. An s-matroid M=(S,s) is a finite set S and a function s from the subsets of S to the subsets of S such that for every pair of subsets X,Y of S and for every pair of elements x,y in S the following four conditions are satisfied.

(S1) X is a subset of S(X);
(S2) if Y is a subset of X, then s(Y) is a subset of s(X);
(S3) s(X)=s(s(X)); and
(S4) if y is not in s(X) and y is in s(X union {x}), then x is in s(X union {y}).

Theorem. An s-matroid is an I-matroid, and conversely.

Base B, Circuit C, Closure s, 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.

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

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

Last modified February 2, 1996, by S.C. Locke.