Matroids and polymatroids

Jack Edmonds’ LTCC intensive course is now over. It differed in several respects from what was advertised. First, he shared the presentation with Alex Fink on a roughly equal basis; second, bimatrix games were shelved in favour of some exciting new developments in the area of matroid subdivision, leading up to a result of Lafforgue, who received a Fields medal for his work on the Langlands program. Seems incredible? Well, while I was at Permutation Patterns last week, Jack and Alex were teaching each other what they needed to know to make an attack on this development, and I hope that exciting things will be forthcoming.

I will give a very brief summary of the course content, leaving a lot out. I am completely unable to capture the complex dynamics between two remarkable mathematicians and speakers, and will not attempt much to tease apart their contributions – you should have been there!

Course material, and much more besides, is available here.

Polymatroids

We are working in n-dimensional real space, with basis indexed by a “ground set” E, which will carry some of the combinatorial structure.

A polymatroid set function is a function f from the power set of E (the set of subsets of E to the set of real numbers (though we often restrict to rationals or even integers) satisfying three conditions:

• f(∅) = 0;
• f is non-decreasing; that is, if A ⊆ B then f(A) ≤ f(B);
• f is submodular; that is, for any two sets A and B, we have f(A∪B)+f(A∩B) ≤ fA)+f(B).

Submodular functions have wide applicability, perhaps partly because the condition means that the utility of a new element e relative to a set B is not more than its utility relative to a proper subset A. In any case, Jack explained how to find the optimum value of a submodular function by reducing it to a polymatroid set function.

A polymatroid set function defines a polyhedron in R^E consisting of those vectors x with non-negative components which satisfy x(A) ≤ f(A), where x(A) means the sum of the coordinates of x lying within the subset A of E.

This polyhedron is defined by exponentially many linear inequalities, which sounds like bad news; but its vertices can be found efficiently by the greedy algorithm (which, as Jack pointed out, was devised by the Czech mathematician Borůvka).

Matroids

There are many ways to define a matroid. Jack was somewhat scathing about books which laboriously prove the equivalence of definitions in terms of independent sets, bases, circuits, hyperplanes, rank function, and so on. I am perhaps guilty, but I think that a couple of definitions I have drawn attention to are rather more suprising.

A matroid here is defined by its rank function. This is a polymatroid set function with two extra properties: its values are non-negative integers; and f(A) ≤ |A| for all subsets A. The independent sets of the matroid are just the sets for which equality holds here.

In the other direction, given any polymatroid set function f, we can define a matroid by the rule that its independent sets are those sets A for which f(S) ≥ |S| for all subsets S of A.

The prototypical example of a matroid is given by a matrix (hence the name): we take E to be a set indexing the columns of the matrix, and a subset A is independent if and only if the corresponding columns are linearly independent.

Jack said that there are three areas of matroid theory in which important work is going on today:

• optimization;
• representability (by a matrix over a field, as above);
• connections with algebraic geometry (touched on below).

Matroid representability over finite fields is the subject of a major piece of work by Geelen, Gerards, and Whittle, which will hopefully be published soon. (According to Geoff Whittle, they have found a path through the wilderness, and need now to construct a decent road so that others can travel that way.)

A matroid rank function is a particular examplel of a polymatroid set function, and so it defines a polytope, sometimes called a matroid polytope. Its vertices are precisely zero-one characteristic vectors of the independent sets of the matroid. For this reason it is sometimes called the independent set polytope of the matroid. Later we will meet another polytope, the base polytope.

Matroid sum

It is clear that the sum of polymatroid set functions is a polymatroid set function. So in particular, if M₁, …, M_r are matroids on the same ground set E, then the sum of their rank functions is a polymatroid set function. By the construction of the preceding section, it gives rise to a matroid, called the matroid sum of the given matroids.

How do we recognise the independent sets of a matroid sum? It turns out that the following two conditions on a set A are equivalent to its independence in the sum, and hence to each other:

• for every subset S of A, f₁(S)+…+f_r(S) ≥ |S|;
• A can be partitioned into subsets A₁, …, A_r such that A_i is independent in M_i for i=1,…,r.

This is the matroid sum theorem or matroid partition theorem. It is an example of what Jack calls a “good characterization”: the second condition provides a short certificate for the independence of A (the partition into independent sets of the matroids), and the first provides a short certificate for its failure (the existence of a set S failing this inequality).

Transversal matroids

Here is a simple application. Let G be a bipartite graph, with r vertices on the left and n on the right. Call a subset of the right vertices independent if it has a matching to the left vertices. These sets are the independent sets of a matroid, called a transversal matroid.

For i=1,…,r, let M_i be the matroid on the right vertices, where the rank of a set is 1 if some right vertex is joined to the ith left vertex. This is a very simple rank 1 matroid; and the transversal matroid defined by the graph is the sum of the matroids M₁, …, M_r.

For this example, the matroid sum theorem reduces precisely to Hall’s marriage theorem.

Another application involves the sum of k copies of the usual graphic matroid of a connected graph G, whose independent sets are the edge sets of forests. The matroid sum theorem gives a condition for a graph to have k edge-disjoint spanning trees, which is a theorem of Nash-Williams.

Matroid intersection

By the intersection of two matroids on a given ground set, we mean the structure given by the subsets which are independent in both matroids. I think this is not in general a matroid, though it is in some special cases. But it does have a remarkable property, the matroid intersection theorem, which states that the intersection of the two matroid polytopes is a polytope whose vertices are just the characteristic vectors of the sets which are independent in both matroids. (This is Jack’s favourite theorem.)

Here is an application. Let G be a connected directed graph on n vertices which has a distinguisued vertex r, the root. A branching of G is a spanning tree in which each edge is directed away from the root. Now branchings are the sets of n−1 edges which are independent in both of the following matroids:

• M₁, the usual graphic matroid of G;
• M₂, the matroid in which the rank of a set is the number of vertices which have an entering edge from the set (note that each vertex other than the root has exactly one entering edge in a branching). (This matroid, incidentally, is the sum of n−1 matroids of rank 1.)

By taking the sums of k copies of each of these matroids, we obtain a test for a directed graph to have k edge-disjoint branchings.

The reason why we cannot expect a nice result for the intersection of three matroids is that, in the above, if we take M₃ to be the matroid where the rank of a set of edges is the number of vertices with an edge of the set leaving the vertex, then a set of n−1 edges independent in all three matroids is precisely a Hamiltonian path; it is difficult to find Hamiltonian paths. So we cannot expect an efficient algorithm.

Matroid subdivision

Here we decompose, not the combinatorial structure, but the polytope associated with a matroid. This does not work for the independent set polytope, since such a polytope contains a neighbourhood of the identity, which cannot be shared among the pieces. So we use the base polytope instead.

I discussed Alex’s favourite example of this here. The base polytope of U_2,4 is an octahedron, whose vertices are indexed by the 2-element subsets of {1,2,3,4} (the bases of the uniform matroid). The kind of subdivision we are interested in corresponds to cutting the octahedron along one of its planes of symmetry to form two square prisms: each is the base polytope of the matroid on 4 points in which all but one pair of points are bases.

Matroid base polytopes are characterised by the conditions that all its vertices are zero-one vectors and any edge is in the direction of the difference between two standard basis vectors. (This is the translate of the exchange property into polytope language.)

One reason why subdivisions are important is that the Tutte polynomial of a matroid is additive over subdivisions.

There is an important class of subdivisions called regular. One of these arises as follows. Add an extra dimension to the space, and “raise” each vertex of the matroid polytope by a certain distance in the extra dimension. Some extra faces have to be added if the function giving the distances is not affine (the polytope will gain extra folds when it is lifted up). Projecting the “lower” faces of the lifted polytope gives a regular subdivision of the original one.

It is not immediately clear that this procedure produces a subdivision; but it turns out that it does. For example, if we fix five vertices of the octahedron and lift the sixth by 1 (in the fourth dimension), we obtain the subdivision into two square pyramids.

Now the remarkable result of Lafforgue, which connects with toric varieties in algebraic geometry and also with the assignment problem, is the following. Consider matroids represented by vectors in a real vector space. There are two operations on the vectors which clearly doesn’t affect the matroid: applying an invertible linear map to the vector space; and scaling the representing vectors by non-zero constants. We say that the representation is deformable if there are continuous motions of the vectors, not a combination of the above types, which preserves the matroid.

Theorem If a matroid represented over the real numbers is deformable, then it has a nontrivial subdivision.

Alex gave us as an example the Desargues matroid, the usual Desargues configuration as a rank 3 matroid where the dependent 3-sets correspond to the lines of the configuration. He showed us how to do the computations by hand or by using software.