×

Matroid polytopes and their volumes. (English) Zbl 1204.52016

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 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\).

MSC:

52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)

Citations:

Zbl 1162.52007
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, F., Fink, A., Rincon, F.: Valuations for matroid polytope subdivisions. Can. Math. Bull. (to appear) · Zbl 1231.05053
[2] Billera, L.J., Jia, N., Reiner, V.: A quasisymmetric function for matroids. Eur. J. Comb. 30, 1727-1757 (2009) · Zbl 1179.05025 · doi:10.1016/j.ejc.2008.12.007
[3] 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) · Zbl 0929.05014 · doi:10.1007/BF02558461
[4] Borovik, A., Gelfand, I.M., White, N.: Coxeter Matroids. Birkhäuser, Boston (2003) · Zbl 1050.52005
[5] Crapo, H.: A higher invariant for matroids. J. Comb. Theory 2, 406-417 (1967) · Zbl 0168.26203 · doi:10.1016/S0021-9800(67)80051-6
[6] De Loera, J.A., Haws, D.C., Köppe, M.: Ehrhart polynomials of matroid polytopes and polymatroids. Discrete Comput. Geom. 42, 670-702 (2009) · Zbl 1207.52015 · doi:10.1007/s00454-008-9080-z
[7] Derksen, H.: Symmetric and quasi-symmetric functions associated to polymatroids. J. Algebr. Comb. 30, 43-86 (2009) · Zbl 1231.05276 · doi:10.1007/s10801-008-0151-2
[8] Fulton, W.: Introduction to Toric Varieties. Ann. of Math. Stud., vol. 131. Princeton Univ., Princeton (1993) · Zbl 0813.14039
[9] Gelfand, I.M., Goresky, M., MacPherson, R.D., Serganova, V.V.: Combinatorial geometries, convex polyhedra, and Schubert cells. Adv. Math. 63, 301-316 (1987) · Zbl 0622.57014 · doi:10.1016/0001-8708(87)90059-4
[10] Lafforgue, L.: Chirurgie des grassmanniennes. CRM Monograph Series, vol. 19. American Mathematical Society, Providence (2003) · Zbl 1026.14015
[11] Lam, T., Postnikov, A.: Alcoved polytopes. Discrete Comput. Geom. 38, 453-478 (2007) · Zbl 1134.52019 · doi:10.1007/s00454-006-1294-3
[12] McMullen, P.: Valuations and Euler-type relations on certain classes of convex polytopes. Proc. Lond. Math. Soc. 3(35), 113-135 (1977) · Zbl 0353.52001 · doi:10.1112/plms/s3-35.1.113
[13] Oxley, J.G.: Matroid Theory. Oxford University Press, New York (1992) · Zbl 0784.05002
[14] Postnikov, A.: Permutohedra, associahedra and beyond. Int. Res. Math. Res. Not. 2009(6), 1026-1106 (2009) · Zbl 1162.52007
[15] Speyer, D.E.: Tropical linear spaces. SIAM J. Discrete Math. 22, 1527-1558 (2008) · Zbl 1191.14076 · doi:10.1137/080716219
[16] Speyer, D.E.: A matroid invariant via the K-theory of the Grassmannian. Adv. Math. 221, 882-913 (2009) · Zbl 1222.14131 · doi:10.1016/j.aim.2009.01.010
[17] Stanley, R.; Aigner, M. (ed.), Eulerian partition of a unit hypercube (1977), Dordrecht
[18] Sturmfels, B.: Solving Systems of Polynomial Equations. CBMS Regional Conference in Mathematics, vol. 97. American Mathematical Society, Providence (2002) · Zbl 1101.13040
[19] Welsh, D.J.A.: Matroid Theory. Academic Press, London (1976) · Zbl 0343.05002
[20] White, N.: Theory of Matroids. Encyclopedia of Mathematics and its Applications, vol. 26. Cambridge University Press, Cambridge (1986) · Zbl 0579.00001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.