The perfect matching polytope has exponential extension complexity

You need to know: Graph, complete n-vertex graph, notation for the number of elements in finite set S, Euclidean space , polytope, convex hull.

Background: Let be a graph with vertex set V and edge set E.  A set of edges of G is called matching if no two edges in M share a common vertex. A matching is called perfect if . Let us enumerate the edges of G from to . For any subset , let be the characteristic vector of S, that is, i-th coordinate of is if the edge number i belongs to S, and otherwise. The perfect matching polytope in graph G is the convex hull of all characteristic vectors of perfect matchings in G. An extension complexity of any polytope P is the smallest number of inequalities necessary to describe a higher-dimensional polytope Q that can be linearly projected on P.

The Theorem: On 11th November 2013, Thomas Rothvoss submitted to arxiv a paper in which he proved that for all even n, the extension complexity of the perfect matching polytope in the complete n-vertex graph is at least for some constant c.

Short context: A popular method in combinatorial optimization is to express polytopes P, 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. The extension complexity describes the minimal size of linear program needed for this method. The Theorem states that the perfect matching polytope has exponential extension complexity. It resolves a long-standing open question in the field. This is a rare example when we have a proof that some powerful method (in this case linear programming) cannot efficiently solve a problem.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems