Fall 2007 Seminar Series

DATE: September 27
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
Rekha Thomas

TITLE
Small Chvatal Rank

ABSTRACT
We introduce a new measure of complexity of integer hulls of rational polyhedra called the small Chvatal rank (SCR). The SCR of an integer matrix A is the number of rounds of a Hilbert basis procedure needed to generate all normals of a sufficient set of inequalities to cut out the integer hulls of all polyhedra {x: Ax <= b} as b varies. The SCR of A is bounded above by the Chvatal rank of A and is hence finite. We exhibit examples where SCR is much smaller than Chvatal rank. When the number of columns of A is at least three, we show that SCR can be arbitrarily high proving that, in general, SCR is not a function of dimension alone. For polytopes in the unit cube we provide a lower bound for SCR that is comparable to the known lower bounds for Chvatal rank in that situation. We use the notion of supernormality to completely characterize matrices for which SCR equals zero.