From Wikipedia, the free encyclopedia.
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
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)
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.
The matroid concept was introduced by Whitney in 1935 in his paper "On the abstract properties of linear dependence".
History
Links and References
