Matroid: Difference between revisions

In combinatorics, a branch of mathematics, a matroid is a structure that captures the essence of a notion of "independence" (hence independence structure) that generalizes linear independence in vector spaces.

There are many equivalent ways to define a matroid, and many concepts within matroid theory have a variety of equivalent formulations. Depending on the sophistication of the concept, it may be nontrivial to show that the different formulations are equivalent, a phenomenon sometimes called cryptomorphism. Significant definitions of matroid include those in terms of independent sets, bases, circuits, closed sets or flats, closure operators, and rank functions.

Matroid theory borrows extensively from the terminology of linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields.

Formal definitions of finite matroids

There are dozens of equivalent ways to define a (finite) matroid. Here are some of the most important. There is no one preferred or customary definition; in that respect, matroids differ from many other mathematical structures, such as groups and topologies.

Independent sets, bases, and circuits

One of the most valuable definitions is that in terms of independence. In this definition a finite matroid M is a pair (E, I), where E is a finite set and I is a collection of subsets of E (called the independent sets) with the following properties:

1. The empty set is independent.
2. Every subset of an independent set is independent. This is sometimes called the hereditary property.
3. 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. This is sometimes called the augmentation property or the independent set exchange property.

The first two properties are simple, but the motivation behind the third property is not obvious. The examples in the example section below will make its motivation clearer.

A subset of E that is not independent is called dependent. A maximal independent set—that is, an independent set which becomes dependent on adding any element of E—is called a basis for the matroid. It is a basic result of matroid theory, directly analogous to a similar theorem of linear algebra, that any two bases of a matroid M have the same number of elements. This number is called the rank of M.

A circuit in a matroid M is minimal dependent subset of E—that is, a dependent set whose proper subsets are all independent. In spite of the similarity to the definition of basis this notion has no analogue in classical linear algebra. The terminology comes from graph theory; see below.

The depedent sets, the bases, and the circuits of a matroid characterize the matroid completely. Furthermore, the collection of dependent sets, or of bases, or of circuits all have simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid M to be a pair (E, B), where E is a finite set as before and B is a collection of subsets of E, called bases, with the following property:

• If A and B are distinct bases of M and a is an element of A not belonging to B, then there exists an element b belonging to B such that B - b + a is a basis. This property is sometimes called the basis exchange property.

Rank functions

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 us to talk about submatroids and 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:

1. r(A) ≤ |A| for all subsets A of E.
2. If A and B are subsets of E with A ⊆ B, then r(A) ≤ r(B).
3. For any two subsets A and B of E, we have r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).

These three properties can be used as one of the alternative definitions of a finite matroid: the independent sets are then defined as those subsets A of E with r(A) = |A|.

Closure operators

Let M be a matroid on a finite set E, defined as above. The closure cl(A) of a subset A of E is the subset of E containing A and every element x in E\A, such that there is a circuit C containing x and contained in the union of A and {x}. This defines the closure operator, from P(E) to P(E), where P denotes the power set.

The closure operator cl from P(E) to P(E) has the following property:

• For all elements a, b of E and all subsets Y, Z of E, if a is in cl(Y ∪ b) \ cl(Y), then b is in cl(Y ∪ a). This is sometimes called the MacLane–Steinitz exchange property.

In fact this may be taken as another definition of matroid -- any closure operator on E with this property determines a matroid on E.

Examples

The uniform matroid

Let E be a finite set and k a natural number. One may define a matroid on E by taking every k-element subset of E to be a basis. This is known as the uniform matroid of rank k.

Matroids from linear algebra

• If E is any finite subset of a vector space V, then we can define a matroid M on E by taking the independent sets of M to be the linearly independent elements in E. Matroids of this kind are called vector matroids or representable matroids.

• A matrix A with entries in a field gives rise to a matroid M on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors. This matroid is called the column matroid of A, and A is said to represent M. Column matroids are just vector matroids under another name, but there are many reasons to favor the matrix representation.

The Fano matroid

Matroids with a small number of elements are often pictured as in the diagram. The dots are the elements of the underlying set, and a curve has been drawn through every circuit. The diagram shows a rank 3 matroid called the Fano matroid, an example that appeared in the original paper of Whitney.

The name arises from the fact that the Fano matroid is the projective plane of order 2, known as the Fano plane, whose coordinate field is the 2-element field. This means the Fano matroid is the vector matroid associated to the seven nonzero vectors in a three-dimensional vector space over a field with two elements.

It is known from projective geometry that the Fano matroid is not a vector matroid associated to any set of vectors in a real or complex vector space.

Matroids from graph theory

Every finite graph or multigraph 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 if and only if it does not contain a simple cycle. Such an edge set is called a forest in graph theory. This is called the cycle matroid or graphic matroid.

Constructions

Let M be a matroid with an underlying set of elements E, and let N be another matroid on underlying set F.

There are some standard ways to make new matroids out of old ones.

• Restriction. If S is a subset of E, the restriction of M to S, written M|S, is the matroid on underlying set S whose independent sets are the independent sets of M that are contained in S. Its circuits are the circuits of M that are contained in S and its rank function is that of M restricted to subsets of S.

• Contraction. If T is a subset of E, the contraction of M by T, written M/T, is the matroid on the underlying set E − T whose rank function is $r'(A)=r(A\cup T)-r(T).$

• Direct sum. The direct sum of M and N is the matroid whose underlying set is the disjoint union of E and F, and whose independent sets are the disjoint unions of an independent set of M with an independent set of N.

• Matroid union. The union of M and N is the matroid whose underlying set is the union (not the disjoint union) of E and F, and whose independent sets are those subsets whose intersections with both E and F are independent. Usually the term "union" is applied when E = F, but that assumption is not essential. If E and F are disjoint, the union is the direct sum.

Further terminology

Let M be a matroid with an underlying set of elements E.

• A subset of E spans M if its closure is E. It spans a closed set K if its closure is K.

• An element that forms a single-element circuit of M is called a loop.

• An element that belongs to no circuit is called a coloop.

• If a two-element set {f, g} is a circuit of M, then f and g are parallel in M.

• M is called simple if no 1- or 2-element subset of E is a circuit.

• A matroid which cannot be written as the direct sum of two nonempty matroids is called connected or irreducible.

• A maximal irreducible submatroid of M is called a component of M.

Matroid duality

If M is a finite matroid, we can define the dual matroid M* by taking the same underlying set and calling a set a basis in M* if and only if its complement is a basis in M. It is not difficult to verify that M* is a matroid and that the dual of M* is M.

The dual can be described equally well in terms of other ways to define a matroid. For instance:

• A set is independent in M* if and only if its complement spans M.

• A set is a circuit of M* if and only if its complement is a coatom in M.

• The rank function of the dual is r*(S) = |E|- r(M) - |S| + r(S).

A main result is the matroid version of Kuratowski's theorem: The dual of a graphic matroid M is a graphic matroid if and only if M is the matroid of a planar graph.

A simpler result is that the dual of a vector matroid representable over a particular field F is also representable over F.

Infinite matroids

The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. One of the difficulties is that there are many reasonable and useful definitions, none of which captures all the important aspects of finite matroid theory. For instance, it seems to be hard to have bases, circuits, and duality together in one notion of infinite matroids.

See also

• Infinite matroid
• Weighted matroid
• Oriented matroid
• Hassler Whitney
• Gian-Carlo Rota

References

• Crapo, H., and Rota, G-C. (1970), On the Foundations of Combinatorial Theory: Combinatorial Geometries. M.I.T. Press, Cambridge, Mass.
• Oxley, J. (1992), Matroid Theory. Oxford University Press, New York. ISBN 0-19-853563-5.
• White, N., ed. (1986), Theory of Matroids. Encyclopedia of Mathematics and its Applications, Vol. 26. Cambridge University Press, Cambridge.
• Whitney, H. (1935), "On the abstract properties of linear dependence". American Journal of Mathematics, vol. 57, pp. 509-533.

External links

• Weisstein, Eric W. "Matroid". MathWorld.
• Matroid at PlanetMath. Contains several other equivalent definitions of matroids.
• A.A. Sapozhenko (2001) [1994], "Matroid", Encyclopedia of Mathematics, EMS Press {{citation}}: Unknown parameter |urlname= ignored (help)
• Steven R. Pagano: Matroids and Signed Graphs.
• Sandra Kingan: Matroid theory. Lots of links.
• Klaus Truemper Matroid decomposition.