Matroids are not Ehrhart positive

Abstract

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 (2007) and of generalized permutohedra by Castillo and Liu (2015). We prove constructively that for every $n\ge 19$ there exist connected matroids on $n$ elements that are not Ehrhart positive. Also, we prove that for every $k\ge 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.

arXiv comment22 pages, final version. Accepted in Advances in Mathematics

References in corpus (9)

• Matroid polytopes, nested sets and Bergman fans
• Valuative invariants for polymatroids
• Matroids from hypersimplex splits
• Ehrhart polynomials of matroid polytopes and polymatroids
• On the Ehrhart Polynomial of Minimal Matroids
• Hypersimplices are Ehrhart Positive
• Ehrhart polynomials of rank two matroids
• Stanley's non-Ehrhart-positive order polytopes
• Integer point enumeration on independence polytopes and half-open hypersimplices

Cited by in corpus (7)

• Valuative invariants for large classes of matroids
• Stressed hyperplanes and Kazhdan-Lusztig gamma-positivity for matroids
• Ehrhart polynomials of rank two matroids
• Matroid relaxations and Kazhdan-Lusztig non-degeneracy
• Hodge Theory for Polymatroids
• Lattice points in slices of prisms
• Restricted Birkhoff polytopes and Ehrhart period collapse