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 $A x \leq 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 $A x \leq b$ that become equalities on $F$. In other words, there exists a set of indices $J$, such that $|J| \geq n-k$, $rank(A_{ J}) = n-k$, and $$ A_{ J} x - b_{ J} = 0,\quad \text{ for any $x \in F$}. $$ We show that a similar fact holds for the integer polyhedron $$ P_{ I} = conv.hull\bigl(P \cap Z^n\bigr), $$ 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| \geq n-k$, $rank(A_{ J}) = n-k$, and $$ A_{ J} x - b_{ J} \overset{ \Delta}{ =} 0,\quad \text{ for any $x \in F \cap Z^n$}, $$ where $x \overset{ \Delta}{ =} y$ means that $\|x - y\|_{ \infty} < \Delta$. In other words, there exist at least $n-k$ linearly independent inequalities of the system $A x \leq 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)| \leq 2 \cdot \binom{ m}{ n} \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)$.
Categories: cs.DM cs.CG math.CO