CFDP 917

On Integer Points in Polyhedra: A Lower Bound

Author(s): 

Publication Date: June 1989

Pages: 12

Abstract: 

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.

Keywords: 

Polyhedra; integral points, Dirichlet unit theorem

JEL Classification Codes:  213

Note: 

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