Open AccessOn integer points in polyhedra: A lower bound
Author(s) -
Imre Bárány,
Roger Howe,
László Lovász
Publication year - 1992
Publication title -
combinatorica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.106
H-Index - 58
eISSN - 1439-6912
pISSN - 0209-9683
DOI - 10.1007/bf01204716
Subject(s) - polyhedron , mathematics , combinatorics , convex hull , integer (computer science) , regular polygon , upper and lower bounds , unit (ring theory) , discrete mathematics , geometry , mathematical analysis , computer science , programming language , mathematics education
Given a polyhedronP?R 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 f. Here we give an example showing thatPI can have as many as O(?n-1) vertices. The construction uses the Dirichlet unit theorem.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom