|
|||||
|
|
On integer points in polyhedra: A lower bound |
|
| Authors: | Imre Bárány Roger Howe László Lovász |
| Institution: | (1) Mathematical Institute, Pf. 127, 1364 Budapest, Hungary;(2) Department of Mathematics, Yale University, 06520 New Haven, CT, U. S. A.;(3) Department of Computer Science, Eötvös University, Múzeum krt. 6-8, 1088 Budapest, Hungary;(4) Princeton University, 08544 Princeton, NJ, U. S. A. |
| Abstract: | Given a polyhedronP  we writeP
I
for the convex hull of the integral points inP. It is known thatP
I
can have at most135-2 vertices ifP is a rational polyhedron with size  . Here we give an example showing thatP
I
can have as many as  (
n–1) vertices. The construction uses the Dirichlet unit theorem.The results of the paper were obtained while this author was visiting the Cowles Foundation at Yale University |
| Keywords: | 52 C 07 11 H 06 |
| 本文献已被 SpringerLink 等数据库收录！ | |