Extension of a polyhedron
Encyclopedia
In mathematics
, in particular in the theory of polyhedra
and polytope
s, an extension of a polyhedron P is a polyhedron
Q together with an affine
or, more generally, projective map π mapping Q onto P.
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.
, 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
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, in particular in the theory of polyhedra
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
and polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
s, an extension of a polyhedron P is a polyhedron
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
Q together with an affine
Affine transformation
In geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...
or, more generally, projective map π mapping Q onto P.
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
Facet (mathematics)
A facet of a simplicial complex is a maximal simplex.In the general theory of polyhedra and polytopes, two conflicting meanings are currently jostling for acceptability:...
of any polyhedron Q which participates in an extension of P.
History
Historically, questions about extensions first surfaced in combinatorial optimizationCombinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
, 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
Nonnegative rank (linear algebra)
In linear algebra, the nonnegative rank of a nonnegative matrix is a concept similar to the usual linear rank of a real matrix, but adding the requirement that certain coefficients and entries of vectors/matrices have to be nonnegative....
and communication complexity
Communication complexity
The notion of communication complexity was introduced by Yao in 1979,who investigated the following problem involving two separated parties . Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them to compute a certain function f with the least amount of...
.