Campuses:

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.
MSC Code: 
58Dxx