III.54 Matroids

Dominic Welsh

The original aim of Hassler Whitney when he introduced the concept of a matroid in 1935 was to produce an abstract notion that would capture the main ingredients of the structure of a set of vectors in a VECTOR SPACE [I.3 §2.3], while avoiding any explicit mention of linear independence.

To do this he singled out two fundamental properties and postulated that any family of subsets that possessed these properties was the collection of “independent sets” of a “matroid.” The first of these properties was an obvious one: any subset of a linearly independent set is also linearly independent. The second property was more subtle: if A and B are two linearly independent sets and B contains more elements than A, then there exists some element of B that is not in A but which, when added to A, gives a set that is still linearly independent. Finally, in order to avoid trivialities he insisted that in every matroid the empty set must be independent.

Thus, formally, a matroid is defined to be a finite set E together with a family of subsets of E which are called the independent sets and which satisfy the following axioms.

  (i) The empty set is independent.

 (ii) Every subset of an independent set is independent.

(iii) If A and B are independent sets, with the number of elements of A being one less than the number of elements of B, then there is some x in B that is not in A such that A ∪ {x} is also independent.

Property (iii) is called the exchange axiom. The most fundamental example of a matroid is a set of vectors in a vector space with the “independent sets” being the usual linearly independent ones: in this case the exchange axiom is known as Steinitz’s exchange lemma. However, there are many examples of matroids that are not subsets of vector spaces.

Figure 1 Two graphs giving rise to the same matroid.

Here, for example, is an important class of matroids that arise from graph theory. A cycle in a graph is a collection of edges of the form (υ₁, υ₂), (υ₂, υ₃), . . . , (υ_k-1, υ_k), (υ_k, υ₁), where the υ_i, are distinct vertices. Take any graph and call a subset of edges “independent” if it contains no cycle.

So here we are thinking of a cycle among the edges as being in some way similar to a linear dependence among some vectors. It is obvious that any subset of an independent set will also not contain a cycle, so condition (it) is satisfied. Slightly less obvious is that if A and B are sets of t and t + 1 edges, respectively, neither containing a cycle, then there will be at least one edge in B but not in A which can be added to A without creating a cycle. So we see that this is another example of a matroid, even though it arises in a very different context from the vector space one.

As it turns out, there is a way of identifying the edges of a graph with a set of vectors in a vector space over the field ₂ of integers mod 2 (see MODULAR ARITHMETIC [III.58]). If G has n vertices and one associates with each vertex a basis element of , then one can associate with each edge the vector that is given by the sum of the basis elements corresponding to its two endpoints. A set of edges will then be independent if and only if the corresponding vectors in are linearly independent. However, as we shall see, there are important examples of matroids that are not even isomorphic to sets of vectors.

Note that the collection of the independent sets (in a graph) conveys part of the information present in the graph, but by no means all of it. For example, consider the graphs G and H in figure 1. As graphs, G and H are distinct, but both give the same matroid on the set {a, b, c, d} (the independent sets are all subsets of size less than or equal to 3, except for {a, b, c}). Note that this matroid is also the same as the matroid formed by the columns of the matrix

However, it turns out that most matroids do not come from either graphs or matrices.

Although a matroid is defined by very simple axioms, many basic results from both linear algebra and graph theory can be extended to the wider setting of matroids. For example, suppose that G is a connected graph. It is not hard to prove that if B is a maximal independent set of the matroid on G, then B is a tree which is incident with every vertex of G. Such a tree is called a spanning tree of G. All spanning trees of a connected graph have the same number of edges, namely, one less than the number of vertices. Similarly, in a vector space, or indeed in any subset of vectors, all maximal linearly independent sets have the same size. Both of these are special cases of the general result that in any matroid all maximal independent sets have the same size. This common size is called the rank of the matroid and, by analogy with vector spaces, a maximal independent set in a matroid is called a basis.

Matroids arise naturally in many parts of mathematics, and they often turn up unexpectedly. For example, consider the minimum connector problem: a company needs to connect a number of cities by links, such as railways or phone cables, and wishes to minimize the total cost. This is clearly equivalent to the following problem. Given a connected graph G, with each edge e having a nonnegative weight (e), find a set of edges that has the minimum total weight but that connects all the vertices of G. It is not hard to see that this problem reduces to finding a spanning tree of minimum weight.

For this there is a classical algorithm. It is the simplest possible algorithm one could imagine for the problem, and it works as follows. Start by choosing an edge of minimum weight, and at each subsequent step add an edge of minimum weight to your chosen set provided that at no stage a cycle is formed.

For example, consider the graph in figure 2. The algorithm would successively select the edges (a, b), (b, c), (d, f), (e, f), (c, d), giving a spanning tree of total weight 1 + 2 + 3 + 5 + 7 = 18. Because of the way it works, the algorithm is known as a greedy algorithm.

At first sight, it seems rather unlikely that this algorithm could work, as it denies the possibility that choosing a suboptimal edge now might have a payoff later. However, it is not hard to show that the algorithm is actually correct. In fact, it extends in almost exactly the same way to matroids in general: what it gives is a (rather fast) algorithm for selecting a basis of minimum weight in a matroid in which each element has a nonnegative weight.

Figure 2 A graph with edge-weights.

Somewhat more surprisingly, matroids are the only structures for which the greedy algorithm works. More precisely, suppose that is a family of subsets of a set E with the property that if A ∈ and B ⊆ A, then B ∈ . Now let be any weight function and suppose that the problem is to select a member B of which has maximum weight, where the weight of a set is just the sum of the weights of its elements. As above, the greedy algorithm starts by choosing an element e of maximum weight and then successively picks elements of maximum weight from the remaining elements subject to the proviso that at each stage, the set of elements chosen is a member of . It turns out that the following is true: the greedy algorithm works on for all weight functions if and only if is the collection of independent sets of a matroid. Thus, matroids form a “natural home” for many optimization problems. Moreover, the concept is genuinely useful, since many of the matroids that arise in such problems are not derived from either vector spaces or graphs.