Matroid

Matroid

In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of "independence" that generalizes linear independence in vector spaces. 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:

the empty set is independent
every subset of an independent set is independent
if A and B are two independent sets and A has more elements than B, then there exists an element in A which is not in B and when added to B still gives an independent set

Table of contents

1 Examples
2 Further definitions and properties
3 History
4 Links and References

Examples

If V is a vector space and M is any finite subset of V, then M turns into a matroid if we define a subset of M to be independent iff it is linearly independent.
Every finite simple graph G gives rise to a matroid as follows: take as M the set of all edges in G and consider a set of edges independent iff it is not possible to form a simple cycle with them.
Let M be a finite set and k a natural number. M turns into a matroid if we define a subset to be independent iff it has at most k elements.

Further definitions 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 proper 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:

r(N) ≤ |N| for all subsets N of M
if L and N are subsets of M with L ⊆ N, then r(L) ≤ r(N)
for any two subsets L and N of M, we have r(L∪N) + r(L∩N) ≤ 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. One checks easily that M* is indeed a matroid.

History

The matroid concept was introduced by Whitney in 1935 in his paper "On the abstract properties of linear dependence".

Links and References

Steven R. Pagano: Matroids and Signed Graphs

Oxley, James G.: "Matroid Theory", Oxford University Press, New York, 1992

PlanetMath article on matroids. Contains several other equivalent definitions of matroids.

Sandra Kingan: Matroid theory. Lots of links.