Integral polytope

In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates.[1] That is, it is a polytope that equals the convex hull of its integer points.[2] Integral polytopes may also be called convex 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.

Cube Cuboctahedron Octahedron Truncated
octahedron
(±1, ±1, ±1) (0, ±1, ±1) (0, 0, ±1) (0, ±1, ±2)
Four integral polytopes in three dimensions

Examples

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.

In optimization

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.[3]

Computational complexity

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.[4]

Many of the important properties of an integral polytope, including its volume and number of vertices, is encoded by its Ehrhart polynomial.[5]

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 -fold product of the projective line.

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 has four terms, with exponent vector (1,1), with exponent vector (2,0), with exponent vector (0,5), and with exponent vector (0,0). Its Newton polytope is the convex hull of the four points (1,1), (2,0), (0,5), and (0,0). This hull is an integral triangle with the point (1,1) interior to the triangle and the other three points as its vertices.

References
  1. Cornuéjols, Gérard (2001), Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics, 74, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 4, doi:10.1137/1.9780898717105, ISBN 0-89871-481-8, MR 1828452
  2. Murota, Kazuo (2003), Discrete convex analysis, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 90, doi:10.1137/1.9780898718508, hdl:2433/149564, ISBN 0-89871-540-7, MR 1997998
  3. Stanley, Richard P. (1986), "Two poset polytopes", Discrete & Computational Geometry, 1 (1): 9–23, doi:10.1007/BF02187680, MR 0824105
  4. Ding, Guoli; Feng, Li; Zang, Wenan (2008), "The complexity of recognizing linear systems with certain integrality properties", Mathematical Programming, Series A, 114 (2): 321–334, doi:10.1007/s10107-007-0103-y, hdl:10722/58972, MR 2393045
  5. Barvinok, A. I. (1994), "Computing the Ehrhart polynomial of a convex lattice polytope", Discrete & Computational Geometry, 12 (1): 35–48, doi:10.1007/BF02574364, MR 1280575
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.