The Matching Polytope has Exponential Extension Complexity

<jats:p> A popular method in combinatorial optimization is to express polytopes <jats:italic>P</jats:italic> , which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so-called <jats:italic>extension complexity</jats:italic> , which for a polytope <jats:italic>P</jats:italic> denotes the smallest number of inequalities necessary to describe a higher-dimensional polytope <jats:italic>Q</jats:italic> that can be linearly projected on <jats:italic>P</jats:italic> . </jats:p> <jats:p> However, the central question in this field remained wide open: can the <jats:italic>perfect matching polytope</jats:italic> be written as an LP with polynomially many constraints? </jats:p> <jats:p> We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete <jats:italic>n</jats:italic> -node graph is 2 <jats:sup> Ω ( <jats:italic>n</jats:italic> ) </jats:sup> . By a known reduction, this also improves the lower bound on the extension complexity for the TSP polytope from 2 <jats:sup> Ω (√ <jats:italic>n</jats:italic> ) </jats:sup> to 2 <jats:sup> Ω ( <jats:italic>n</jats:italic> ) </jats:sup> . </jats:p>