# What are the external triumphs of matroid theory?

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.)

-
Subjective? Argumentative? –  Igor Rivin May 3 '11 at 20:46
>Subjective? Argumentative? I have at least attempted to couch the question in a way to avoid those issues. I just want examples of results or papers...and I ask for all answer to be cast as making the best possible case for the value of studying the subject. That should avoid argument. The value of a result unavoidably has a subjective component, but consensus may emerge, and the question of whether a result in one area depends upon a result in another seems reasonable objective. The information I seek will help me in the classroom. –  David Feldman May 3 '11 at 21:11
Well: matroid theory surely has achieved a remarkable number of equivalent yet completely different definitions! :) Didn't the word cryptomorphism get invented with matroid theory in mind? –  Mariano Suárez-Alvarez May 3 '11 at 21:31
@darji: Yes, see my answer here. mathoverflow.net/questions/5357/… –  Tony Huynh May 3 '11 at 22:38
Not subjective; not argumentative. Can we move these types of discussions to a parallel posting or something? It always detracts from the math. –  Dr Shello May 4 '11 at 1:59

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.

-
Indeed. The decomposition of matroid polytopes figures prominently in the work of (Fields Medalist) Laurent Lafforgue. –  Timothy Chow May 7 '11 at 17:46
What is "Surgery on the Grassmanians" all about? Is there some paper in english discussing these results? –  Alfredo Hubard Oct 8 '11 at 18:53

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.

-
I am a bit too young to truly appreciate it, but my understanding was that Mnëv's result had instantly reconfigured the landscape in terms of certain discrete math conjectures. –  Thierry Zell May 4 '11 at 23:28

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.

-

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.

-

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.

-

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.

-
@fan: want to share the linear algebra result? At least the statement? –  Thierry Zell May 7 '11 at 15:35
Since it was a work in progress, I think I'd better leave it to them. –  fan May 7 '11 at 22:04
Oh, you mean a new linear algebra result! Or is it just a new proof of an old result? –  Thierry Zell May 8 '11 at 0:16
Can you share it now...? –  Felix Goldberg Mar 28 at 20:57

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.For some details see: