Matroid polytopes and their volumes (Q972610): Difference between revisions

The matroid polytope \(P_{M}\) of a matroid \(M\) is the polytope whose vertices are the characteristic vectors of the bases of the matroid. Matroid polytopes are in a sense the natural incarnations of matroids in algebraic geometry and optimization. The paper begins with observing that matroid polytopes are generalized permutohedra, as defined by \textit{A. Postnikov} [Int. Math. Res. Not. 2009, No.~6, 1026--1106 (2009; Zbl 1162.52007)]. Using a natural extension of Postnikov's theory of generalized permutohedra, the authors 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 }\). The authors then derive analogous results for the independent set polytope and the underlying flag matroid polytope of \(M\).