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

, 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 (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...

Cartesian coordinates A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in t ...

. That is, it is a polytope that equals the

convex hull In geometry, the convex hull or 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 point In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid ...

s. 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 In mathematics, the permutohedron of order ''n'' is an (''n'' − 1)-dimensional polytope embedded in an ''n''-dimensional space. Its vertex coordinates (labels) are the permutations of the first ''n'' natural numbers. The edges ident ...

has vertices whose coordinates are obtained by applying all possible permutations to the vector

(1,2,...,n)

. An

associahedron In mathematics, an associahedron is an -dimensional convex polytope in which each vertex corresponds to a way of correctly inserting opening and closing parentheses in a string of letters, and the edges correspond to single application of ...

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 are represented by linear function#As a polynomial function, li ...

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 criterion, from some set of available alternatives. It is generally divided into two subfi ...

, convex polytopes are often described by a system of

linear inequalities Linearity is the property of a mathematical relationship (''function (mathematics), function'') that can be graph of a function, graphically represented as a straight Line (geometry), line. Linearity is closely related to ''Proportionality (mat ...

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 Constraint satisfaction problem, feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programmin ...

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

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

order polytope In mathematics, the order polytope of a finite partially ordered set is a convex polytope defined from the set. The points of the order polytope are the monotonic functions from the given set to the unit interval, its vertices correspond to the uppe ...

of any

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

, 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 mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

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

, 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 of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

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 (complexity), complement is in the complexity class NP (complexity), NP. The class can be defined as follows: ...

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

coNP-complete In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial ...

Related objects

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

volume Volume is a measure of occupied 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). The de ...

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

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

, 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, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...

, an important instance of lattice polytopes called the

Newton polytope In mathematics, the Newton polytope is an integral polytope associated with a multivariate polynomial. It can be used to analyze the polynomial's behavior when specific variables are considered negligible relative to the others. Specifically, give ...

s are the convex hulls of vectors representing the exponents of each variable in the terms of a

polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...

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

, 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