On a Simple Connection Between $\Delta$-modular ILP and LP, and a New Bound on the Number of Integer Vertices

Abstract

Let $A\in Z^{m\times n}$, $rank(A)=n$, $b\in Z^m$, and $P$ be an $n$-dimensional polyhedron, induced by the system $Ax\le b$. It is a known fact that if $F$ is a $k$-face of $P$, then there exist at least $n-k$ linearly independent inequalities of the system $Ax\le b$ that become equalities on $F$. In other words, there exists a set of indices $J$, such that $|J|\ge n-k$, $rank(A_J)=n-k$, and $$A_{J}x-b_J=0,\text{for any x∈F}.$$ We show that a similar fact holds for the integer polyhedron $$P_I=conv.hull(P\cap Z^n),$$ if we additionally suppose that $P$ is $\Delta$-modular, for some $\Delta \in \{1,2,\dots \}$. More precisely, if $F$ is a $k$-face of $P_I$, then there exists a set of indices $J$, such that $|J|\ge n-k$, $rank(A_J)=n-k$, and $$A_{J}x-b_J\stackrel{\Delta }{=}0,\text{for any x∈F∩Zn},$$ where $x\stackrel{\Delta }{=}y$ means that $\Vert x-y{\Vert }_{\infty }<\Delta$. In other words, there exist at least $n-k$ linearly independent inequalities of the system $Ax\le b$ that almost become equalities on $F\cap Z^n$. When we say almost, we mean that the slacks are not greater than $\Delta -1$. Using this fact, we prove the inequality $$|vert(P_I)|\le 2\cdot \left(\genfrac{}{}{0ex}{}{m}{n}\right)\cdot {\Delta }^{n-1},$$ for the number of vertices of $P_I$, which is better, than the state of the art bound for $\Delta =O(n^2)$.