On Integer Points in Polyhedra: A Lower Bound

Given a polyhedron we write P(I) for the convex hull of the integral points in P. It is know 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.

MoreLess

Year of publication:	1989-05
Authors:	Barany, Imre ; Howe, Roger ; Lovasz, Laszlo
Institutions:	Cowles Foundation for Research in Economics, Yale University
Subject:	Polyhedra \| integral points \| Dirichlet unit theorem

More details

Extent:	application/pdf
Series:	Cowles Foundation Discussion Papers.
Type of publication:	Book / Working Paper
Notes:	Published in Combinatorica (1992), 12(2): 135-142 The price is None Number 917 12 pages
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005593641