Closure Matroids

How to contact me.
Base B, Circuit C, Closure σ, Greedy G, Independence I, Rank r, Rank r'.
Some of the proofs here come from memory, some come more directly from Welsh.
A subset A of S is closed or a flat or a subspace of M if for all elements x ∈ S \ A, r(A ∪ {x}) = 1 + r(A). If x ∈ S and A ⊆ S and r(A ∪ {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 1
. An I-matroid M=(S,I) is an σ-matroid.

Theorem 2. An σ-matroid M=(S,σ) is an I-matroid.

Proof of Theorem 1. For any A ⊆ S, we define σ(A) as above. Note that we have already proven the equivalence of some of the other forms of matroids: in particular, we have a rank function that satisfies both sets of rank axioms.

(S1): If x ∈ X, then r(X ∪{x}) = r(X). Thus x ∈ σ(X), and X ⊆ σ(X).

(S2): Suppose that Y ⊆ X and that y ∈ σ(Y). Suppose that r(X ∪ {y}) > r(X). Let V be an independent subset of Y with |V| = r(Y) Let W be an independent subset of X ∪ {y}, with |W| = r(X ∪ {y}). By (I3)', (repeated, if necessary) there is an independent subset Z of X ∪ {y} such that Z ⊇ V and with |Z| = r(X ∪ {y}). But, y ∈ Z, since |Z| > r(X). This, in turn, implies that V ∪ {y} is independent and, hence, y does not depend on Y. This is a contradiction. Thus, σ(Y) ⊆ σ(X).

Preparation for (S3), part 1: We first prove that if J is a maximal independent subset of X, then σ(J)=σ(X). Since J ⊆ X, applying (S2) shows that σ(J) 7sube; σ(X). Now, let y ∈ σ(X) \ σ(J). Then, r(X ∪ {y}) = r(X) and r(J ∪ {y}) = r(J) + 1. Since r(J ∪ {y}) ≤ r(X ∪ {y}), we have a contradiction.

Preparation for (S3), part 2: We now prove that, for any X ⊆ S, r(X) = r(σ(X)). Suppose r(X) < r(σ(X)). Let J be a maximal independent subset of X. Now, an application of (I3) yields an element z ∈ σ(X) \ X, such that J ∪ {z} is independent. But then, z ∉ σ(J), while we have already seen that σ(J) = σ(X).

(S3): Let X ⊆ S and let J be a maximal independent subset of X. Therefore, r(J)=r(σ(X)) (by part 2) and, therefore, σ(X) = σ(J) = σ(σ(X)) (by part 1).

(S4): Suppose that X ⊆ S, and that x,y ∈ S. Suppose also that y ∈ σ(X ∪ {x}) \ σ(X), but x ∉ σ(X ∪ {y}). Then,

r(X ∪ {y}) = r(X) + 1,
r((X ∪ {x}) ∪ {y}) = r(X ∪ {x}) ≤ r(X) + 1,
r((X ∪ {y}) ∪ {x}) = r(X ∪ {y}) + 1 = r(X) + 2.

This is a contradiction. Therefore (S4) holds.

Proof of theorem 2. We define a set J, and then show that this set is the collection of independent sets of a matroid.

let J = {A ⊆ S : ∀x∈A, x∉ σ(A\{x})}.

(I1): Obviously, { } ∈ J.

(I2): Suppose that A ∈ J, and B ⊆ A, but B ∉ J. Then, B has an element x such that x ∈ σ(B\{x}). But then, by (S2), x ∈ σ(A\{x}), contradicting the assumption that A ∈ J.

Preparation for (I3), part 1: Definition. If X ∈ J, we say that X is J-independent.

Preparation for (I3), part 2: Let A ⊆ S and let X be a maximal J-independent subset of A. Then σ(A)=σ(X).

Proof of part 2. Suppose that A is not a subset of s(X). Then, there is an element a ∈ A\σ(X). Let Y = X ∪{a}. Suppose there is some element x ∈ Y such that x ∈ σ(Y\{x}). Obviously, x ≠ a. Therefore, x ∈ σ(Y \ {x}) = σ((X \ {x}) ∪ {a}), but x ∉ σ(X \ {x}). By (S4), a ∈ σ((X \ {x}) ∪{x}) = s(X). This is a contradiction. Therefore, A ⊆ σ(X).

On the other hand, X ⊆ A. Hence, A ⊆ σ(X) (from the previous paragraph) and, by (S2), σ(X) ⊆ σ(A). Applying (S2) again, σ(A) ⊆ σ(σ(X)) and σ(σ(X)) ⊆ σ(σ(A)). But by (S3), this reduces to σ(A) ⊆ σ(X) and σ(X) ⊆ σ(A). Thus, σ(X) = σ(A).

Preparation for (I3), part 3: If X is J-independent, and Y ⊆ X, Y ≠ X, then σ(Y) ⊆ σ(X), σ(Y) ≠ σ(X).

Proof of part 3. If x ∈ X \ Y, then x ∉ σ(X \ {x}). By (S2), σ(Y) ⊆ σ(X \ {x}). Therefore, x ∈ σ(X) \ σ(Y).

Preparation for (I3), part 4: If a ∈ σ(A), then σ(A ∪ {a}) = σ(A).

Proof of part 4. By (S1), A ⊆ σ(A). Therefore, A ∪ {a} ⊆ σ(A). Applying (S2), σ(A ∪ {a}) ⊆ σ(σ(A)). Applying (S3), σ(A ∪ {a}) ⊆ σ(A). Also, A ⊆ A ∪ {a}, and thus, by (S2), σ(A) ∪ σ(A ∪ {a}). Therefore, σ(A) = σ(A ∪ {a}).

Preparation for (I3), part 5: If A ⊆ S and X,Y are maximal J-independent subsets of A, then |X| =|Y|.

Proof of part 5. Let A ⊆ S and let X,Y be maximal J-independent subsets of A. Suppose that |X| < |Y| and that, subject to this, |X ∩ Y| is maximum. Let y ∈ Y \ X, let Z = Y \ {y} and let D = σ(Z). By parts (2) and (3), D ⊆ σ(A), D ≠ σ(A). Add elements x1,x2,...,xk of X to Z until σ(Z ∪ {x1,x2,...,xk}) = σ(A). This process must stop, with k ≤ |X|, since, by part (2), σ(X)=σ(A).

Now, let Y'=Z ∪ {xk}. Suppose that Y' is not J-independent. Then, for some a ∈ Y', we must have a ∈ σ(Y' \ {a}). Suppose that a = xk. We chose xk such that σ(Z ∪ {x1,x2,...,xk}) = σ(A), but σ(Z ∪ {x1,x2,...,xk-1}) ≠ σ(A). Therefore, by part (4) and (S2), xk ∉ σ(Z ∪ {x1,x2,...,xk-1}), and hence, by (S2), xk ∉ σ(Z). Thus, a ≠ xk.

Now, suppose a = w, for some w ∈ Z. Thus, w ∈ σ((Z \ {w}) ∪ {xk}). But, Z is J-independent, and therefore, w ∉ Z \ {w}. Hence, by (S4), xk ∈ σ ((Z \ {w}) ∪ {w}) = σ(Z) = σ(Y \ {y}), which was already shown to be impossible.

Therefore, Y' is J-independent and, since xk ∈ Y' \ Y, |Y'X| gt; |YX|, contradicting the choice of X and Y. Thus, |X| = |Y|.

(I3): Let X and Y be J-independent sets, with |Y| = |X| + 1. Let A = X ∪ Y. Since, by part 5, all maximum J-independent subsets of A must have the same cardinality, X cannot be maximal. Therefore, there is some maximal J-independent subset, Z, such that X ⊆ Z, x ≠ Z. Let x ∈ Z \ X. Then, by (I2), which have already proven, X ∪ {x} is J-independent.

A note before we depart this file: there is a third way to state matroid independence axioms:

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.

We have just seen that an I"-matroid is an I-matroid. The converse is easy.

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

Office: Room 237, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436

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