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.
(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
such that U union V is as large as possible.
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|.