  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 $n\geq 19$ there exist connected
matroids on $n$ elements that are not Ehrhart positive. Also, we prove that for
every $k\geq 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.
