Matroids are not Ehrhart positive

DOI10.1016/J.AIM.2022.108337MaRDI QIDQ2136552zbMATH OpenOpenAlexFDO

Authors Luis Ferroni

Publication date 11 May 2022

Published in Advances in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2105.04465

zbMATH Keywords

Ehrhart polynomialsgeneralized permutohedramatroid polytopespolymatroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

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

Recommendations

• An Erdős-Gallai theorem for matroids
• A note on nongraphic matroids
• Realizable but not strongly Euclidean oriented matroids
• Almost all matroids are nonrepresentable
• The Erdös-Pósa property for matroid circuits
• Euler and bipartite matroids
• Positroids and Schubert matroids
• On binary matroids not isomorphic to their base matroids
• Matroids are immune to Braess' paradox
• Matroids without adjoint

Cites work

• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• An extremal problem for non-separable matroids
• Berline-Vergne valuation and generalized permutohedra
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial Reciprocity Theorems
• Computing the Continuous Discretely
• Ehrhart polynomials of matroid polytopes and polymatroids
• Ehrhart polynomials with negative coefficients
• Faces of generalized permutohedra
• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 3472075 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Hypersimplices are Ehrhart positive
• Integer point enumeration on independence polytopes and half-open hypersimplices
• Log-concavity of Stirling numbers and unimodality of Stirling distributions
• Lower bounds for constant weight codes
• Matroid polytopes and their volumes
• Matroid polytopes, nested sets and Bergman fans
• Matroids from hypersimplex splits
• On positivity of Ehrhart polynomials
• On the asymptotic proportion of connected matroids
• On the number of matroids
• On the number of matroids compared to the number of sparse paving matroids
• On the Todd class of the permutohedral variety
• Permutohedra, Associahedra, and Beyond
• Some new distance-4 constant weight codes
• Stanley's non-Ehrhart-positive order polytopes
• Ternary paving matroids
• THE HILBERT SERIES OF ALGEBRAS OF THE VERONESE TYPE
• Upper bounds for constant-weight codes
• Valuations and Euler-Type Relations on Certain Classes of Convex Polytopes
• Valuative invariants for polymatroids

Cited in

(21)

• Ehrhart polynomials of matroid polytopes and polymatroids
• Integer point enumeration on independence polytopes and half-open hypersimplices
• Ehrhart polynomials of rank two matroids
• Hypersimplices are Ehrhart positive
• Matroid relaxations and Kazhdan-Lusztig non-degeneracy
• Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity
• Ehrhart theory of paving and panhandle matroids
• On the Ehrhart polynomial of Schubert matroids
• The Merino-Welsh conjecture is false for matroids
• Valuative invariants for large classes of matroids
• Ehrhart positivity for a certain class of panhandle matroids
• Restricted Birkhoff polytopes and Ehrhart period collapse
• Valuative invariants of Catalan matroids
• The Ehrhart polynomial of a matroid specializes to the -invariant
• The polytope of all matroids
• A regular unimodular triangulation of the matroid base polytope
• Partial permutohedra
• Lattice points in slices of prisms
• Ehrhart bounds for panhandle and paving matroids through enumeration of chain forests
• Partial permutohedra
• Skew shapes, Ehrhart positivity, and beyond

This page was built for publication: Matroids are not Ehrhart positive

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136552)