Georgia Institute of Technology College of Sciences

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions on systems linear inequalities. The purpose of this paper is to present the following ``weighted'' generalization: Given an integer k, we prove that there exists a constant c(k,n), depending only on the dimension n and k, such that if a polyhedron {x : Ax <= b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. We work on both upper and lower bounds for this constant. This is joint work with Quentin Louveaux, Iskander Aliev and Robert Bassett.