Regular Matroids Have Polynomial Extension Complexity
Manuel Aprile, Samuel Fiorini · Padua Research Archive (University of Padova) · 2022
We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree polytope of a graph imply a O(n2) bound for the special case of (co)graphic matroids. However, the case of a general regular matroid was open, despite recent attempts. We also consider the extension complexity of circuit dominants of regularmatroids, for which we give a O(n2) bound.