2025/06/15 by Bludov Mikhail, Mikhail, Bludov, Gribanov Dmitry +11 · 1 citation
Business, Management and Accounting · Computer Science · Engineering · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optics and Image Analysis #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2506.12774
openalex publication_date 2025/06/15 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
Let P be a polytope defined by the system A x ≤ 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! ⋅ \fracΔΔaverage ⋅ vol(B2) ∼ (1)/(√(πn)) ⋅ ((2 π)/(e))n/2 ⋅ nn/2 ⋅ \fracΔΔ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 ≥ 1, where Δmin 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(n3 ⋅ \fracΔΔmin ⋅ ln (n \fracΔΔmin) ). Thus, both characteristic of P are linear in Δ/Δmin. From an algorithmic perspective, we demonstrate that: Given A ∈ Qm × n, b ∈ Qm, and an initial feasible solution to A x ≤ b, the convex hull of P can be constructed in O(n)n/2 ⋅ m2 ⋅ \fracΔΔaverage operations. For simple polyhedra, the dependence on m reduces to linear; Given A ∈ Zm × n and b ∈ Qm, the number |P ∩ Zn| can be computed in O(n)n ⋅ \fracΔ4Δaverage arithmetic operations.