×
Ferroni, Luis; Jochemko, Katharina; Schröter, Benjamin

Ehrhart polynomials of rank two matroids. (English) Zbl 1496.52016

Adv. Appl. Math. 141, Article ID 102410, 26 p. (2022).
Summary: Over a decade ago De Loera, Haws and Köppe conjectured that Ehrhart polynomials of matroid polytopes have only positive coefficients and that the coefficients of the corresponding \(h^\ast \)-polynomials form a unimodal sequence. The first of these intensively studied conjectures has recently been disproved by the first author who gave counterexamples in all ranks greater than or equal to three. In this article we complete the picture by showing that Ehrhart polynomials of matroids of lower rank have indeed only positive coefficients. Moreover, we show that they are coefficient-wise bounded by the Ehrhart polynomials of minimal and uniform matroids. We furthermore address the second conjecture by proving that \(h^\ast \)-polynomials of matroid polytopes of sparse paving matroids of rank two are real-rooted and therefore have log-concave and unimodal coefficients. In particular, this shows that the \(h^\ast \)-polynomial of the second hypersimplex is real-rooted, thereby strengthening a result of De Loera, Haws and Köppe.

Cited in 5 Documents

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)
05A15 Exact enumeration problems, generating functions
05B35 Combinatorial aspects of matroids and geometric lattices
26C10 Real polynomials: location of zeros

Keywords:

Ehrhart theory; lattice polytopes; matroids; log-concavity; real-rootedness; Ehrhart positivity
Cite Review PDF
Full Text: DOI arXiv
Creative Commons CC license icon Creative Commons BY license icon

References:

[1] Adiprasito, K.; Huh, J.; Katz, E., Hodge theory for combinatorial geometries, Ann. Math. (2), 188, 2, 381-452 (2018) · Zbl 1442.14194
[2] Ardila, F.; Rincón, F.; Williams, L., Positroids and non-crossing partitions, Trans. Am. Math. Soc., 368, 1, 337-363 (2016) · Zbl 1325.05015
[3] Beck, M.; Robins, S., Computing the Continuous Discretely, Undergraduate Texts in Mathematics (2015), Springer: Springer New York, Integer-point enumeration in polyhedra, with illustrations by David Austin · Zbl 1339.52002
[4] Brändén, P., Unimodality, log-concavity, real-rootedness and beyond, (Handbook of Enumerative Combinatorics. Handbook of Enumerative Combinatorics, Discrete Math. Appl. (Boca Raton) (2015), CRC Press: CRC Press Boca Raton, FL), 437-483 · Zbl 1327.05051
[5] Brändén, P.; Huh, J., Lorentzian polynomials, Ann. Math. (2), 192, 3, 821-891 (2020) · Zbl 1454.52013
[6] Braun, B., Unimodality problems in Ehrhart theory, (Recent Trends in Combinatorics. Recent Trends in Combinatorics, IMA Vol. Math. Appl., vol. 159 (2016), Springer: Springer Cham), 687-711 · Zbl 1366.52014
[7] Brenti, F., Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, (Jerusalem Combinatorics ’93. Jerusalem Combinatorics ’93, Contemp. Math., vol. 178 (1994), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 71-89 · Zbl 0813.05007
[8] Castillo, F.; Liu, F., Berline-Vergne valuation and generalized permutohedra, Discrete Comput. Geom., 60, 4, 885-908 (2018) · Zbl 1401.52024
[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] Dinolt, G. W., An extremal problem for non-separable matroids, (Théorie des matroïdes (Rencontre Franco-Britannique). Théorie des matroïdes (Rencontre Franco-Britannique), Brest, 1970. Théorie des matroïdes (Rencontre Franco-Britannique). Théorie des matroïdes (Rencontre Franco-Britannique), Brest, 1970, Lecture Notes in Math., vol. 211 (1971)), 31-49 · Zbl 0215.33603
[12] Ehrhart, E., Sur les polyèdres rationnels homothétiques à n dimensions, C. R. Acad. Sci. Paris, Ser. I, 254, 616-618 (1962) · Zbl 0100.27601
[13] Feichtner, E. M.; Sturmfels, B., Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), 62, 4, 437-468 (2005) · Zbl 1092.52006
[14] Ferroni, L., Hypersimplices are Ehrhart positive, J. Comb. Theory, Ser. A, 178, Article 105365 pp. (2021), 13 pp. · Zbl 1459.52010
[15] Ferroni, L., Matroids are not Ehrhart positive, Adv. Math., 402, Article 108337 pp. (2022) · Zbl 1487.52022
[16] Ferroni, L., On the Ehrhart polynomial of minimal matroids, Discrete Comput. Geom., 68, 1, 255-273 (2022) · Zbl 1490.05026
[17] Fujishige, S., A characterization of faces of the base polyhedron associated with a submodular system, J. Oper. Res. Soc. Jpn., 27, 2, 112-129 (1984) · Zbl 0543.52008
[18] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics (1994), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA, A foundation for computer science · Zbl 0836.00001
[19] Hibi, T., Some results on Ehrhart polynomials of convex polytopes, Discrete Math., 83, 1, 119-121 (1990) · Zbl 0708.52005
[20] Jochemko, K.; Ravichandran, M., Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity, Mathematika, 68, 1, 217-236 (2022) · Zbl 1522.52030
[21] Joswig, M.; Schröter, B., Matroids from hypersimplex splits, J. Comb. Theory, Ser. A, 151, 254-284 (2017) · Zbl 1366.05024
[22] Katzman, M., The Hilbert series of algebras of the Veronese type, Commun. Algebra, 33, 4, 1141-1146 (2005) · Zbl 1107.13003
[23] Knauer, K.; Martínez-Sandoval, L.; Ramírez Alfonsín, J. L., On lattice path matroid polytopes: integer points and Ehrhart polynomial, Discrete Comput. Geom., 60, 3, 698-719 (2018) · Zbl 1494.52014
[24] Lam, T.; Postnikov, A., Polypositroids (Oct. 2020), arXiv e-prints
[25] 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
[26] 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
[27] Nishimura, H.; Kuroda, S., A Lost Mathematician, Takeo Nakasawa (2009), Birkhäuser Verlag: Birkhäuser Verlag Basel, The forgotten father of matroid theory · Zbl 1163.01001
[28] Oh, S., Positroids and Schubert matroids, J. Comb. Theory, Ser. A, 118, 8, 2426-2435 (2011) · Zbl 1231.05061
[29] Oxley, J., Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 21 (2011), Oxford University Press: Oxford University Press Oxford · Zbl 1254.05002
[30] Postnikov, A., Total positivity, Grassmannians, and networks (Sept. 2006), arXiv Mathematics e-prints
[31] Savage, C. D.; Schuster, M. J., Ehrhart series of lecture Hall polytopes and Eulerian polynomials for inversion sequences, J. Comb. Theory, Ser. A, 119, 4, 850-870 (2012) · Zbl 1237.05017
[32] 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
[33] Stanley, R. P., Decompositions of rational convex polytopes, Ann. Discrete Math., 6, 333-342 (1980) · Zbl 0812.52012
[34] Stanley, R. P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, (Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Jinan, 1986. Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Jinan, 1986, Ann. New York Acad. Sci., vol. 576 (1989), New York Acad. Sci.: New York Acad. Sci. New York), 500-535 · Zbl 0792.05008
[35] Stanley, R. P., On the Hilbert function of a graded Cohen-Macaulay domain, J. Pure Appl. Algebra, 73, 3, 307-314 (1991) · Zbl 0735.13010
[36] Stanley, R. P., Enumerative Combinatorics, volume 1, Cambridge Studies in Advanced Mathematics, vol. 49 (2012), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1247.05003
[37] Stapledon, A., Inequalities and Ehrhart δ-vectors, Trans. Am. Math. Soc., 361, 10, 5615-5626 (2009) · Zbl 1181.52024
[38] Székely, L. A., Common origin of cubic binomial identities; a generalization of Surányi’s proof on Le Jen Shoo’s formula, J. Comb. Theory, Ser. A, 40, 1, 171-174 (1985) · Zbl 0573.05005
[39] (White, N., Theory of Matroids. Theory of Matroids, Encyclopedia of Mathematics and Its Applications., vol. 26 (1986), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 0579.00001
[40] Whitney, H., On the abstract properties of linear dependence, Am. J. Math., 57, 3, 509-533 (1935) · JFM 61.0073.03
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.