Yesterday marked the second anniversary of my blog, and today is the 239th birthday of the U.S. In celebration of Independence Day, I want to explain what matroids are. Matroids were invented by Hassler Whitney (and independently by Takeo Nakasawa) to abstract the notion of linear independence from vector spaces to a much more general setting that includes acyclicity in graphs. Other pioneering early work on matroids was done by Garrett Birkhoff and Saunders MacLane. Matroid theory is a rich subject about which we will only scratch the surface here. In particular, there are many different (“cryptomorphic“) ways to present the matroid axioms which all turn out to be (non-obviously) equivalent to one another. We will focus on just a couple of ways of looking at matroids, emphasizing their connections to tropical geometry.
We begin with the independence point of view, which in many ways is the most intuitive one (not to mention the most appropriate for the Fourth of July).
A matroid is a finite set (called the ground set of ) together with a collection of subsets of , called independent sets of , such that:
• (I1) The empty set is independent.
• (I2) Every subset of an independent set is independent.
• (I3) (Augmentation axiom) If are independent sets with , then there exists such that is independent.
A maximal independent set is called a basis. The augmentation axiom implies that any two bases of have the same cardinality; we define the rank of to be this common cardinality.
A subset of which is not independent is called dependent. A circuit in a matroid is a minimal dependent set. The collection of circuits in a matroid satisfies the following axioms, which can in fact be taken as an alternate definition of a matroid:
• (C1) Every circuit is non-empty.
• (C2) No proper subset of a circuit is a circuit.
• (C3) (Circuit Elimination Axiom) If are distinct circuits and , then contains a circuit.
It is often convenient to replace (C3) by the a priori stronger but equivalent axiom
• (C3′) (Strong Circuit Elimination Axiom) If are distinct circuits, , and , there is a circuit containing and contained in .
Here are some key examples of matroids:
Example 1 (Linear matroids): Let be a vector space over a field , let be a finite subset of , and let be the collection of all linearly independent subsets of . Then is a matroid. A matroid of this form is said to be representable over . If we write the elements of as the columns of an matrix (with respect to some ordered basis of ), then a subset of is independent iff the corresponding columns of are linearly independent over . We denote this matroid by .
Example 2 (Graphic matroids): Let be a connected finite graph, let be the set of edges of , and let be the collection of all subsets of which do not contain a cycle. Then is a matroid which is representable over every field . (Matroids with this latter property are called regular.) A basis of is just a spanning tree of . An amazing theorem of Whitney says that if is -connected then determines up to isomorphism.
Example 3 (Fano matroid): Let be the projective plane over (the seven elements of can be identified with the dots in the picture below). A subset is dependent if and only if or and is one of the 7 lines in the picture (6 straight and one curved). This notion of dependency gives rise to a rank 3 matroid, the Fano matroid, which is representable over but not over any field of characteristic different from 2. In particular, the Fano matroid is not graphic.
Example 4 (Algebraic matroids): Let , let be the polynomial ring in variables over a field , and let be a prime ideal of . Let be the collection of all such that . Then is a matroid. A matroid of this form is said to be algebraic over . (This is not the usual definition, but is equivalent to it.) All representable matroids over are algebraic.
Example 5 (Vamos matroid): Let be the 8 vertices of the cuboid shown in the following picture. A subset is dependent if and only if or and is one of the 5 square faces in the picture. This notion of dependency gives rise to a rank 4 matroid, the Vamos matroid, which is not algebraic, so in particular not representable, over any field.
If is a matroid, let be the collection of subsets such that contains a basis for . It turns out that satisfies axioms (I1),(I2), and (I3) and thus is a matroid, called the dual matroid of .
If is the linear matroid associated to a matrix , then is the linear matroid associated to the transpose of . If is the matroid associated to a planar graph , then is the matroid associated to the planar dual of . Another amazing theorem of Whitney says that, conversely, if is a connected graph for which the dual matroid is graphic, then is planar.
It is an open problem whether or not the dual of an algebraic matroid is always algebraic.
Connection to tropical geometry
Let be a matroid with ground set . We define to be the set of vectors such that for any circuit of , the minimum is achieved twice in . A matroid fan is a subset of of the form for some matroid on . There is a close connection between matroid fans and tropicalizations of linear spaces over trivially valued fields, as we will now describe.
Let be a field equipped with a valuation, i.e., a map satisfying iff , , , and for all .
A valued field extension of is a pair consisting of a field extension together with a valuation on extending the given valuation on . We denote by the set of valued field extensions of .
If is an algebraic subvariety, we define the tropicalization of to be
where is the base-change of to .
One can show that is the topological closure of
for any such that is dense in , and such a valued field always exists.
By the Bieri-Groves theorem, if is an algebraic subvariety of of pure dimension , then is the support of a rational polyhedral complex of pure dimension . Moreover, if is connected then so is . If the valuation on is trivial (meaning that for ), then is the support of a rational polyhedral fan.
Let be a field. We call a subspace of non-degenerate if it is not contained in any coordinate hyperplane , . If is a non-degenerate -dimensional subspace of , one can define an associated rank matroid by declaring that a subset is independent if and only if
The following theorem is a consequence of results of Kapranov and Sturmfels:
Theorem 1: If is a non-degenerate subspace of then (with respect to the trivial valuation on )
This shows, in particular, that the tropicalization of depends only on the matroid .
A natural way to put a fan structure on is as follows. For , we define the initial matroid to be the matroid on whose circuits are the minimal sets among
Note that, by definition, is equal to the set of such that has no loops. (A loop is a circuit with one element.) It turns out that the cones associated to the various distinct initial matroids form a -dimensional rational polyhedral fan, called the Bergman fan of , whose support is . This fan is balanced, meaning that for each -dimensional cone , the sum of the ray generators of the -dimensional cones that contain belongs to .
The relationship between matroids and tropical geometry is even closer than Theorem 1 would indicate. To state the result, we define a tropical linear fan of dimension to be the support of a balanced rational polyhedral fan of pure dimension .
Theorem 2: One can recover a matroid on from the tropical linear fan . Moreover, every tropical linear fan is the support of for some matroid . Thus the association gives a natural bijection between rank matroids on and tropical linear fans of dimension in . A matroid is representable over iff for some non-degenerate linear subspace .
Motivated by Rota’s conjecture that the coefficients of the characteristic polynomial of a matroid form a log-concave sequence, June Huh has asked (see e.g. Section 4.3 of his thesis) whether, given a matroid on and an algebraically closed field , there always exists an algebraic variety (not necessarily a linear space!) such that (as sets). My Georgia Tech colleague Josephine Yu recently proved that the answer is no; more precisely, she shows in this beautiful short paper if is not algebraic then there is no such variety . So, for example, the Bergman fan of the Vamos matroid is not the set-theoretic tropicalization of any algebraic variety.
Valuated matroids and general tropical linear spaces
So far we have been working over a trivially valued field . There is an analogous story which works for arbitrary non-archimedean fields in which we replace matroids by valuated matroids. The circuit-based definition (due to Murota and Tamura) is as follows.
Let , and define the support of a vector to be
A valuated matroid on is a collection of (valuated) circuits satisfying:
(VC1) If and then .
(VC2) If with then .
(VC3) (Valuated Strong Circuit Elimination) If and with and , then there exists such that , , and .
It follows from the axioms that a circuit is determined, up to a scalar multiple of , by its support. In particular, the set of circuits mod in a valuated matroid is finite.
Every matroid can be enhanced to a valuated matroid, but possibly in many different ways. This is analogous to the fact that every field can be regarded as a valued field by putting the trivial absolute value on it, but in general there are many different valued field structures on .
We denote by the underlying matroid of a valuated matroid : a subset of is a circuit of if and only if it is the support of a circuit of .
Like ordinary matroids, valuated matroids have duals. We say that two vectors and in are orthogonal, written , if the minimum is achieved twice in the “tropical dot product” . The vectors of minimal support in satisfy the axioms (VC0)-(VC3) and therefore form the circuits of a valuated matroid called the dual valuated matroid . The underlying matroid of is the dual of the underlying matroid of .
Let be a valuated matroid. We define the tropical linear space associated to , denoted , to be the tropical convex hull of the circuits of , i.e. the set of all such that for and .
A tropical linear space is a subspace of of the form for a valuated matroid . It can be given the structure of a polyhedral complex whose recession fan is . One can check that a tropical linear fan, as previously defined, is in particular a tropical linear space (modulo the fact that for technical reasons we are now working in rather than ).
As in the trivially valued case, there is a close relationship between this definition and the tropicalization of linear spaces. If is a non-archimedean field and is a -dimensional -linear subspace of , we can define an associated valuated matroid whose circuits are the minimal (in the sense of inclusion of supports) elements of
The fact that satisfies (VC0)-(VC3) is one justification for the definition of a valuated matroid. There are lots of other good justifications. For example, Alex Fink proved the folklore fact that a tropical linear space is the same thing as a balanced polyhedral complex whose recession fan is a tropical linear fan, which is the same as a “tropical cycle of degree 1”. As another example of why valuated matroids are nice, there is an equivalent definition using tropical Plücker vectors reflecting the fact that, just as linear spaces can be thought of as vectors satisfying the Plücker relations, a valuated matroid can be thought of as a tropical vector satisfying the tropicalization of the Plücker relations.
1. A good reference for tropical geometry and its relation to matroid theory is the recently published book Introduction to Tropical Geometry by Maclagan and Sturmfels. For an introduction to matroids targeted to algebraic geometers, I recommend Eric Katz’s survey paper. For the combinatorially minded, there are many good introductions including this survey paper by Oxley.
2. Simon Hampe has recently shown that a tropical linear fan (resp. tropical linear space) is the same thing as a pure-dimensional balanced rational polyhedral fan (resp. polyhedral complex) which is tropically convex. This gives a purely geometric characterization of matroids (resp. valuated matroids).
3. June Huh and Eric Katz use Bergman fans of matroids in order to prove Rota’s conjecture for matroids representable over some field in this paper. Note that what they call the Bergman fan is a subdivision of what we have called the Bergman fan. See Section 4.2 of the Maclagan-Sturmfels book for descriptions of both of these fan structures on .
4. Bergman fans of matroids are examples of strongly extremal tropical varieties, i.e., pure-dimensional rational polyhedral complexes admitting a unique (up to scalar multiple) set of weights which make them balanced. Strongly extremal tropical varieties play a central role in this paper by Farhad Babaee and June Huh giving a counterexample to the strongly positive Hodge conjecture of Demailly.
5. Maclagan and Rincon use tropical linear spaces and valuated matroids to prove some new results about the Giansiricusas’ notion of tropical scheme theory in their recent paper “Tropical schemes, tropical cycles, and valuated matroids”.
6. Just as a smooth manifold is a space which is locally a linear space, it is natural in tropical geometry to define a tropical variety to be smooth if the star of every point is a tropical linear fan (i.e., the Bergman fan of a matroid). This point of view leads, for example, to a tropical analogue of Hodge theory via the Orlik-Solomon algebra of a matroid (see, e.g., Chapter 2 of Kristin Shaw’s thesis).