Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations

Robert Hildebrand, Robert Weismantel, Rico Zenklusen

We prove that any mixed-integer linear extended formulation for the matching polytope of the complete graph on $n$ vertices, with a polynomial number of constraints, requires $Ω(\s…