Integral polytope

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 -dimensional regular simplex can be represented as an integer polytope in , the convex hull of the integer points for which one coordinate is one and the rest are zero. Another important type of integral simplex, the orthoscheme, can be formed as the convex hull of integer points whose coordinates begin with some number of consecutive ones followed by zeros in all remaining coordinates. The -dimensional unit cube in has as its vertices all integer points whose coordinates are zero or one. A permutahedron has vertices whose coordinates are obtained by applying all possible permutations to the vector . An associahedron in Loday's convex realization is also an integer polytope and a deformation of the permutahedron. 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.