What are the external triumphs of matroid theory?

Question

As a relatively new abstraction, matroids clearly enjoy a rich theory unto themselves and also offer a viewpoint that suggests interesting analogies and clarifies aspects of the foundations of venerable subjects.

All that said, a very harsh metric by which to judge such an abstraction might ask what important results in other areas reasonably seem to depend in an essential way upon insights first gleaned from the pursuit of the pure theory. So I'd like to know, please, what specific results a matroid theory partisan would likely cite as the best demonstrations of the power of matroid theory within the larger arena of mathematics.

(I realize that mathematicians in one field will sometimes absorb ideas from another field, then translate back to their preferred language possibly obscuring the debt. So important papers that somehow could not exist without matroid theory should count here even if they never explicitly mention matroids.)

Answer 1

Here are two such triumphs. There are many others.

(1) Oriented matroids were used by Gelfand and MacPherson to give a combinatorial formula for Pontrjagin classes, a long-open problem. See http://www.ams.org/journals/bull/1992-26-02/S0273-0979-1992-00282-3/home.html. There have been many further developments in this area.

(2) Quoting from the first sentence of the Math Review 88f:14045, "in this paper the authors discover a remarkable connection between the geometry of the Schubert cells in a Grassmannian manifold, matroid theory, and convex polyhedra." The authors are Gelfand, Goresky, MacPherson, and Serganova. This paper began (I believe) the study of matroid polytopes, which has grown into a big industry.

Answer 2

Many years ago, I learned from Vladimir Arnold that the most important results in mathematics later seem trivial because they become definitions (he gave an example of the Pythagoras theorem and scalar product). You phrased your question very carefully, so as to avoid this pitfall, but there lies your answer. Not only matroid theory was born as an abstraction of basic linear algebra results, its most important contribution is crystallization of what's important and what's possible in neighboring fields. Here is my favorite example.

Mnёv's universality theorem was born as a fundamental result on realization (moduli) spaces of matroids. Mnёv himself used it to prove a delicate theorem on realizations of combinatorial polyhedra. Kapovich and Millson's universality of linkages theorem, Vakil's Murphy's Law, and Belkale-Brosnan (strong) disproof of Kontsevich's conjecture followed. Although some of these results do not explicitly use Mnёv's theorem, it served as an important motivation.

Answer 3

Here is an example from polyhedral theory. A matrix $A \in \mathbb{R}^{n \times m}$ is totally unimodular, if every square submatrix of $A$ has determinant $1, -1,$ or $0$. Totally unimodular matrices are important objects in optimization theory since integer programs can be efficiently solved when the constraint matrix is totally unimodular. That is, if $A$ is a totally unimodular matrix, and $b$ is an integer vector, then the polyhedron

$P:=\lbrace x : Ax \leq b \rbrace$ is integral (the convex hull of the integral points inside $P$ is $P$ itself). This motivates the following important question.

Question: How can one efficiently recognize when a matrix is totally unimodular?

Here's where matroids come in. A matroid is regular if it can be represented over any field. In 1980, Seymour proved a decomposition theorem for regular matroids. Seymour's decomposition theorem states that every regular matroid can be obtained from graphic matroids, cographic matroids, and a specific matroid $R_{10}$ using 1-, 2- and 3- sums. Truemper showed that Seymour's decomposition theorem actually leads to a polynomial-time algorithm for recognizing totally unimodular matrices. Even now, I believe that the only such recognition algorithm uses the decomposition theorem.

Answer 4

A cell complex $K$ is an $m$-obstructor if the subcomplex $K\circledast K$ of the join $K*K$ consisting of the joins of disjoint cells is PL homeomorphic to the $(m+1)$-sphere. Flores (1933) proved that every $m$-obstructor does not embed in $\Bbb R^m$ (this is an easy consequence of the Borsuk-Ulam theorem), and found some $n$-dimensional $2n$-obstructors: the $n$-skeleton $F_n$ of the $(2n+2)$-simplex, and the join $F_0*\dots*F_0$ of $n+1$ copies of the three-point set. Similar arguments show that every $n$-dimensional join of the form $F_{i_1}*\dots*F_{i_k}$ is a $2n$-obstructor (Gruenbaum, 1969).

Using matroids, Sarkaria proved that these joins are the only $2n$-obstructors among all $n$-dimensional simplicial complexes. I wish I could redo this result without matroids, but unfortunately I can't!

The attraction of $n$-dimensional $2n$-obstructors is that while they don't embed in $\Bbb R^{2n}$, all their proper minors (in particular, proper subcomplexes) do. The quest is now to extend Sarkaria's methods to non-simplical complexes, for non-simplicial obstructors are much more interesting than simplicial ones.

Answer 5

Perhaps not the most powerful results, but here are some rather neat and rather recent applications.

Ingleton's inequality relates the ranks of certain combinations of subsets of the ground set. It holds for any representable matroid, but not for all non-representable matroids. For instance, it can be used to show that the Vámos matroid is non-representable.

Ingleton's inequality has found its way into information theory, in the context of Shannon entropy. Here's one example: http://arxiv.org/abs/0905.1519

The Vámos matroid provided a counterexample to a conjecture on sets representable by linear matrix inequalities: http://arxiv.org/abs/1004.1382

The other day, a colleague showed me a rather nice proof of a linear algebra result. The proof used matroid union.

Answer 6

Matroids provide a unified framework for many efficient computer algorithms. For example, finding the maximum-weight element of a matroid can be done with a greedy algorithm and access to a oracle for the matroid. This provides a simple explanation for the Minimum Spanning Tree algorithms.

More advanced matroid algorithms, such as Matroid Intersection, also lead to simple descriptions of efficient algorithms for graph matching, minimum-weight branchings, and other problems.

Answer 7

There are important algorithmic problems, not mentioning matroids at all in their formulations, for which the only polynomial algorithm I know is through matroids.

Here is one. I call a digraph D with a specified root-node r rooted k-connected if there are k openly disjoint paths from r to every other node of D.

Using network flow techniques it is possible to check in polnomial time if a digraph is rooted k-connected or not. Suppose now it is and let c be a cost function on the edge-set of D.

The optimization problem we consider is to construct a minimum cost subgraph of D (on the same node-set) which is rooted k-connected.

Using weighted matroid intersection, this is doable in polynomial time, though the reduction is not straightforward at all.

Here is another example. We are given a connected undirected graph and a stable subset S of its nodes (stable means that S induces no edges). Decide if there is a spanning tree of the graph in which the degree of every node in S is at least 2 but at most 3. (Of course, here any other bounds in place of 2 and 3 can be imposed.) What is a necessary and sufficient condition for the existence and how can you find algorithmically the requested tree, if exists?

There are great many other (hyper)graph optimization problems that can be handled only with matroid optimization.

If it does not sound terribly unmodest, let me call attention to my recent book entitled Connections in Combinatorial Optimization (Oxford University Press) that contains several other applications of matroid theory.

Andras Frank

Answer 8

The notion of NBC-basis from matroid theory was used to give an elegant presentation for the cohomology algebra for the complement of a complex hyperplane arrangement, the `Orlk-Solomon Algebra'.