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 M on a finite set E is a pair (E, I), where I is a collection of subsets of E (called the independent sets) with the following properties:
- 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 E is any finite subset of a vector space V, then we can define a matroid M on E by taking the linearly independent elements in E to be the independent sets of M.
- Every finite simple graph G gives rise to a matroid as follows: take as E 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 E be a finite set and k a natural number. The subsets of E with at most k elements are the independent sets of a matroid on E.
Further definitions and properties
A subset of E 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). Hence bases are independent sets which cannot increase further while being indepedent (maximal independent sets), and circuits are dependent sets which cannot decrease and still being dependent (minimal dependent sets). An important fact is that all bases of a matroid have the same number of elements, called the rank of M. In general, the circuits of M have different sizes.
In the first example matroid above, a basis is a basis in the sense of linear algebra of the subspace spanned by E, and a circuit is a minimal set of dependent vectors of E. In the second example, a basis is the same as a spanning tree of the graph G, and circuits are cycles in the graph. In the third example, a basis is any subset of E with k elements, and a circuit is any subset of k + 1 elements.
If A is a subset of E, then a matroid on A can be defined by considering a subset of A independent if and only if it is independent in M. This allows to talk about the rank of any subset of E.
The rank function r assigns a natural number to every subset of E and has the following properties:
- r(A) ≤ |A| for all subsets A of E
- if A and B are subsets of E with A ⊆ B, then r(A) ≤ r(B)
- for any two subsets A and B of E, we have r(A∪B) + r(A∩B) ≤ r(A) + r(B)
In fact, these three properties can be used as an alternative definition of matroids: the independent sets are then defined as those subsets A of E with r(A) = |A|.
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 Hassler Whitney in 1935 in his paper "On the abstract properties of linear dependence".
See also
Links and references
- Steven R. Pagano:
- Oxley, James G.: "Matroid Theory", Oxford University Press, New York, 1992
- PlanetMath . Contains several other equivalent definitions of matroids.
- Sandra Kingan: . Lots of links.
