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(AB)+f(AB) ≤ 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 RE 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 M1, …, Mr 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, f1(S)+…+fr(S) ≥ |S|;
  • A can be partitioned into subsets A1, …, Ar such that Ai is independent in Mi 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 Mi 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 M1, …, Mr.

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:

  • M1, the usual graphic matroid of G;
  • M2, 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 M3 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 U2,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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, exposition and tagged , , , , , , , , . Bookmark the permalink.

4 Responses to Matroids and polymatroids

  1. Gordon Royle says:

    A couple of questions/comments: firstly, in the matroid sum section, you observe that the sum of matroid rank functions yields a polymatroid rank function, and then allude to a result “in the preceding section” that gives a matroid, which is the matroid sum. But I can’t see exactly where this is described?

    Secondly, I think Jack is being unduly harsh on books that “laboriously prove the equivalence” of all the different ways of defining matroids. It may not be his (Jack’s) style, but I still think it is amazing that no matter which aspect of a vector space you try to axiomatise combinatorially (I.e no fields allowed) you end up with exactly the same class of structures. Given this, the author of a definitive introduction to matroids (i.e James) has no choice but to prove these things, laboriously or otherwise. In my opinion, it’s a bit like criticising the author of a Linear Algebra text for showing that “0 is unique” follows from the axioms – it’s not much fun, but somebody has to do it!

    • Thanks for the comments, Gordon. I was not at all sure what sort of job I made of this. I was feeling quite unwell, my computer had crashed and I had only just re-installed the operating system and not yet downloaded my files, and I was trying to do it from memory and rough notes of what Jack said without too much distortion. I know there are a couple of places where I wasn’t as clear as I might have been.

      The construction of a matroid from a polymatroid set function is in the paragraph beginning “In the other direction”.

      As to Jack’s comments on matroid theory books, he was very emphatic about that and I felt I couldn’t just pass over it in silence. I hope my ambivalence comes across. But I agree that someone has to do it. Indeed, although Jack’s examples tend to come from vector matroids, he said, more strongly than I would have done, that matroid terminology all derives from graphic matroids.

      I don’t think I made as good a job of describing the stuff about matroid subdivisions as I might have done. Both Jack and Alex were very excited about this, and both thanked me for my role as matchmaker at least, if not midwife. But Alex can certainly explain this better than I can. His notes will be (if they are not already) among the course material and are well worth looking at. He might even be tempted to write something for posting here …

      • Jack Edmonds says:

        Sorry guys.
        I do not mean to be harsh or ” somewhat scathing about books which laboriously prove the equivalence of definitions in terms of independent sets, bases, circuits, hyperplanes, rank function, and so on.”
        To the contrary I do that and like it.

        I am somewhat harsh about avoiding the extraordinarily useful tool of polyhedra, i.e., linear programming, i.e., theory of systems of linear inequalities.
        To me the word ‘scathing’ is somewhat harsh.

        I suppose I feel scathing about the semantics of ZFC as a supposed foundation of mathematics. I do not believe mathematics is done by manipulation of words but it is perhaps a formal foundation, as suggested by Turing.

        I appreciate the suggestion by Ferdinand Ihringer of work by Paul Lorenzen about a constructivism which sounds good. I would like to learn more about it, perhaps at my email: jack.n2m2m6@gmail.com.

  2. Dear Jack, thanks for your comments. I accept the blame for mis-representing you and happily accept the clarification. I am well aware that you feel more strongly about ZFC than about matroid axioms!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s