Videos

Integral Versions of Helly's Theorem

Presenter
November 13, 2014
Keywords:
  • Integral versions
MSC:
  • 58Dxx
Abstract
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.