The polytope of all matroids

• Luis Ferroni ^[1] ; Alex Fink ^[2]
  1. [1] University of Pisa

     University of Pisa

     Pisa, Italia

     
  2. [2] Queen Mary University of London

     Queen Mary University of London

     Reino Unido

     
• Localización: Selecta Mathematica, New Series, ISSN 1022-1824, Vol. 31, Nº. 5, 2025
• Idioma: inglés
• DOI: 10.1007/s00029-025-01103-z
• Enlaces
  • Texto completo
• Resumen

  • It is possible to write the indicator function of any matroid polytope as an integer combination of indicator functions of Schubert matroid polytopes. In this way, every matroid on n elements of rank r can be thought of as a lattice point in the space having a coordinate for each Schubert matroid on n elements of rank r. We study the convex hull of all these lattice points, with particular focus on the vertices, which come from the matroids we call extremal matroids. We show that several famous classes of matroids arise as faces of the polytopes, and in many cases we determine the dimension of this face explicitly. As an application, we show that there exist valuative invariants that attain non-negative values at all representable matroids, but fail to be non-negative in general.

• Referencias bibliográficas
  • 1. Ardila, F., Fink, A., Rincón, F.: Valuations for matroid polytope subdivisions. Canad. J. Math. 62(6), 1228–1245 (2010)
  • 2. Barvinok, A.: A course in convexity, Graduate Studies in Mathematics, vol. 54. American Mathematical Society, Providence, RI (2002)
  • 3. Bennett, M.K., Bogart, K.P., Bonin, J.E.: The geometry of dowling lattices. Adv. Math. 103(2), 131–161 (1994)
  • 4. Beke, C., Csáji, G.K., Csikvári, P., Pituk, S.: The merino-welsh conjecture is false for matroids. Adv. Math. 446, 109674 (2024)
  • 5. Bonin, J.E., de Mier, A.: Lattice path matroids: structural properties. European J. Combin. 27(5), 701–738 (2006)
  • 6. Braden, T., Huh, J., Matherne, J.P., Proudfoot, N., Wang, B.: A semi-small decomposition of the Chow ring of a matroid. Adv. Math. 409,...
  • 7. Bonin, J.E., Kung, J.P.S.: The G-invariant and catenary data of a matroid. Adv. in Appl. Math. 94, 39–70 (2018)
  • 8. Bérczi, K., Király, T., Schwarcz, T., Yamaguchi, Y., Yokoi, Y.: Hypergraph characterization of split matroids. J. Combin. Theory Ser. A...
  • 9. Bonin, J.E., Miller, W.P.: Characterizing combinatorial geometries by numerical invariants. European J. Combin. 20(8), 713–724 (1999)
  • 10. Bonin, J.E.: Characterizations of certain matroids by maximizing valuative invariants, arXiv e-prints (2025), arXiv:2507.14720
  • 11. Brylawski, T.H.: A combinatorial model for series-parallel networks. Trans. Amer. Math. Soc. 154, 1–22 (1971)
  • 12. Crapo, H.H., Rota, G.-C.: On the foundations of combinatorial theory: Combinatorial geometries, preliminary ed., The M.I.T. Press, Cambridge,...
  • 13. Derksen, H., Fink, A.: Valuative invariants for polymatroids. Adv. Math. 225(4), 1840–1892 (2010)
  • 14. Dinolt, G.W.: An extremal problem for non-separable matroids, Théorie des matroïdes (Rencontre Franco-Britannique, Brest, 1970), Lecture...
  • 15. De Loera, J.A., Haws, D.C., Köppe, M.: Ehrhart polynomials of matroid polytopes and polymatroids. Discrete Comput. Geom. 42(4), 670–702...
  • 16. Eur, C., Huh, J., Larson, M.: Stellahedral geometry of matroids. Forum Math. Pi 11, e24 (2023)
  • 17. Ferroni, L.: Matroids are not Ehrhart positive. Adv. Math. 402, 108337 (2022)
  • 18. Ferroni, L.: On the Ehrhart polynomial of minimal matroids. Discrete Comput. Geom. 68(1), 255–273 (2022)
  • 19. Ferroni, L.: Schubert matroids, delannoy paths, and speyer’s invariant. Comb. Theory 3(3), 13 (2023)
  • 20. Ferroni, L., Matherne, J.P., Stevens, M., Vecchi, L.: Hilbert-Poincaré series of matroid Chow rings and intersection cohomology. Adv....
  • 21. Ferroni, L., Schröter, B.: Valuative invariants for large classes of matroids. J. Lond. Math. Soc. (2) 110(3), e12984 (2024)
  • 22. Ferroni, L., Schröter, B.: Tutte polynomials of matroids as universal valuative invariants. Comb. Theory 5(2), 3 (2025)
  • 23. Greene, C.: A rank inequality for finite geometric lattices. J. Combinatorial Theory 9, 357–364 (1970)
  • 24. Hampe, S.: The intersection ring of matroids. J. Combin. Theory Ser. B 122, 578–614 (2017)
  • 25. Hanely, D., Martin, J.L., McGinnis, D., Miyata, D., Nasr, G.D., Vindas-Meléndez, A.R., Yin, M.: Ehrhart theory of paving and panhandle...
  • 26. Hoster, E.: The Chow and augmented Chow polynomials of uniform matroids, arXiv e-prints (2024), arXiv:2410.22329
  • 27. Hameister, T., Rao, S., Simpson, C.: Chow rings of vector space matroids. J. Comb. 12(1), 55–83 (2021)
  • 28. Joswig, M., Schröter, B.: Matroids from hypersimplex splits. J. Combin. Theory Ser. A 151, 254–284 (2017)
  • 29. Kung, P.S.J.: Curious characterizations of projective and affine geometries. Adv. in Appl. Math. 28(3– 4), 523–543 (2002). (Special issue...
  • 30. Kung, P.S.J.: Syzygies on Tutte polynomials of freedom matroids. Ann. Comb. 21(4), 605–628 (2017)
  • 31. Lee, M., Patel, A., Spink, H., Tseng, D.: Orbits in (Pr)n and equivariant quantum cohomology. Adv. Math. 362, 106951 (2020)
  • 32. Mayhew, D., Newman, M.,Welsh, D.,Whittle, G.: On the asymptotic proportion of connected matroids. European J. Combin. 32(6), 882–890 (2011)
  • 33. Mayhew, D., Royle, G.F.: Matroids with nine elements. J. Combin. Theory Ser. B 98(2), 415–431 (2008)
  • 34. Merino, C., Welsh, D.J.A.: Forests, colorings and acyclic orientations of the square lattice. Ann. Comb. 3(2–4), 417–429 (1999)
  • 35. Oxley, J.: Matroid theory, Oxford Graduate Texts in Mathematics, vol. 21, 2nd edn. Oxford University Press, Oxford (2011)
  • 36. Petersen, T.K.: Eulerian numbers, Birkhäuser Advanced Texts: Basler Lehrbücher. [Birkhäuser Advanced Texts: Basel Textbooks], Birkhäuser/Springer,...
  • 37. Postnikov, A., Reiner, V., Williams, L.: Faces of generalized permutohedra. Doc. Math. 13, 207–273 (2008)
  • 38. Pendavingh, R., van der Pol, J.: On the number of matroids compared to the number of sparse paving matroids. Electron. J. Combin. 22(2),...
  • 39. Stanley, R.P.: Enumerative combinatorics. Volume 1, second ed., Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University...
  • 40. Welsh, J.A.D.: Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, (1976)