In geometry and

polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral co ...

, an integral polytope is a

convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

whose vertices all have

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

Cartesian coordinates In geometry, a Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of real numbers called ''coordinates'', which are the signed distances to the point from two fixed perpendicular o ...

. That is, it is a polytope that equals the

convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

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.

Examples

n

-dimensional regular

simplex In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...

can be represented as an integer polytope in

\mathbb^

, 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 A unit cube, more formally a cube of side 1, is a cube whose sides are 1 unit long.. See in particulap. 671. The volume of a 3-dimensional unit cube is 1 cubic unit, and its total surface area is 6 square units.. Unit hypercube The term '' ...

\mathbb^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 Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

and related problems in

mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...

, 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 An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...

problems for the given system of inequalities, a problem that can otherwise be more difficult. Some polyhedra arising from

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...

problems are automatically integral. For instance, this is true of the order polytope of any

partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...

, 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 In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the the ...

. 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 graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s, that is, it exactly describes the matching polytope, while for general graphs it is non-integral. 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. 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 In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variable (math), variables. For example, : \begin 3x+2y-z=1\\ 2x-2y+4z=-2\\ -x+\fracy-z=0 \end is a system of th ...

, have a unique solution, and verifying that this solution point obeys all of the other inequalities. Therefore, testing integrality belongs to the

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

coNP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and o ...

of problems for which a negative answer can be easily proven. More specifically, it is coNP-complete.

Related objects

Many of the important properties of an integral polytope, including its

volume Volume is a measure of regions in three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch) ...

and number of vertices, is encoded by its

Ehrhart polynomial In mathematics, an integral polytope has an associated Ehrhart polynomial that encodes the relationship between the volume of a polytope and the number of integer points the polytope contains. The theory of Ehrhart polynomials can be seen as a hi ...

. Integral polytopes are prominently featured in the theory of

toric varieties In algebraic geometry, a toric variety or torus embedding is an algebraic variety containing an algebraic torus as an open dense subset, such that the action of the torus on itself extends to the whole variety. Some authors also require it to be ...

, where they correspond to polarized projective toric varieties. For instance, the toric variety corresponding to a

is a

projective space In mathematics, the concept of a projective space originated from the visual effect of perspective, where parallel lines seem to meet ''at infinity''. A projective space may thus be viewed as the extension of a Euclidean space, or, more generally ...

. The toric variety corresponding to a

is the

Segre embedding In mathematics, the Segre embedding is used in projective geometry to consider the cartesian product (of sets) of two projective spaces as a projective variety. It is named after Corrado Segre. Definition The Segre map may be defined as the map : ...

of the

n

-fold product of the projective line. In

algebraic geometry Algebraic geometry is a branch of mathematics which uses abstract algebraic techniques, mainly from commutative algebra, to solve geometry, geometrical problems. Classically, it studies zero of a function, zeros of multivariate polynomials; th ...

, 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 In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

. 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

{{reflist, refs= {{citation , last = Barvinok , first = A. I. , doi = 10.1007/BF02574364 , issue = 1 , journal = Discrete & Computational Geometry , mr = 1280575 , pages = 35–48 , title = Computing the Ehrhart polynomial of a convex lattice polytope , volume = 12 , year = 1994, doi-access = free {{citation , last = Cornuéjols , first = Gérard , doi = 10.1137/1.9780898717105 , isbn = 0-89871-481-8 , location = Philadelphia, Pennsylvania , mr = 1828452 , page = 4 , publisher = Society for Industrial and Applied Mathematics (SIAM) , series = CBMS-NSF Regional Conference Series in Applied Mathematics , title = Combinatorial Optimization: Packing and Covering , url = https://books.google.com/books?id=npf_fv25vo8C&pg=PA4 , volume = 74 , year = 2001 {{citation , last1 = Ding , first1 = Guoli , last2 = Feng , first2 = Li , last3 = Zang , first3 = Wenan , doi = 10.1007/s10107-007-0103-y , issue = 2 , journal = Mathematical Programming, Series A , mr = 2393045 , pages = 321–334 , title = The complexity of recognizing linear systems with certain integrality properties , volume = 114 , year = 2008, hdl = 10722/58972 , hdl-access = free {{citation , last = Murota , first = Kazuo , doi = 10.1137/1.9780898718508 , isbn = 0-89871-540-7 , location = Philadelphia, Pennsylvania , mr = 1997998 , page = 90 , publisher = Society for Industrial and Applied Mathematics (SIAM) , series = SIAM Monographs on Discrete Mathematics and Applications , title = Discrete convex analysis , url = https://books.google.com/books?id=LeRlixEjy3EC&pg=PA90 , year = 2003, hdl = 2433/149564 , hdl-access = free {{citation , last = Stanley , first = Richard P. , doi = 10.1007/BF02187680 , issue = 1 , journal =

Discrete & Computational Geometry '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational ...

, mr = 824105 , pages = 9–23 , title = Two poset polytopes , volume = 1 , year = 1986, doi-access = free Polytopes

Examples

In optimization

Computational complexity

Related objects

See also

References