×

Matroids are not Ehrhart positive. (English) Zbl 1487.52022

Summary: In this article we disprove the conjectures asserting the positivity of the coefficients of the Ehrhart polynomial of matroid polytopes by De Loera, Haws and Köppe [J. A. De Loera et al., Discrete Comput. Geom. 42, No. 4, 670–702; erratum ibid. 42, No. 4, 703–704 (2009; Zbl 1207.52015)] and of generalized permutohedra by F. Castillo and F. Liu [in: Proceedings of the 27th international conference on formal power series and algebraic combinatorics, FPSAC 2015, Daejeon, South Korea, July 6–10, 2015. Nancy: The Association. Discrete Mathematics & Theoretical Computer Science (DMTCS). 865–876 (2015; Zbl 1362.05130)]. We prove constructively that for every \(n \geq 19\) there exist connected matroids on \(n\) elements that are not Ehrhart positive. Also, we prove that for every \(k \geq 3\) there exist connected matroids of rank \(k\) that are not Ehrhart positive. Our proofs rely on our previous results on the geometric interpretation of the operation of circuit-hyperplane relaxation and our formulas for the Ehrhart polynomials of hypersimplices and minimal matroids. This allows us to give a precise expression for the Ehrhart polynomials of all sparse paving matroids, a class of matroids which is conjectured to be predominant and which contains the counterexamples arising from our construction.

MSC:

52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
05B35 Combinatorial aspects of matroids and geometric lattices
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agrell, E.; Vardy, A.; Zeger, K., Upper bounds for constant-weight codes, IEEE Trans. Inf. Theory, 46, 7, 2373-2395 (2000) · Zbl 0997.94036
[2] Ardila, F.; Benedetti, C.; Doker, J., Matroid polytopes and their volumes, Discrete Comput. Geom., 43, 4, 841-854 (2010) · Zbl 1204.52016
[3] Bansal, N.; Pendavingh, R. A.; van der Pol, J. G., On the number of matroids, Combinatorica, 35, 3, 253-277 (2015) · Zbl 1363.05005
[4] Beck, M.; Robins, S., Computing the Continuous DiscretelyInteger-Point Enumeration in Polyhedra, Undergraduate Texts in Mathematics (2015), Springer: Springer New York, With illustrations by David Austin · Zbl 1339.52002
[5] Beck, M.; Sanyal, R., Combinatorial Reciprocity TheoremsAn Invitation to Enumerative Geometric Combinatorics, Graduate Studies in Mathematics, vol. 195 (2018), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1411.05001
[6] Brouwer, A. E.; Etzion, T., Some new distance-4 constant weight codes, Adv. Math. Commun., 5, 3, 417-424 (2011) · Zbl 1248.94127
[7] Castillo, F.; Liu, F., Berline-Vergne valuation and generalized permutohedra, Discrete Comput. Geom., 60, 4, 885-908 (2018) · Zbl 1401.52024
[8] Castillo, F.; Liu, F., Deformation cones of nested braid fans, Int. Math. Res. Not. (June 2020)
[9] Castillo, F.; Liu, F., On the Todd class of the permutohedral variety, Algebraic Combin., 4, 3, 387-407 (2021) · Zbl 1467.52022
[10] De Loera, J. A.; Haws, D. C.; Köppe, M., Ehrhart polynomials of matroid polytopes and polymatroids, Discrete Comput. Geom., 42, 4, 670-702 (2009) · Zbl 1207.52015
[11] Derksen, H.; Fink, A., Valuative invariants for polymatroids, Adv. Math., 225, 4, 1840-1892 (2010) · Zbl 1221.05031
[12] Dinolt, G. W., An extremal problem for non-separable matroids, (Théorie des matroïdes. Théorie des matroïdes, Rencontre Franco-Britannique, Brest, 1970. Théorie des matroïdes. Théorie des matroïdes, Rencontre Franco-Britannique, Brest, 1970, Lecture Notes in Math., vol. 211 (1971)), 31-49 · Zbl 0215.33603
[13] Edmonds, J., Submodular functions, matroids, and certain polyhedra, (Combinatorial Structures and Their Applications, Proc. Calgary Internat. Conf.. Combinatorial Structures and Their Applications, Proc. Calgary Internat. Conf., Calgary, Alta., 1969 (1970), Gordon and Breach: Gordon and Breach New York), 69-87 · Zbl 0268.05019
[14] Edmonds, J.; Rota, G.-C., Submodular set functions, (Waterloo Combinatorics Conference (1966), University of Waterloo: University of Waterloo Waterloo, Ontario)
[15] Ehrhart, E., Sur les polyèdres rationnels homothétiques à n dimensions, C. R. Acad. Sci. Paris, 254, 616-618 (1962) · Zbl 0100.27601
[16] Feichtner, E. M.; Sturmfels, B., Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), 62, 4, 437-468 (2005) · Zbl 1092.52006
[17] Ferroni, L., Hypersimplices are Ehrhart positive, J. Comb. Theory, Ser. A, 178, Article 105365 pp. (2021), 13 · Zbl 1459.52010
[18] Ferroni, L., Integer point enumeration on independence polytopes and half-open hypersimplices, Discrete Math., 344, 8, Article 112446 pp. (2021), 6 · Zbl 1475.51014
[19] Ferroni, L., On the Ehrhart polynomial of minimal matroids, Discrete Comput. Geom. (2021)
[20] Ferroni, L.; Jochemko, K.; Schröter, B., Ehrhart polynomials of rank two matroids (June 2021), arXiv e-prints
[21] Gel’fand, I. M.; Goresky, R. M.; MacPherson, R. D.; Serganova, V. V., Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. Math., 63, 3, 301-316 (1987) · Zbl 0622.57014
[22] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete MathematicsA Foundation for Computer Science (1994), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA · Zbl 0836.00001
[23] Graham, R. L.; Sloane, N. J.A., Lower bounds for constant weight codes, IEEE Trans. Inf. Theory, 26, 1, 37-43 (1980) · Zbl 0441.94012
[24] Hibi, T.; Higashitani, A.; Tsuchiya, A.; Yoshida, K., Ehrhart polynomials with negative coefficients, Graphs Comb., 35, 1, 363-371 (2019) · Zbl 1409.52012
[25] Jochemko, K.; Ravichandran, M., Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity, Mathematika (2021), in press
[26] Joswig, M.; Schröter, B., Matroids from hypersimplex splits, J. Comb. Theory, Ser. A, 151, 254-284 (2017) · Zbl 1366.05024
[27] Katzman, M., The Hilbert series of algebras of the Veronese type, Commun. Algebra, 33, 4, 1141-1146 (2005) · Zbl 1107.13003
[28] Liu, F., On positivity of Ehrhart polynomials, (Recent Trends in Algebraic Combinatorics. Recent Trends in Algebraic Combinatorics, Assoc. Women Math. Ser., vol. 16 (2019), Springer: Springer Cham), 189-237 · Zbl 1435.52007
[29] Liu, F.; Tsuchiya, A., Stanley’s non-Ehrhart-positive order polytopes, Adv. Appl. Math., 108, 1-10 (2019) · Zbl 1420.52016
[30] Mayhew, D.; Newman, M.; Welsh, D.; Whittle, G., On the asymptotic proportion of connected matroids, Eur. J. Comb., 32, 6, 882-890 (2011) · Zbl 1244.05047
[31] McMullen, P., Valuations and Euler-type relations on certain classes of convex polytopes, Proc. Lond. Math. Soc. (3), 35, 1, 113-135 (1977) · Zbl 0353.52001
[32] Murty, U. S.R., On the number of bases of a matroid, (Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing. Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La., 1971 (1971)), 387-410 · Zbl 0302.05026
[33] Oxley, J. G., Ternary paving matroids, Discrete Math., 91, 1, 77-86 (1991) · Zbl 0768.05023
[34] Oxley, J. G., Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 21 (2011), Oxford University Press: Oxford University Press Oxford · Zbl 1254.05002
[35] Pendavingh, R.; van der Pol, J., On the number of matroids compared to the number of sparse paving matroids, Electron. J. Comb., 22, 2, 17 (2015), Paper 2.51 · Zbl 1327.05056
[36] Postnikov, A., Permutohedra, associahedra, and beyond, Int. Math. Res. Not., 6, 1026-1106 (2009) · Zbl 1162.52007
[37] Postnikov, A.; Reiner, V.; Williams, L., Faces of generalized permutohedra, Doc. Math., 13, 207-273 (2008) · Zbl 1167.05005
[38] Schrijver, A., Combinatorial Optimization. Polyhedra and Efficiency. Vol. B, Algorithms and Combinatorics, vol. 24 (2003), Springer-Verlag: Springer-Verlag Berlin, Matroids, trees, stable sets, Chapters 39-69 · Zbl 1041.90001
[39] Sibuya, M., Log-concavity of Stirling numbers and unimodality of Stirling distributions, Ann. Inst. Stat. Math., 40, 4, 693-714 (1988) · Zbl 0676.60022
[40] Truemper, K., Alpha-balanced graphs and matrices and \(\operatorname{GF}(3)\)-representability of matroids, J. Comb. Theory, Ser. B, 32, 2, 112-139 (1982) · Zbl 0478.05026
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.