Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem

The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [Combinatorica, 37 (2017), pp. 313--332] 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 ${R}^n$. They show that there exists a number $c(n,k)$ such that any polyhedron in $\mathbb{R}^n$ 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(k)2^n$. In this paper, we improve the bound asymptotically to be sublinear in $k$, that is, $c(n,k) = o(k) 2^n$. We also provide lower bounds on $c(n,k)$, along with other structural results. For dimension n=2, our upper and lower bounds match to within a constant factor.