# 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.

**Proof**.

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

**Proof**

**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

USA**
Office: Room 286, Science & Engineering**

Phone: (561) 297-3350

Fax: (561) 297-2436

URL: http://www.math.fau.edu/locke/circuit.htm

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