On integer points in polyhedra: A lower bound

DOI10.1007/BF01204716MaRDI QIDQ1196682zbMATH OpenFDO

Authors Imre Bárány, Roger Howe, László Lovász

Publication date 16 January 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01204716

zbMATH Keywords

latticespolytopesrational polytopes

Mathematics Subject Classification ID

Lattices and convex bodies (number-theoretic aspects) (11H06) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Review text

For a polyhedron \(P\subset\mathbb{R}^ n\) let \(P_ I\) denote the convex hull of integer points in \(P\). It is known that \(P_ I\) can have at most \(O(\varphi^{n-1})\) vertices if \(P\) is a rational polyhedron with size \(\varphi\). Here the size of a rational polyhedron is the sum of the sizes of the defining inequalities, measured by the encoding lengths as binary strings. The authors give an example which shows that \(P_ I\) can have as many as \(\Omega(\varphi^{n-1})\) vertices.

Recommendations

• On integer points in polyhedra
• scientific article; zbMATH DE number 2068095
• scientific article; zbMATH DE number 942482
• Some estimates for the number of vertices of integer polyhedra
• Upper and lower bound results on the convex hull of integer points in polyhedra

Cites work

• scientific article; zbMATH DE number 3968699 (Why is no real title available?)
• scientific article; zbMATH DE number 4083375 (Why is no real title available?)
• scientific article; zbMATH DE number 3735554 (Why is no real title available?)
• scientific article; zbMATH DE number 3233758 (Why is no real title available?)
• On integer points in polyhedra
• On the Unlimited Number of Faces in Integer Hulls of Linear Programs with a Single Constraint
• The vertices of the knapsack polytope

Cited in

(19)

• On integer points in polyhedra
• On the maximal number of edges of convex digital polygons included into an m m-grid
• Note on the complexity of the mixed-integer hull of a polyhedron
• On the number of integer points in translated and expanded polyhedra
• About the decidability of polyhedral separability in the lattice \(\mathbb {Z}^d\). Recognizing digital polyhedra with a prescribed number of faces
• Approximation of convex sets by polytopes
• Some estimates for the number of vertices of integer polyhedra
• Polytope Volume Computation
• On the number of irreducible points in polyhedra
• Random points and lattice points in convex bodies
• Upper and lower bound results on the convex hull of integer points in polyhedra
• scientific article; zbMATH DE number 2068095 (Why is no real title available?)
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• scientific article; zbMATH DE number 942482 (Why is no real title available?)
• Enumerating integer points in polytopes with bounded subdeterminants
• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• On the integer points in a lattice polytope: \(n\)-fold Minkowski sum and boundary
• On the polyhedral complexity of the integer points in a hyperball
• Some theoretical challenges in digital geometry: a perspective

This page was built for publication: On integer points in polyhedra: A lower bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1196682)