COWLES FOUNDATION FOR RESEARCH IN ECONOMICS
AT YALE UNIVERSITY

Box 208281
New Haven, CT 06520-8281

COWLES FOUNDATION DISCUSSION PAPER NO. 917

"On Integer Points in Polyhedra: A Lower Bound"

Imre Barany, Roger Howe and Laszlo Lovasz

May 1989

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

Keywords: Polyhedra; integral points, Dirichlet unit theorem

JE Classification: 213