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.