Paperlane

no. 14 · Friday 13 November 2026

An upper bound on the number of edges of a Gomory corner polyhedron

A. Yu. Chirkov, S. I. Veselov, D. V. Gribanov, D. S. Malyshev and N. Yu. Zolotykh

math.CO

Abstract

We establish the first nontrivial upper bound on the number of edges of a Gomory corner polyhedron, resolving a long-standing open question. For an $n$-dimensional corner polyhedron associated with an integer lattice of determinant $δ$, the number of edges is at most $$ O\left(n6^n \cdot \bigl(1+\log_2(2δ)\bigr)^{2n-3}\right). $$ This improves the standard bound obtained by counting pairs of vertices, reducing the logarithmic exponent from $(2n-2)$ to $(2n-3)$.

fields
Combinatorics, Optimization and Control
pdf ↗ page arXiv:2611.16839 ↗