×

Ehrhart polynomials of matroid polytopes and polymatroids. (English) Zbl 1207.52015

It is shown that the Ehrhart polynomials of polymatroids and of matroid polytopes of given (fixed) rank can be computed in polynomial time. An ingredient required in the computation is an efficient method for evaluation of Todd polynomials. Examination of the Ehrhart polynomials of many of these polytopes led the authors to conjecture that (1) the \(h^*\)-vector of any matroid polytope is unimodal and (2) the coefficients of the Ehrhart polynomial of any matroid polytope are nonnegative. It is proven that the two conjectures hold in the case of uniform matroids of rank two. Tables containing the coefficients of the Ehrhart polynomials of nearly three dozen polymatroids and matroid polytopes are included.

MSC:

52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
52B55 Computational aspects related to convexity

Software:

LattE; cdd
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barvinok, A.I.: Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19, 769-779 (1994) · Zbl 0821.90085 · doi:10.1287/moor.19.4.769
[2] Barvinok, A.I.: Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comput. 75(255), 1449-1466 (2006) (electronic) · Zbl 1093.52009 · doi:10.1090/S0025-5718-06-01836-9
[3] Barvinok, A. I.; Pommersheim, J. E.; Billera, L. J. (ed.); Björner, A. (ed.); Greene, C. (ed.); Simion, R. E. (ed.); Stanley, R. P. (ed.), An algorithmic theory of lattice points in polyhedra, No. 38, 91-147 (1999), Cambridge · Zbl 0940.05004
[4] Barvinok, A.I., Woods, K.: Short rational generating functions for lattice point problems. J. AMS 16(4), 957-979 (2003) · Zbl 1017.05008
[5] Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra. Springer, Berlin (2007) · Zbl 1114.52013
[6] Beck, M., Sottile, F.: Irrational proofs for three theorems of Stanley. Eur. J. Comb. 28(1), 403-409 (2007) · Zbl 1109.05017 · doi:10.1016/j.ejc.2005.06.003
[7] Beck, M., Haase, C., Sottile, F.: Formulas of Brion, Lawrence, and Varchenko on rational generating functions for cones. Eprint arXiv:math.CO/0506466 (2006) · Zbl 1185.05007
[8] Billera, L.J., Jia, N., Reiner, V.: A quasisymmetric function for matroids. Eprint arXiv:math/0606646 (2006) · Zbl 1179.05025
[9] Brightwell, G., Winkler, P.: Counting linear extensions. Order 8(3), 225-242 (1991) · Zbl 0759.06001 · doi:10.1007/BF00383444
[10] Brion, M.: Points entiers dans les polyédres convexes. Ann. Sci. Éc. Norm. Sup. 21(4), 653-663 (1988) · Zbl 0667.52011
[11] De Loera, J.A., Haws, D., Hemmecke, R., Huggins, P., Sturmfels, B., Yoshida, R.: Short rational functions for toric algebra and applications. J. Symb. Comput. 38(2), 959-973 (2004) · Zbl 1137.13316 · doi:10.1016/j.jsc.2004.02.001
[12] De Loera, J.A., Hemmecke, R., Tauzer, J., Yoshida, R.: Effective lattice point counting in rational convex polytopes. J. Symb. Comput. 38(4), 1273-1302 (2004) · Zbl 1137.52303 · doi:10.1016/j.jsc.2003.04.003
[13] De Loera, J.A., Haws, D.C., Hemmecke, R., Huggins, P., Tauzer, J., Yoshida, R.: Software and User’s Guide for Latte v.1.1 (2005). http://www.math.ucdavis.edu/ latte
[14] De Loera, J.A., Rambau, J., Santos, F.: Triangulations: Applications, Structures, Algorithms. Book Manuscript (2006)
[15] De Loera, J.A., Haws, D.C., Köppe, M.: Matroid Polytopes (2007). http://math.ucdavis.edu/ haws/Matroids/ · Zbl 1207.52015
[16] De Negri, E., Hibi, T.: Gorenstein algebras of Veronese type. J. Algebra 193(2), 629-639 (1997), 1997 · Zbl 0884.13012 · doi:10.1006/jabr.1997.6990
[17] Dyer, M.E., Frieze, A.M.: On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17(5), 967-974 (1988). ISSN 0097-5397 · Zbl 0668.68049 · doi:10.1137/0217060
[18] Edmonds, J.; Jünger, M. (ed.); Reinelt, G. (ed.); Rinaldi, G. (ed.), Submodular functions, matroids, and certain polyhedra, Aussois, France, 5-9 March 2001, Berlin · Zbl 1024.90054
[19] Elekes, G.: A geometric inequality and the complexity of computing volume. Discrete Comput. Geom. 1(4), 289-292 (1986), 1986 · Zbl 0611.52010 · doi:10.1007/BF02187701
[20] Feichtner, E.M., Sturmfels, B.: Matroid polytopes, nested sets and Bergman fans. Port. Math. 62, 437-468 (2005) · Zbl 1092.52006
[21] Fukuda, K.: cdd+, a C++ implementation of the double description method of Motzkin et al. (2006). Available from URL http://www.ifor.math.ethz.ch/ fukuda/cdd_home/cdd.html
[22] 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
[23] Goodman, J.E., O’Rourke, J. (eds.): Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton (1997) · Zbl 0890.52001
[24] Hibi, T.: Algebraic Combinatorics on Convex Polytopes. Carslaw, Glebe (1992) · Zbl 0772.52008
[25] Katzman, M.: The Hilbert series of algebras of Veronese type. Commun. Algebra 33, 1141-1146 (2005) · Zbl 1107.13003 · doi:10.1081/AGB-200053828
[26] Khachiyan, L., Complexity of polytope volume computation, No. 10, 91-101 (1993), Berlin · Zbl 0789.52016
[27] Köppe, M.: A primal Barvinok algorithm based on irrational decompositions. SIAM J. Discrete Math. 21(1), 220-236 (2007). doi:10.1137/060664768 · Zbl 1135.05003 · doi:10.1137/060664768
[28] Köppe, M.: LattE macchiato, version 1.2-mk-0.9, an improved version of De Loera et al.’s LattE program for counting integer points in polyhedra with variants of Barvinok’s algorithm (2007). Available from URL http://www.math.uni-magdeburg.de/ mkoeppe/latte/
[29] Köppe, M., Verdoolaege, S.: Computing parametric rational generating functions with a primal Barvinok algorithm. Electron. J. Comb. 15, R16 (2008) · Zbl 1180.52014
[30] Lawrence, J.: Polytope volume computation. Math. Comput. 57(195), 259-271 (1991) · Zbl 0734.52009 · doi:10.2307/2938672
[31] Lawrence, J., Rational-function-valued valuations on polyhedra, New Brunswick, NJ, 1989/1990, Providence · Zbl 0744.52007
[32] Oxley, J.: Matroid Theory. Oxford University Press, New York (1992) · Zbl 0784.05002
[33] Petkovšek, M., Wilf, H.S., Zeilberger, D.: A=B. AK Peters, Wellesley (1996). http://www.math.upenn.edu/ wilf/AeqB.html · Zbl 0848.05002
[34] Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986) · Zbl 0665.90063
[35] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003) · Zbl 1041.90001
[36] Speyer, D.E.: A matroid invariant via the K-theory of the Grassmannian. Eprint arXiv:math/0603551v1 (2006) · Zbl 1222.14131
[37] Stanley, R.P.: Combinatorics and Commutative Algebra, 2nd edn. Birkhäuser, Boston (1996) · Zbl 0838.13008
[38] Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge (1997) · Zbl 0889.05001
[39] Topkis, D.M.: Adjacency on polymatroids. Math. Program. 30(2), 229-237 (1984) · Zbl 0544.90077 · doi:10.1007/BF02591887
[40] Verdoolaege, S., Woods, K.M.: Counting with rational generating functions. J. Symb. Comput. 43(2), 75-91 (2008). doi:http://dx.doi.org/10.1016/j.jsc.2007.07.007. ISSN 0747-7171 · Zbl 1137.05007 · doi:10.1016/j.jsc.2007.07.007
[41] Welsh, D.: Matroid Theory. Academic Press, San Diego (1976) · Zbl 0343.05002
[42] Woods, K.: Rational generating functions and lattice point sets. Ph.D. thesis, University of Michigan (2004)
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.