# Integral Versions of Helly's Theorem

Thursday, November 13, 2014 - 10:30am - 10:55am

Keller 3-180

Jesus De Loera (University of California)

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 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.

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 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.

MSC Code:

58Dxx

Keywords: