Tristram Bogart
University of Washington

Title: The Small Chvatal Rank of an Integer Matrix
Abstract: 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 Sturmfels.
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 page...