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 polynomialspolymatroidsmatroid polytopesgeneralized permutohedra

Mathematics Subject Classification ID

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) Combinatorial aspects of matroids and geometric lattices (05B35)

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

• 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?)
• 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 Reciprocity Theorems
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing the Continuous Discretely
• Ehrhart polynomials of matroid polytopes and polymatroids
• Ehrhart polynomials with negative coefficients
• Faces of generalized permutohedra
• 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 Todd class of the permutohedral variety
• 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
• Permutohedra, Associahedra, and Beyond
• Some new distance-4 constant weight codes
• Stanley's non-Ehrhart-positive order polytopes
• THE HILBERT SERIES OF ALGEBRAS OF THE VERONESE TYPE
• Ternary paving matroids
• Upper bounds for constant-weight codes
• Valuations and Euler-Type Relations on Certain Classes of Convex Polytopes
• Valuative invariants for polymatroids

Cited in

(12)

• On the Ehrhart polynomial of Schubert matroids
• Ehrhart theory of paving and panhandle matroids
• Valuative invariants for large classes of matroids
• Integer point enumeration on independence polytopes and half-open hypersimplices
• Hypersimplices are Ehrhart positive
• Ehrhart polynomials of rank two matroids
• Matroid relaxations and Kazhdan-Lusztig non-degeneracy
• Ehrhart positivity for a certain class of panhandle matroids
• The Merino-Welsh conjecture is false for matroids
• Restricted Birkhoff polytopes and Ehrhart period collapse
• Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity
• Ehrhart polynomials of matroid polytopes and polymatroids

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)