University of Washington
Title: The Small Chvatal Rank of an Integer Matrix
Given an integer matrix A and an integer vector b, we define the
small Chvatal rank (SCR) of the system Ax <= b to be the least number of
iterations of an iterated Hilbert basis construction to obtain all facet
normals of the integer hull (that is, the convex hull of the set of
integer solutions. Our procedure is a variation of the
Chvatal-Gomory procedure to compute integer hulls of polyhedra. The key
difference is that our procedure ignores the right-hand side vector b and
uses only the matrix A.
We prove that the SCR of Ax <= b is bounded above by the Chvatal rank
of Ax <= b and is hence finite. To justify the adjective "small", we
show that when n=2, SCR is at most one while Chvatal rank can
be arbitrarily high. For a family of examples from combinatorial
optimization, we prove that the SCR is one or two while the Chvatal rank
is known to be roughly log(n).
We next relate SCR to the notion of supernormality of a vector
configuration (specifically, the rows of A.) Supernormality is a
generalization of unimodularity and we exhibit an infinite family of
vector configurations arising from odd cycles that are supernormal but not
unimodular. This answers a question of Hosten, Maclagan and
Lastly, we provide lower bounds on SCR. We prove that when n >= 3, SCR
can be arbitrarily high and exponentially large in the input size. We also
prove that for polytopes contained in the d-dimensional unit cube, the SCR
can be at least d/2 - o(d) which is of the same order as the known
lower bounds on Chvatal rank for such systems. Our methods thus provide an
alternate way to compute lower bounds on Chvatal rank.
This project is joint work with Rekha Thomas.
...Back to the IMA postdoc seminar