What are Matroids?

Matroids were introduced by Whitney in 1935 to capture abstractly the essence of dependence. Whitney’s definition embraces a surprising diversity of combinatorial structures.

A matroid consists of a pair (E; I) where E is a finite set called ground set and I is a collection of the subsets of E called independent sets such that

• the empty set is independent,

•  subsets of independent sets are independent,

•  for each X, a proper subset of E, the maximal independent subsets of X all have the same cardinality.

Consider the canonical example. Let A be a matrix over a fi eld, F, and let E be the set of column indices of A. The column matroid, denoted M(A), is the pair (E; I). A matroid is called F-representable if it is the column matroid of a matrix over the fi eld F.
The basis is the maximal independent set and the rank of a set X in a matroid

M = (E; I)

denoted r_{M}(X), is the size of the a maximal independent subset of X.