Regular matroids have polynomial extension complexity

Manuel Aprile, Samuel Fiorini

We prove that the extension complexity of the independence polytope of every regular matroid on $n$ elements is $O(n^6)$. Past results of Wong and Martin on extended formulations o…