Integral polytope

Four integral polytopes in three dimensions


Cube	Cuboctahedron	Octahedron	Truncated octahedron
(±1, ±1, ±1)	(0, ±1, ±1)	(0, 0, ±1)	(0, ±1, ±2)

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 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.

Examples

An $n$ -dimensional regular simplex can be represented as an integer polytope in $\mathbb {R} ^{n+1}$ , 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 $n$ -dimensional unit cube in $\mathbb {R} ^{n}$ 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 $(1,2,...,n)$ . An associahedron in Loday's convex realization is also an integer polytope and a deformation of the permutahedron.

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

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.^[6]

Related objects

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

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$ -fold product of the projective line.^{[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. For example, the polynomial $xy+2x^{2}+y^{5}+4$ has four terms, $xy$ with exponent vector (1,1), $2x^{2}$ with exponent vector (2,0), $y^{5}$ with exponent vector (0,5), and $4$ 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

^ Cornuéjols, Gérard (2001), Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 4, doi:10.1137/1.9780898717105, ISBN 0-89871-481-8, MR 1828452
^ 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
^ Stanley, Richard P. (1986), "Two poset polytopes", Discrete & Computational Geometry, 1 (1): 9–23, doi:10.1007/BF02187680, MR 0824105
^ Lovász, László (1986). Matching theory. North-Holland. pp. 269–274. ISBN 978-0-444-87916-5. OCLC 316569965.
^ Lovász, László (1986). Matching theory. North-Holland. pp. 274–281. ISBN 978-0-444-87916-5. OCLC 316569965.
^ 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
^ 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

[c-1] Cornuéjols, Gérard (2001), Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74, Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics (SIAM), p. 4, doi:10.1137/1.9780898717105, ISBN 0-89871-481-8, MR 1828452

[m-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

[s-3] Stanley, Richard P. (1986), "Two poset polytopes", Discrete & Computational Geometry, 1 (1): 9–23, doi:10.1007/BF02187680, MR 0824105

[4] Lovász, László (1986). Matching theory. North-Holland. pp. 269–274. ISBN 978-0-444-87916-5. OCLC 316569965.

[5] Lovász, László (1986). Matching theory. North-Holland. pp. 274–281. ISBN 978-0-444-87916-5. OCLC 316569965.

[dfz-6] 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

[b-7] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]