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 c ...
, an integral polytope is a
convex polytope 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 i ...
. That is, it is a polytope that equals the
convex hull 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
An
-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
, 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
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 '' ...
in
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
. 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 ...
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 relationships. Linear programming is ...
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 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 combi ...
problems are automatically integral. For instance, this is true of the
order polytope 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. A poset consists of a set together with a binar ...
, 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 ar ...
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, 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 ...
coNP 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). Th ...
and number of vertices, is encoded by its
Ehrhart polynomial.
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
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 ...
is a
projective space. The toric variety corresponding to a
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 '' ...
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
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 ex ...
. 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.
See also
*
Reeve tetrahedron
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 ge ...
, mr = 824105
, pages = 9–23
, title = Two poset polytopes
, volume = 1
, year = 1986, doi-access = free
Polytopes