, the convex hull of the integer points for which one coordinate is one and the rest are zero.
[citation needed] 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.
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.
Some polyhedra arising from combinatorial optimization problems are automatically integral.
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.
[4] 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.
[5] These characterizations are of further interest in Edmonds' famous blossom algorithm used for finding such matchings in general graphs.
Therefore, testing integrality belongs to the complexity class coNP of problems for which a negative answer can be easily proven.
[6] Many of the important properties of an integral polytope, including its volume and number of vertices, is encoded by its Ehrhart polynomial.
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
[citation needed] 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.