Total: 1
Let P be a polytope defined by the system Ax≤b, where A∈Rm×n, b∈Rm, 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(B2)∼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≥Δmin, where \Delta_{\min} is the minimum absolute value of subdeterminants of A corresponding to feasible bases of A x \leq 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\bigl(n^3 \cdot \frac{\Delta}{\Delta_{\min}} \cdot \ln (n \frac{\Delta}{\Delta_{\min}}) \bigr). Thus, both characteristic of P are linear in \Delta/\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 A x \leq b, the convex hull of P can be constructed in O(n)^{n/2} \cdot m^2 \cdot \frac{\Delta}{\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 |P \cap Z^n| can be computed in O(n)^n \cdot \frac{\Delta^4}{\Delta_{\text{average}}} arithmetic operations.