Main Page | See live article | Alphabetical index

Matroid

In mathematics and specifically combinatorics, a matroid is a certain structure that captures the essence of "independence", with linear independence in vector spaces being one example. Formally, a matroid is a finite set M together with a collection of some subsets of M (called the independent sets) such that the following properties obtain:

Table of contents
1 Examples
2 Further definition and properties
3 Links and References

Examples

Further definition and properties

A subset of a matroid M is called dependent if it is not independent. A dependent set all of whose proper subsets are independent is called a circuit (with the terminology coming from the graph example above). An independent set all of whose supersets are dependent is called a basis (with the terminology coming from the vector space example above). An important fact is that all bases of a matroid have the same number of elements, called the rank of M. Removing any element from a circuit yields a basis, so all circuits have the same number of elements too, one more than the rank.

In the first example matroid above, a basis is a basis in the sense of linear algebra of the subspace spanned by M. In the second example, a basis is the same as a spanning tree of the graph G. In the third example, a basis is any subsets of M with k elements.

If N is a subset of the matroid M, then N becomes a matroid by considering a subset of N independent if and only if it is independent in M. This allows to talk about the rank of any subset of M.

The rank function r assigns a natural number to every subset of M and has the following properties:

  1. r(N) ≤ |N| for all subsets N of M
  2. if L and N are subsets of M with LN, then r(L) ≤ r(N)
  3. for any two subsets L and N of M, we have r(LN) + r(LN) ≤ r(L) + r(N)

In fact, these three properties can be used as an alternative definition of matroids: the independent sets are then defined as those subsets N of M with r(N) = |N|.

If M is a matroid, we can define the dual matroid M* by taking the same underlying set and calling a set independent in M* if and only if it is contained in the complement of some basis of M.

Links and References