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. Lastly, we establish the connection between SCR and the notion of supernormality.

## Citation

University of Washington Department of Mathematics Box 354350 Seattle, WA 98195-4350