×
Hanely, Derek; Martin, Jeremy L.; McGinnis, Daniel; Miyata, Dane; Nasr, George D.; Vindas-Meléndez, Andrés R.; Yin, Mei

Ehrhart theory of paving and panhandle matroids. (English) Zbl 1526.05028

Adv. Geom. 23, No. 4, 501-526 (2023).
Summary: We show that the base polytope \(P_M\) of any paving matroid \(M\) can be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial of \(P_M\), starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes L. Ferroni’s work on sparse paving matroids [Discrete Comput. Geom. 68, No. 1, 255–273 (2022; Zbl 1490.05026)]. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation of stressed-hyperplane relaxation introduced by L. Ferroni [“Stressed hyperplanes and Kazhdan-Lusztig gamma-positivity for matroids”, Preprint, arXiv:2110.08869], which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent.

Cited in 1 Document

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
05C31 Graph polynomials
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
05B25 Combinatorial aspects of finite geometries

Keywords:

Ehrhart theory; matroid; relaxation; positivity; base polytope; paving matroid; Steiner system; projective plane

Citations:

Zbl 1490.05026

Software:

SageMath; OEIS
Cite Review PDF
Full Text: DOI arXiv

References:

[1] M. Aguiar, F. Ardila, Hopf monoids and generalized permutahedra. Preprint 2017, arXiv:1709.07504
[2] F. Ardila, C. Benedetti, J. Doker, Matroid polytopes and their volumes. Discrete Comput. Geom. 43 (2010), 841-854. MR2610473 Zbl 1204.52016 · Zbl 1204.52016
[3] A. U. Ashraf, An alternate approach to volumes of matroid polytopes. Preprint 2018, arXIV:1812.09373
[4] M. Beck, S. Robins, Computing the continuous discretely. Springer 2015. MR3410115 Zbl 1339.52002 · Zbl 1339.52002
[5] H. Bidkhori, Lattice path matroid polytopes. Preprint 2012, arXiv:1212.5705v1
[6] J. Bonin, A. de Mier, M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials. J. Combin. Theory Ser. A 104 (2003), 63-94. MR2018421 Zbl 1031.05031 · Zbl 1031.05031
[7] P. J. Cameron, Finite geometries. In: Handbook of combinatorics, Vol. 1, 647-691, Elsevier, Amsterdam 1995. MR1373669 Zbl 0854.51003 · Zbl 0854.51003
[8] F. Castillo, F. Liu, Berline-Vergne valuation and generalized permutohedra. Discrete Comput. Geom. 60 (2018), 885-908. MR3869454 Zbl 1401.52024 · Zbl 1401.52024
[9] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial optimization. Wiley-Interscience 1998. MR1490579 Zbl 0909.90227 · Zbl 0909.90227
[10] J. A. De Loera, D. C. Haws, M. Köppe, Ehrhart polynomials of matroid polytopes and polymatroids. Discrete Comput. Geom. 42 (2009), 670-702. MR2556462 Zbl 1207.52015 · Zbl 1207.52015
[11] J. Edmonds, Submodular functions, matroids, and certain polyhedra. In: Combinatorial optimization—Eureka, you shrink!, volume 2570 of Lecture Notes in Comput. Sci., 11-26, Springer 2003. MR2163945 Zbl 1024.90054 · Zbl 1024.90054
[12] E. Ehrhart, Sur les polyèdres rationnels homothétiques à \(n\) dimensions. C. R. Acad. Sci. Paris 254 (1962), 616-618. MR130860 Zbl 0100.27601 · Zbl 0100.27601
[13] N. J. Fan, Y. Li, On the Ehrhart polynomial of Schubert matroids. To appear in Discrete Comput. Geom. (2023).
[14] E. M. Feichtner, B. Sturmfels, Matroid polytopes, nested sets and Bergman fans. Port. Math. (N.S.) 62 (2005), 437-468. MR2191630 Zbl 1092.52006 · Zbl 1092.52006
[15] L. Ferroni, Hypersimplices are Ehrhart positive. J. Combin. Theory Ser. A 178 (2021), Paper No. 105365, 13 pages. MR4179055 Zbl 1459.52010 · Zbl 1459.52010
[16] L. Ferroni, Matroids are not Ehrhart positive. Adv. Math. 402 (2022), Paper No. 108337, 27 pages. MR4396506 Zbl 1487.52022 · Zbl 1487.52022
[17] L. Ferroni, On the Ehrhart polynomial of minimal matroids. Discrete Comput. Geom. 68 (2022), 255-273. MR4430288 Zbl 1490.05026 · Zbl 1490.05026
[18] L. Ferroni, K. Jochemko, B. Schröter, Ehrhart polynomials of rank two matroids. Adv. in Appl. Math. 141 (2022), Paper No. 102410, 26 pages. MR4461609 Zbl 1496.52016 · Zbl 1496.52016
[19] L. Ferroni, D. McGinnis, Lattice points in slices of prisms. Preprint 2022, arXiv:2202.11808
[20] L. Ferroni, G. Nasr, L. Vecchi, Stressed hyperplanes and Kazhdan-Lusztig gamma-positivity for matroids. To appear in Int. Math. Res. Not. 2023, 60 pages.
[21] L. Ferroni, B. Schröter, Valuative invariants for large classes of matroids. Preprint 2022, arXiv:2208.04893
[22] S. Fujishige, Submodular functions and optimization, volume 58 of Annals of Discrete Mathematics. Elsevier, Amsterdam 2005. MR2171629 Zbl 1119.90044 · Zbl 1119.90044
[23] I. M. Gel’cprime fand, R. M. Goresky, R. D. MacPherson, V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells. Adv. in Math. 63 (1987), 301-316. MR877789 Zbl 0622.57014 · Zbl 0622.57014
[24] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics. Addison-Wesley, Reading, MA 1994. MR1397498 Zbl 0836.00001 · Zbl 0836.00001
[25] B. Grünbaum, Convex polytopes. Springer 2003. MR1976856 Zbl 1033.52001 · Zbl 1024.52001
[26] S. Herrmann, M. Joswig, Splitting polytopes. Münster J. Math. 1 (2008), 109-141. MR2502496 Zbl 1159.52016 · Zbl 1159.52016
[27] M. Joswig, B. Schröter, Matroids from hypersimplex splits. J. Combin. Theory Ser. A 151 (2017), 254-284. MR3663497 Zbl 1366.05024 · Zbl 1366.05024
[28] M. Katzman, The Hilbert series of algebras of the Veronese type. Comm. Algebra 33 (2005), 1141-1146. MR2136691 Zbl 1107.13003 · Zbl 1107.13003
[29] S. Kim, Flag enumerations of matroid base polytopes. J. Combin. Theory Ser. A 117 (2010), 928-942. MR2652103 Zbl 1228.05112 · Zbl 1228.05112
[30] K. Knauer, L. Martínez-Sandoval, J. L. Ramírez Alfonsín, On lattice path matroid polytopes: integer points and Ehrhart polynomial. Discrete Comput. Geom. 60 (2018), 698-719. MR3849147 Zbl 1494.52014 · Zbl 1494.52014
[31] A. Knutson, T. Lam, D. E. Speyer, Positroid varieties: juggling and geometry. Compos. Math. 149 (2013), 1710-1752. MR3123307 Zbl 1330.14086 · Zbl 1330.14086
[32] F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes. II. North-Holland 1977. MR0465510 Zbl 0369.94008 · Zbl 0369.94008
[33] D. Mayhew, M. Newman, D. Welsh, G. Whittle, On the asymptotic proportion of connected matroids. European J. Combin. 32 (2011), 882-890. MR2821559 Zbl 1244.05047 · Zbl 1244.05047
[34] S. Oh, Positroids and Schubert matroids. J. Combin. Theory Ser. A 118 (2011), 2426-2435. MR2834184 Zbl 1231.05061 · Zbl 1231.05061
[35] J. Oxley, Matroid theory. Oxford Univ. Press 2011. MR2849819 Zbl 1254.05002 · Zbl 1254.05002
[36] R. Pendavingh, J. van der Pol, On the number of matroids compared to the number of sparse paving matroids. Electron. J. Combin. 22 (2015), Paper 2.51, 17 pages. MR3367294 Zbl 1327.05056 · Zbl 1327.05056
[37] A. Postnikov, Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 2009, issue 6, 1026-1106. MR2487491 Zbl 1162.52007 · Zbl 1162.52007
[38] A. Postnikov, V. Reiner, L. Williams, Faces of generalized permutohedra. Doc. Math. 13 (2008), 207-273. MR2520477 Zbl 1167.05005 · Zbl 1167.05005
[39] N. Sloane, The On-Line Encyclopedia of Integer Sequences. http://oeis.org · Zbl 1044.11108
[40] R. P. Stanley, Enumerative combinatorics. Volume 1. Cambridge Univ. Press 2012. MR2868112 Zbl 1247.05003 · Zbl 1247.05003
[41] W. A. Stein, et al., Sage Mathematics Software (Version 9.3), 2021. www.sagemath.org
[42] D. J. A. Welsh, Matroid theory. Academic Press 1976. MR0427112 Zbl 0343.05002 · Zbl 0343.05002
[43] G. M. Ziegler, Lectures on polytopes. Springer 1995. MR1311028 Zbl 0823.52002 · Zbl 0823.52002
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.