On the Vertices of Delta-modular Polyhedra

Let P be a polytope defined by the system A x ≤ b, where A ∈ Rm × n, b ∈ Rᵐ, and rank(A) = n. We give a short geometric proof of the following tight upper bound on the number of vertices of P: n! · ΔΔaverage · vol(B₂) ~ 1√πn · (2 π/e)n/2 · nn/2 · ΔΔaverage, where $Δ$ is the maximum absolute value of n × n subdeterminants of A, and Δ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 $Δ$-modular polyhedra. Note that in the integer case, the bound can be simplified via the inequality Δaverage ≥ Δₘᵢₙ ≥ 1, where Δₘᵢₙ is the minimum absolute value of subdeterminants of A corresponding to feasible bases of A x ≤ 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³ · ΔΔₘᵢₙ · ln (n ΔΔₘᵢₙ) ). Thus, both characteristic of P are linear in Δ/Δₘᵢₙ. From an algorithmic perspective, we demonstrate that: Given A ∈ Qm × n, b ∈ Qᵐ, and an initial feasible solution to A x ≤ b, the convex hull of P can be constructed in O(n)n/2 · m² · ΔΔaverage operations. For simple polyhedra, the dependence on m reduces to linear; Given A ∈ Zm × n and b ∈ Qᵐ, the number |P ∩ Zⁿ| can be computed in O(n)ⁿ · Δ⁴Δaverage arithmetic operations.