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 Grk,n. We then derive analogous results for the independent set polytope and the underlying flag matroid polytope of M. Our proofs are based on a natural extension of Postnikov’s theory of generalized permutohedra.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ardila, F., Fink, A., Rincon, F.: Valuations for matroid polytope subdivisions. Can. Math. Bull. (to appear)
Billera, L.J., Jia, N., Reiner, V.: A quasisymmetric function for matroids. Eur. J. Comb. 30, 1727–1757 (2009)
Borovik, A., Gelfand, I.M., Vince, A., White, N.: The lattice of flats and its underlying flag matroid polytope. Ann. Comb. 1, 17–26 (1997)
Borovik, A., Gelfand, I.M., White, N.: Coxeter Matroids. Birkhäuser, Boston (2003)
Crapo, H.: A higher invariant for matroids. J. Comb. Theory 2, 406–417 (1967)
De Loera, J.A., Haws, D.C., Köppe, M.: Ehrhart polynomials of matroid polytopes and polymatroids. Discrete Comput. Geom. 42, 670–702 (2009)
Derksen, H.: Symmetric and quasi-symmetric functions associated to polymatroids. J. Algebr. Comb. 30, 43–86 (2009)
Fulton, W.: Introduction to Toric Varieties. Ann. of Math. Stud., vol. 131. Princeton Univ., Princeton (1993)
Gelfand, I.M., Goresky, M., MacPherson, R.D., Serganova, V.V.: Combinatorial geometries, convex polyhedra, and Schubert cells. Adv. Math. 63, 301–316 (1987)
Lafforgue, L.: Chirurgie des grassmanniennes. CRM Monograph Series, vol. 19. American Mathematical Society, Providence (2003)
Lam, T., Postnikov, A.: Alcoved polytopes. Discrete Comput. Geom. 38, 453–478 (2007)
McMullen, P.: Valuations and Euler-type relations on certain classes of convex polytopes. Proc. Lond. Math. Soc. 3(35), 113–135 (1977)
Oxley, J.G.: Matroid Theory. Oxford University Press, New York (1992)
Postnikov, A.: Permutohedra, associahedra and beyond. Int. Res. Math. Res. Not. 2009(6), 1026–1106 (2009)
Speyer, D.E.: Tropical linear spaces. SIAM J. Discrete Math. 22, 1527–1558 (2008)
Speyer, D.E.: A matroid invariant via the K-theory of the Grassmannian. Adv. Math. 221, 882–913 (2009)
Stanley, R.: Eulerian partition of a unit hypercube. In: Aigner, M. (ed.) Higher Combinatorics. Reidel, Dordrecht (1977)
Sturmfels, B.: Solving Systems of Polynomial Equations. CBMS Regional Conference in Mathematics, vol. 97. American Mathematical Society, Providence (2002)
Welsh, D.J.A.: Matroid Theory. Academic Press, London (1976)
White, N.: Theory of Matroids. Encyclopedia of Mathematics and its Applications, vol. 26. Cambridge University Press, Cambridge (1986)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by NSF grant DMS-0801075 (Ardila), the Proyecto Semilla of the Universidad de Los Andes (Benedetti), and a San Francisco State University Seed Funding Grant to support the SFSU-Colombia Combinatorics Initiative.
Rights and permissions
About this article
Cite this article
Ardila, F., Benedetti, C. & Doker, J. Matroid Polytopes and their Volumes. Discrete Comput Geom 43, 841–854 (2010). https://doi.org/10.1007/s00454-009-9232-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9232-9