Sublinear bounds for a quantitative Doignon-Bell-Scarf Theorem

Abstract

The recent paper "A quantitative Doignon-Bell-Scarf Theorem" by Aliev et al. generalizes the famous Doignon-Bell-Scarf Theorem on the existence of integer solutions to systems of linear inequalities. Their generalization examines the number of facets of a polyhedron that contains exactly k integer points in Rn. They show that there exists a number c(n,k) such that any polyhedron in Rn that contains exactly k integer points has a relaxation to at most c(n,k) of its inequalities that will define a new polyhedron with the same integer points. They prove that c(n,k)=O(k2n). In this paper, we improve the bound asymptotically to be sublinear in k. We also provide lower bounds on c(n,k), along with other structural results. For dimension n=2, our bounds are asymptotically tight to within a constant.