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

In our note, we present a very simple and short proof of a new interesting fact about the faces of an integer hull of a given rational polyhedron. This fact has a complete analog in linear programming theory and can be useful to establish new constructive upper bounds on the number of vertices in an integer hull of a \(\Delta\) $\mathrm{\Delta }$ -modular polyhedron, which are competitive for small values of \(\Delta\) $\mathrm{\Delta }$ and can be useful for integer linear maximization problems with a convex or quasiconvex objective function. As an additional corollary, we show that the number of vertices in an integer hull is bounded by \(O(n)^n\) $O{(n)}^n$ for \(\Delta = O(1)\) $\mathrm{\Delta }=O(1)$ . As a part of our method, we introduce the notion of deep bases of a linear program. The problem to estimate their number by a non-trivial way seems to be quite challenging.