In mathematics, in particular in the theory of polyhedra and polytopes, an extension of a polyhedron P is a polyhedron Q together with an affine or, more generally, projective map π mapping Q onto P.
Contents
Typically, given a polyhedron P, one asks what properties an extension of P must have. Of particular importance here is the extension complexity of P: the minimum number of facets of any polyhedron Q which participates in an extension of P.
History
Historically, questions about extensions first surfaced in combinatorial optimization, where extensions arise naturally from extended formulations.
A seminal work by Yannakakis connected extension complexity to various other notions in mathematics, in particular nonnegative rank of nonnegative matrices and communication complexity.
The notorious Matching Polytope
Much of the research in the theory of extensions is driven by a notorious problem about the Matching Polytope: Is the extension complexity of the convex hull of all matchings of a graph on n vertices bounded by a polynomial in n? (cf.)