On the Vertices of Delta-modular Polyhedra

Let $P$ be a polytope defined by the system $Ax\le b$, where $A\in R^{m\times n}$, $b\in R^m$, and $\text{rank}(A)=n$. We give a short geometric proof of the following tight upper bound on the number of vertices of $P$: $$n!\cdot \frac{\mathrm{\Delta }}{{\mathrm{\Delta }}_{\text{average}}}\cdot \text{vol}(B_2)\sim \frac{1}{\sqrt{\pi n}}\cdot {\left(\frac{2\pi }{e}\right)}^{n\mathrm{/}2}\cdot n^{n\mathrm{/}2}\cdot \frac{\mathrm{\Delta }}{{\mathrm{\Delta }}_{\text{average}}},$$ where $\mathrm{\Delta }$ is the maximum absolute value of $n\times n$ subdeterminants of $A$, and ${\mathrm{\Delta }}_{\text{average}}$ is the average absolute value of subdeterminants of $A$ corresponding to a triangulation of $P$’s normal fan. Assuming that $A$ is integer, such polyhedra are called $\mathrm{\Delta }$-modular polyhedra. Note that in the integer case, the bound can be simplified via the inequality ${\mathrm{\Delta }}_{\text{average}}\ge {\mathrm{\Delta }}_{\min }\ge 1$, where ${\mathrm{\Delta }}_{\min }$ is the minimum absolute value of subdeterminants of $A$ corresponding to feasible bases of $Ax\le b$. For this, we prove and use a symmetric variant of Macbeath’s theorem. Additionally, we give a direct argument based on prior results in the field, showing that the graph diameter of $P$ is bounded by $O(n^3\cdot \frac{\mathrm{\Delta }}{{\mathrm{\Delta }}_{\min }}\cdot \ln (n\frac{\mathrm{\Delta }}{{\mathrm{\Delta }}_{\min }}))$. Thus, both characteristic of $P$ are linear in $\mathrm{\Delta }\mathrm{/}{\mathrm{\Delta }}_{\min }$. From an algorithmic perspective, we demonstrate that: Given $A\in Q^{m\times n}$, $b\in Q^m$, and an initial feasible solution to $Ax\le b$, the convex hull of $P$ can be constructed in $O(n{)}^{n\mathrm{/}2}\cdot m^2\cdot \frac{\mathrm{\Delta }}{{\mathrm{\Delta }}_{\text{average}}}$ operations. For simple polyhedra, the dependence on $m$ reduces to linear; Given $A\in Z^{m\times n}$ and $b\in Q^m$, the number $\mathrm{\mid }P\cap Z^n\mathrm{\mid }$ can be computed in $O(n{)}^n\cdot \frac{{\mathrm{\Delta }}^4}{{\mathrm{\Delta }}_{\text{average}}}$ arithmetic operations.