Matroids are not Ehrhart positive

DOI10.1016/J.AIM.2022.108337zbMATH Open1487.52022arXiv2105.04465OpenAlexW3161963287MaRDI QIDQ2136552FDOQ2136552

Luis Ferroni

Publication date: 11 May 2022

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• On the Ehrhart polynomial of Schubert matroids
• Ehrhart theory of paving and panhandle matroids
• Valuative invariants for large classes of matroids
• Ehrhart polynomials of rank two matroids
• Matroid relaxations and Kazhdan-Lusztig non-degeneracy
• The Merino-Welsh conjecture is false for matroids
• Restricted Birkhoff polytopes and Ehrhart period collapse
• Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity

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)