×

On the Ehrhart polynomial of minimal matroids. (English) Zbl 1490.05026

Summary: We provide a formula for the Ehrhart polynomial of the connected matroid of size \(n\) and rank \(k\) with the least number of bases, also known as a minimal matroid. We prove that their polytopes are Ehrhart positive and \(h^\ast\)-real-rooted (and hence unimodal). We prove that the operation of circuit-hyperplane relaxation relates minimal matroids and matroid polytopes subdivisions, and also preserves Ehrhart positivity. We state two conjectures: that indeed all matroids are \(h^\ast\)-real-rooted, and that the coefficients of the Ehrhart polynomial of a connected matroid of fixed rank and cardinality are bounded by those of the corresponding minimal matroid and the corresponding uniform matroid.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
11B73 Bell and Stirling numbers
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, F.; Benedetti, C.; Doker, J., Matroid polytopes and their volumes, Discrete Comput. Geom., 43, 4, 841-854 (2010) · Zbl 1204.52016 · doi:10.1007/s00454-009-9232-9
[2] Beck, M.; Jochemko, K.; McCullough, E., \(h^\ast \)-polynomials of zonotopes, Trans. Am. Math. Soc., 371, 3, 2021-2042 (2019) · Zbl 1402.05100 · doi:10.1090/tran/7384
[3] Beck, M.; Robins, S., Computing the Continuous Discretely. Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics (2015), New York: Springer, New York · Zbl 1339.52002
[4] Bonin, J.; de Mier, A.; Noy, M., Lattice path matroids: enumerative aspects and Tutte polynomials, J. Comb. Theory Ser. A, 104, 1, 63-94 (2003) · Zbl 1031.05031 · doi:10.1016/S0097-3165(03)00122-5
[5] Brändén, P., On operators on polynomials preserving real-rootedness and the Neggers-Stanley conjecture, J. Algebr. Comb., 20, 2, 119-130 (2004) · Zbl 1056.05006 · doi:10.1023/B:JACO.0000047295.93525.df
[6] Brändén, P.: Unimodality, log-concavity, real-rootedness and beyond. In: Handbook of Enumerative Combinatorics. Discrete Math. Appl. (Boca Raton), pp. 437-483. CRC Press, Boca Raton (2015) · Zbl 1327.05051
[7] Brändén, P.; Solus, L., Symmetric decompositions and real-rootedness, Int. Math. Res. Not. IMRN, 2021, 10, 7764-7798 (2021) · Zbl 1473.05329 · doi:10.1093/imrn/rnz059
[8] Castillo, F.; Liu, F., Berline -Vergne valuation and generalized permutohedra, Discrete Comput. Geom., 60, 4, 885-908 (2018) · Zbl 1401.52024 · doi:10.1007/s00454-017-9950-3
[9] De Loera, J.A., Haws, D., Hemmecke, R., Huggins, P., Tauzer, J., Yoshida, R.: A user’s guide for LattE (2003). https://www.math.ucdavis.edu/ latte
[10] De Loera, JA; Haws, DC; Köppe, M., Ehrhart polynomials of matroid polytopes and polymatroids, Discrete Comput. Geom., 42, 4, 670-702 (2009) · Zbl 1207.52015 · doi:10.1007/s00454-008-9080-z
[11] Dinolt, G.W.: An extremal problem for non-separable matroids. In: Théorie des Matroïdes (Brest 1970). Lecture Notes in Math., vol. 211, pp. 31-49. Springer, Berlin (1971) · Zbl 0215.33603
[12] Feichtner, EM; Sturmfels, B., Matroid polytopes, nested sets and Bergman fans, Port. Math. (N.S.), 62, 4, 437-468 (2005) · Zbl 1092.52006
[13] Ferroni, L., Hypersimplices are Ehrhart positive, J. Comb. Theory Ser. A, 178, # 105365 (2021) · Zbl 1459.52010 · doi:10.1016/j.jcta.2020.105365
[14] Gel’fand, IM; Goresky, RM; MacPherson, RD; Serganova, VV, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. Math., 63, 3, 301-316 (1987) · Zbl 0622.57014 · doi:10.1016/0001-8708(87)90059-4
[15] Graham, RL; Knuth, DE; Patashnik, O., Concrete Mathematics (1994), Reading: Addison-Wesley, Reading · Zbl 0836.00001
[16] Jochemko, K., On the real-rootedness of the Veronese construction for rational formal power series, Int. Math. Res. Not. IMRN, 2018, 15, 4780-4798 (2018) · Zbl 1408.13045 · doi:10.1093/imrn/rnx027
[17] Knauer, K.; Martínez-Sandoval, L.; Ramírez Alfonsín, JL, A Tutte polynomial inequality for lattice path matroids, Adv. Appl. Math., 94, 23-38 (2018) · Zbl 1377.05089 · doi:10.1016/j.aam.2016.11.008
[18] Knauer, K.; Martínez-Sandoval, L.; Ramírez Alfonsín, JL, On lattice path matroid polytopes: integer points and Ehrhart polynomial, Discrete Comput. Geom., 60, 3, 698-719 (2018) · Zbl 1494.52014 · doi:10.1007/s00454-018-9965-4
[19] Mills, AD, On matroids with many common bases, Discrete Math., 203, 1-3, 195-205 (1999) · Zbl 0930.05027 · doi:10.1016/S0012-365X(99)00005-9
[20] Murty, U.S.R.: On the number of bases of a matroid. In: 2nd Louisiana Conference on Combinatorics, Graph Theory and Computing (Baton Rouge 1971), pp. 387-410. Louisiana State University, Baton Rouge (1971) · Zbl 0302.05026
[21] Oxley, JG, Matroid Theory (1992), New York: Oxford Science Publications, Oxford University Press, New York · Zbl 0784.05002
[22] Székely, LA, 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 · doi:10.1016/0097-3165(85)90057-3
[23] Truemper, K., Alpha-balanced graphs and matrices and \({\rm GF}(3)\)-representability of matroids, J. Comb. Theory Ser. B, 32, 2, 112-139 (1982) · Zbl 0478.05026 · doi:10.1016/0095-8956(82)90028-4
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.