There are matroid toric ideals without quadratic Gr\"obner bases

Our paper shows that if a matroid contains the Fano plane or its dual as a minor, then its toric ideal does not have any quadratic Gr\"obner basis. More than 25 years ago, Hibi, Herzog, and Sturmfels established a direct connection between the existence of quadratic Gr\"obner bases and regular unimodular flag triangulations. Our paper solves a famous question posed by Herzog and Hibi on a polyhedral reformulation for the existence of quadratic Gr\"obner bases: we show that the base polytopes of the Fano plane and its dual do not have regular unimodular flag triangulations which implies the main result on Gr\"obner bases. Our proof relies on several novel tools: a lemma that connects the $1$-skeleton of a lattice polytope to the lattice points in its dilations, an encoding with Boolean formulas and SAT solvers, and symmetry-breaking arguments.