Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The Small Chv{\'a}tal Rank of an Integer Matrix

Algebra & Discrete Mathematics

Speaker: Tristram Bogart, U. Washington
Location: 1147 MSB
Start time: Wed, Nov 15 2006, 12:10PM

Given a matrix $A \in {\mathbb Z^{m \times n}}$ and a vector ${\bf b} \in \ZZ^m$, we define the {\em small Chv{\'a}tal rank} (SCR) of the system $A{\bf x} \leq {\bf b}$ to be the least number of iterations of an iterated Hilbert basis construction, called {\em iterated basis normalization} (IBN), to obtain all facet normals of the integer hull $Q_\bb^I$ of $Q_\bb = \{ {\bf x} \in \mathbb Z^n \,:\, A{\bf x} \leq {\bf b} \}$. IBN is a modified version of the classical Chv{\'a}tal-Gomory procedure to compute integer hulls of polyhedra. The key difference is that IBN ignores the right-hand side vector ${\bf b}$ and needs as input only the matrix $A$.

We prove that SCR of $A{\bf x} \leq {\bf b}$ is bounded above by the Chv{\'a}tal rank of $A{\bf x} \leq {\bf b}$ and is hence finite. In contrast, IBN may not terminate when $n \geq 3$. To justify the adjective ``small'', we show that when $n=2$, SCR is at most one while Chv{\'a}tal rank can be arbitrarily high. For a known linear relaxation of the coclique polytope of the complete graph $K_n$, we prove that SCR is one or two depending on the parity of $n$ while the Chv{\'a}tal rank is known to be $\mathcal O(\textup{log} \, n)$.

We next relate SCR to the notion of {\em supernormality} of a vector configuration. 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 Ho{\c s}ten, Maclagan and Sturmfels.

Lastly, we provide lower bounds on SCR. We prove that when $n \geq 3$, SCR can be arbitrarily high, paralleling the situation of Chv{\'a}tal rank when $n \geq 2$. We also prove that if $A{\bf x} \leq {\bf b}$ is contained in the $d$-dimensional unit cube, then SCR is at least $\frac{d}{2} - o(d)$ which is of the same order as the known lower bounds on Chv{\'a}tal rank for such systems. Our methods provide an alternate way to compute lower bounds on Chv{\'a}tal rank. This project is joint work with Rekha Thomas.