Introduction To Matroids And Transversal Theory

Introduction to Matroid: A matroids M consists of a non-empty finite set E and a non-empty collection B of subsets of E, called bases satisfying the following properties

B(i) no base properly contains another base
B(ii) if B1 and B2 are bases and if e is any element of B1 then there is an element f of B2 such that (B1 – {e}) ∪ {f} is also a base.

Note : Any two bases of a matroid M have the same number of elements, this number is called the rank of M.

The idea of a matroid, first studied in 1935 in a pioneering paper by Hassler Whitney. A matroid is a set with an independence structure.
We defined a spanning tree in a connected graph G to be a connected subgraph of G that contains no cycles and includes every vertex of G. We note that a spanning tree cannot contain another spanning tree as a proper subgraph.

Note : (i) If B1 and B2 are spanning trees of G and e is an edge of B1 then there is an edge f in B2 such that (B1 – {e}) ∪ {f} is also a spanning tree of G.
(ii) If V is a vector space and if B1 and B2 are bases of B and e is an element of B1 then we can find an element f of B2 such that (B1 – {e}) ∪ {f} is also a basis of V.
Cycle Matroid: A matroid can be associated with any graph G by letting E be the set of edges of G and taking as bases the edges of the spanning forests of G, this matroid is called the cycle matroid of G and is denoted by M(G).

Vector Metroid: If E is a finite set of vectors in a vector space V, then we can define a matroid on E by taking as bases all linearly independent subsets of E that span the same subspace as E. A matroid obtained in this way is called a vector matroid.

Independent (Metroid) Sets: A subset of E is independent if it is contained in some base of the matroid M.
(i) for a vector matroid, a subset of E is independent whenever its elements are linearly independent as vectors in the vector space.

(ii) for the cycle matroid, M(G) of a graph G, the independent sets are those sets of edges of G that contain no cycle. i.e., the edge sets of the forests contained in G.
Since the bases of M are maximal independent sets, a matroid is uniquely defined by specifying its independent sets.

Matroid (Modified Definition): A matroid M consists of a non-empty finite set E and a non-empty collection I of subsets of E, called independent sets, satisfying the following properties :
I(i) any subset of an independent set is independent
I(ii) if I and J are independent sets with | J | > | I | then there is an element e, contained in J but not in I such that I ∪ {e} is independent.

Note : (i) A base is defined to be a maximal independent set.
(ii) Any independent set can be extended to a base.

Dependent (Metroid) Sets
If M = (E, I) is a matroid defined in terms of its independent sets then a subset of E is dependent
if it is not independent and a minimal dependent set is called a cycle.
If M(G) is the cycle matroid of a graph G then the cycles of M(G) are precisely the cycles of G.
Since a subset of E is independent if and only if it contains no cycles, a matroid can be defined in terms of its cycles.

Rank of A
If M = (E, I) is a matroid defined in terms of its independent sets and if A is a subset of E then the rank of A denoted by r(A), is the size of the largest independent set contained in A.
We note that the rank of M is equal to r(E) since a subset A of E is independent if and only if r(A) = | A |.

Note : We can define a matroid in terms of its rank function.