What are the external triumphs of matroid theory? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T15:28:06Z http://mathoverflow.net/feeds/question/63847 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory What are the external triumphs of matroid theory? David Feldman 2011-05-03T20:32:26Z 2012-07-07T00:07:29Z <p>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. </p> <p>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.</p> <p>(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.) </p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/63853#63853 Answer by Richard Stanley for What are the external triumphs of matroid theory? Richard Stanley 2011-05-03T21:48:22Z 2011-05-03T21:48:22Z <p>Here are two such triumphs. There are many others.</p> <p>(1) Oriented matroids were used by Gelfand and MacPherson to give a combinatorial formula for Pontrjagin classes, a long-open problem. See <a href="http://www.ams.org/journals/bull/1992-26-02/S0273-0979-1992-00282-3/home.html" rel="nofollow">http://www.ams.org/journals/bull/1992-26-02/S0273-0979-1992-00282-3/home.html</a>. There have been many further developments in this area. </p> <p>(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.</p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/63854#63854 Answer by Tony Huynh for What are the external triumphs of matroid theory? Tony Huynh 2011-05-03T21:51:39Z 2011-05-04T02:24:43Z <p>Here is an example from polyhedral theory. A matrix $A \in \mathbb{R}^{n \times m}$ is <em>totally unimodular</em>, if every square submatrix of $A$ has determinant $1, -1,$ or $0$. Totally unimodular matrices are important objects in optimization theory since <em>integer</em> 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> <p>$P:=\lbrace x : Ax \leq b \rbrace$ is <em>integral</em> (the convex hull of the integral points inside $P$ is $P$ itself). This motivates the following important question.</p> <p><strong>Question:</strong> How can one efficiently recognize when a matrix is totally unimodular? </p> <p>Here's where matroids come in. A matroid is <em>regular</em> 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. </p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/63940#63940 Answer by Igor Pak for What are the external triumphs of matroid theory? Igor Pak 2011-05-04T19:07:23Z 2011-05-04T19:07:23Z <p>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. </p> <p><a href="http://bit.ly/hI8sqV" rel="nofollow">Mnёv's universality theorem</a> 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 <a href="http://www.math.ucdavis.edu/~kapovich/EPR/link.pdf" rel="nofollow">universality of linkages</a> theorem, Vakil's <a href="http://arxiv.org/abs/math/0411469" rel="nofollow">Murphy's Law</a>, and Belkale-Brosnan (strong) <a href="http://arxiv.org/abs/math/0012198" rel="nofollow">disproof of Kontsevich's conjecture</a> followed. Although some of these results do not explicitly use Mnёv's theorem, it served as an important motivation. </p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/63942#63942 Answer by David Harris for What are the external triumphs of matroid theory? David Harris 2011-05-04T19:14:38Z 2011-05-04T19:14:38Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/63951#63951 Answer by Sergey Melikhov for What are the external triumphs of matroid theory? Sergey Melikhov 2011-05-04T21:51:48Z 2011-05-04T21:51:48Z <p>A cell complex $K$ is an <em>$m$-obstructor</em> 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).</p> <p>Using <strong>matroids</strong>, Sarkaria <a href="http://kssarkaria.org/docs/Kuratowski.pdf" rel="nofollow">proved</a> that these joins are the <em>only</em> $2n$-obstructors among all $n$-dimensional <em>simplicial</em> complexes. I wish I could redo this result without matroids, but unfortunately I can't!</p> <p>The attraction of $n$-dimensional $2n$-obstructors is that while they don't embed in $\Bbb R^{2n}$, all their proper <a href="http://arxiv.org/abs/1103.5457" rel="nofollow">minors</a> (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.</p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/64201#64201 Answer by fan for What are the external triumphs of matroid theory? fan 2011-05-07T14:59:14Z 2011-05-07T14:59:14Z <p>Perhaps not the most powerful results, but here are some rather neat and rather recent applications.</p> <p>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.</p> <p>Ingleton's inequality has found its way into information theory, in the context of Shannon entropy. Here's one example: <a href="http://arxiv.org/abs/0905.1519" rel="nofollow">http://arxiv.org/abs/0905.1519</a></p> <p>The Vámos matroid provided a counterexample to a conjecture on sets representable by linear matrix inequalities: <a href="http://arxiv.org/abs/1004.1382" rel="nofollow">http://arxiv.org/abs/1004.1382</a></p> <p>The other day, a colleague showed me a rather nice proof of a linear algebra result. The proof used matroid union.</p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/65722#65722 Answer by andras frank for What are the external triumphs of matroid theory? andras frank 2011-05-22T18:03:02Z 2011-05-22T18:03:02Z <p>There are important algorithmic problems, not mentioning matroids at all in their formulations, for which the only polynomial algorithm I know is through matroids.</p> <p>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. </p> <p>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.</p> <p>The optimization problem we consider is to construct a minimum cost subgraph of D (on the same node-set) which is rooted k-connected. </p> <p>Using weighted matroid intersection, this is doable in polynomial time, though the reduction is not straightforward at all.</p> <p>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? </p> <p>There are great many other (hyper)graph optimization problems that can be handled only with matroid optimization. </p> <p>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:</p> <p><a href="http://ukcatalogue.oup.com/product/academic/series/mathematics/olsma/9780199205271.do" rel="nofollow">http://ukcatalogue.oup.com/product/academic/series/mathematics/olsma/9780199205271.do</a>? sortby=bookTitleAscend</p> <p>Andras Frank</p> http://mathoverflow.net/questions/63847/what-are-the-external-triumphs-of-matroid-theory/101548#101548 Answer by Patricia Hersh for What are the external triumphs of matroid theory? Patricia Hersh 2012-07-07T00:07:29Z 2012-07-07T00:07:29Z <p>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'. </p>