Matroid Polytopes and Their Volumes

Abstract

We express the matroid polytope $P_M$ of a matroid $M$ as a signed Minkowski sum of simplices, and obtain a formula for the volume of $P_M$. This gives a combinatorial expression for the degree of an arbitrary torus orbit closure in the Grassmannian $Gr_{k,n}$. We then derive analogous results for the independent set polytope and the associated flag matroid polytope of $M$. Our proofs are based on a natural extension of Postnikov's theory of generalized permutohedra.

Keywords

• matroid
• generalized permutohedron
• matroid polytope
• minkowski sum
• mixed volume
• flag matroid
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]