Abstract
Given a polyhedronP⊂ℝ we writePI for the convex hull of the integral points inP. It is known thatPI can have at most135-2 vertices ifP is a rational polyhedron with size φ. Here we give an example showing thatPI can have as many as Ω(ϕn−1) vertices. The construction uses the Dirichlet unit theorem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Z. I. Borevich, andI. R. Safarevich:Number theory, Academic Press, New York and London, 1966.
W. Cook, M. Hartmann, R. Kannan, andC. McDiarmid: On integer points in polyhedra,Combinatorica12 (1992), 27–37.
A. C. Hayes, andD. G. Larman: The vertices of the knapsack polytope,Discrete Applied Math.6 (1983), 135–138.
S. Lang:Algebraic number theory, Graduate Texts in Mathematics 110, Springer Verlag, New York etc., 1986.
D. Morgan: Personal communication, 1989.
D. S. Rubin: On the unlimited number of faces in integer hulls of linear programs with a single constraint,Operations Research18 (1970), 940–946.
A. Schrijver:Theory of linear and integer programming, Wiley, Chichester, 1987.
V. N. Shevchenko: On the number of extreme points in integer programming,Kibernetika2 (1981), 133–134.
Author information
Authors and Affiliations
Corresponding author
Additional information
The results of the paper were obtained while this author was visiting the Cowles Foundation at Yale University