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