##### What's Hot

Let $A \in Z^{m \times n}$, $rank(A) = n$, $b \in Z^m$, and $P$ be the $n$-dimensional polyhedron induced by the system $A x \leq b$.

If $F$ is the $k$ surface of $P$, then it is known that there are at least $nk$ linearly independent inequalities in the system $A x \leq b$ that are equal on $F$. It’s a fact. In other words, there exists a set of indices $J$ such that $|J|. \geq nk$, $rank(A_{J}) = nk$, and

$$A_{J} x – b_{J} = 0,\quad \text{for any x \in F}.$$

We show that similar facts apply to integer polyhedra

$$P_{I} = conv.hull\bigl(P \cap Z^n\bigr),$$

Further assuming $P$ is $\Delta$ modular, for some $\Delta \in \{1,2,\dots\}$ . More precisely, if $F$ is the $k$ face of $P_{I}$, then there is a set of indices $J$ such that $|J|. \geq nk$, $rank(A_{J}) = nk$, and

$$A_{J} x – b_{J} \overset{\Delta}{=} 0,\quad \text{for any x \in F \cap Z^n},$$ $x \overset{\Delta}{=} y$ means $\|x – y\|_{\infty} < \Delta$. In other words, there are at least $nk$ linearly independent inequalities of the system $A x \leq b$ that are nearly equal on $F \cap Z^n$. Almost means that the slack does not exceed $\Delta-1$. We will use this fact to prove the inequality.

$$|vert(P_I)| \leq 2 \cdot \binom{m}{n} \cdot \Delta^{n-1},$$ of the number of vertices in $P_I$ outperforms the state-of-the-art bound to $\Delta = O(n^2)$.

Share. 