CFDP 917

On Integer Points in Polyhedra: A Lower Bound


Publication Date: June 1989

Pages: 12


Given a polyhedron P subset Rn we write PI for the convex hull of the integral points in P. It is known that PI can have at most O(ϕn-1) vertices if P is a rational polyhedron with size ϕ. Here we give an example showing that PI can have as many as Ω(ϕn-1) vertices. The construction uses the Dirichlet unit theorem.


Polyhedra; integral points, Dirichlet unit theorem

JEL Classification Codes:  213


Published in Combinatorica (June 1992), 12(2): 135-142 [DOI]