In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points.Integral polytopes are also called lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.
An
n
Rn+1
n
Rn
(1,2,...,n)
In the context of linear programming and related problems in mathematical optimization, convex polytopes are often described by a system of linear inequalities that their points must obey. When a polytope is integral, linear programming can be used to solve integer programming problems for the given system of inequalities, a problem that can otherwise be more difficult.
Some polyhedra arising from combinatorial optimization problems are automatically integral. For instance, this is true of the order polytope of any partially ordered set, a polytope defined by pairwise inequalities between coordinates corresponding to comparable elements in the set. Another well-known polytope in combinatorial optimization is the matching polytope. Clearly, one seeks for finding matchings algorithmically and one technique is linear programming. The polytope described by the linear program upper bounding the sum of edges taken per vertex is integral in the case of bipartite graphs, that is, it exactly describes the matching polytope, while for general graphs it is non-integral.[1] Hence, for bipartite graphs, it suffices to solve the corresponding linear program to obtain a valid matching. For general graphs, however, there are two other characterizations of the matching polytope one of which makes use of the blossom inequality for odd subsets of vertices and hence allows to relax the integer program to a linear program while still obtaining valid matchings.[2] These characterizations are of further interest in Edmonds' famous blossom algorithm used for finding such matchings in general graphs.
For a polytope described by linear inequalities, when the polytope is non-integral, one can prove its non-integrality by finding a vertex whose coordinates are not integers. Such a vertex can be described combinatorially by specifying a subset of inequalities that, when turned into a system of linear equations, have a unique solution, and verifying that this solution point obeys all of the other inequalities. Therefore, testing integrality belongs to the complexity class coNP of problems for which a negative answer can be easily proven. More specifically, it is coNP-complete.
Many of the important properties of an integral polytope, including its volume and number of vertices, is encoded by its Ehrhart polynomial.
Integral polytopes are prominently featured in the theory of toric varieties, where they correspond to polarized projective toric varieties.For instance, the toric variety corresponding to a simplex is a projective space. The toric variety corresponding to a unit cube is the Segre embedding of the
n
In algebraic geometry, an important instance of lattice polytopes called the Newton polytopes are the convex hulls of vectors representing the exponents of each variable in the terms of a polynomial. For example, the polynomial
xy+2x2+y5+4
xy
2x2
y5
4