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:

• 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

Examples

• If V is a vector space and M is a 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 definition and properties

A subset of a matroid M is called dependent if it is not independent. A dependent set all of whose 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 L ⊆ N, then r(L) ≤ r(N)
3. 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.

Links and References

• Steven R. Pagano: "Matroids and Signed Graphs", http://www.ms.uky.edu/~pagano/Matridx.htm
• Oxley, James G.: "Matroid Theory", Oxford University Press, New York, 1992
• PlanetMath article on matroids: http://planetmath.org/encyclopedia/Matroid . Contains several other equivalent definitions of matroids.