UC Berkeley

Many important invariants for matroids and polymatroids are valuations (or are valuative), which is to say they satisfy certain relations imposed by subdivisions of matroid polytopes. These include the Tutte polynomial, the Billera-Jia-Reiner quasi-symmetric function, Derksen's invariant G, and (up to change of variables) Speyer's invariant h.

We prove that the ranks of the subsets and the activities of the bases of a matroid define valuations for the subdivisions of a matroid polytope into smaller matroid polytopes; this provides a more elementary proof that the Tutte polynomial is a valuation than previously known.

We proceed to construct the Z-modules of all Z-valued valuative functions for labeled matroids and polymatroids on a fixed ground set, and their unlabeled counterparts, the Z-modules of valuative invariants. We give explicit bases for these modules and for their dual modules generated by indicator functions of polytopes, and explicit formulas for their ranks. This confirms Derksen's conjecture that G has a universal property for valuative invariants.

We prove also that the Tutte polynomial can be obtained by a construction involving equivariant K-theory of the Grassmannian, and that a very slight variant of this construction yields Speyer's invariant h. We also extend results of Speyer concerning the behavior of such classes under direct sum, series and parallel connection and two-sum; these results were previously only established for realizable matroids, and their earlier proofs were more difficult.

We conclude with an investigation of a generalisation of matroid polytope subdivisions from the standpoint of tropical geometry, namely subdivisions of Chow polytopes. The Chow polytope of an algebraic cycle in a torus depends only on its tropicalisation. Generalising this, we associate a Chow polytope subdivision to any abstract tropical variety in Rⁿ.

Several significant polyhedra associated to tropical varieties are special cases of our Chow subdivision. The Chow subdivision of a tropical variety X is given by a simple combinatorial construction: its normal subdivision is the Minkowski sum of X and an upside-down tropical linear space.