Circuit Matroids

How to contact me.
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.
Theorem 1
.An r'-matroid M=(S,r') is a C-matroid.

Theorem 2. A C-matroid M=(S,C) is an I-matroid.

Proof of Theorem 1. Call A an r'-circuit if r'(A) < |A| and r'(B) = |B| for every subset B of A. Let C' be the set of r'-circuits.

(C1): Suppose that A and B is a proper subset of A. Then, by definition, r'(B) = |B|, and B is not an r'-circuit.

(C2): Let A and B be distinct r'-circuits, and suppose that x is an element of A union B.

Therefore, r'(A) = |A| - 1, and r'(B) = |B| - 1. By (C1), r'(A intersect B) = |A intersect B|.

By (R3)', r'((A union B)\{x}) < r'(A union B) <= r'(A) + r'(B) - r'(A intersect B) = (|A|-1) + (|B|-1) - |A intersect B| = |A union B| - 2 < |(A union B)\{x}|.

Therefore, (A union B)\{x} must contain a circuit.
Proof of Theorem 2. Call a subset J of S C-independent, if J contains no circuit.

(I1): { } can contain no circuit, since every circuit must be non-empty.

(I2): Suppose that Y is C-independent and that X is a subset of Y. Any circuit contained in X is contained in Y. Thus, X is C-independent.

Preparation for (I3), part 1. If X is C-independent and y is an element of S, then X union {y} contains at most one circuit.

Proof of part 1. Suppose that A and B are two circuits contained in X union {y}. Then, y is an element of X intersect {y}. Therefore, by (C2), there is a circuit in (A union B)\{y}, which is a subset of X. This contradicts the choice of X as C-independent.

(I3): Suppose that X and Y are C-independent and that |Y| = |X| + 1. Suppose also that X union {y} is not C-independent, for every element y in Y but that, subject to this, |X\Y| is as small as possible.

If X\Y = { }, then X union {y} is a subset of Y, for any element y of Y\X. Thus, |X\Y| > 0.

By part 1, there is a unique cycle C(y) in X union {y} for each element y in Y.

Pick one particular element w in Y\X, and pick an element z in C(y)\{w}. For any circuit C(y), with y an element of (Y\x)\{w}, construct a circuit D(y) as follows:

if z is not an element of C(y), then D(y) = C(y); and

if z is an element of C(y), then D(y) is a circuit contained in (C(y) union C(w))\{z}.

Now set X' = (X union {w})\{z}. Then |X'| = |X| = |Y| - 1, X' contains no circuit, and for every element y of Y\X', there is a cycle contained in X' union {y}. But |X'\Y| = | X\Y| -1, contradicting the choice of X and Y.
Department of Mathematics
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991

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

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