Upper bound found for edges in Gomory corner polyhedron geometry

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

Computational GeometryDiscrete Mathematics

Summary

Counting the edges in a special kind of geometric shape called a Gomory corner polyhedron has been a challenging problem for many years. The paper shows a new way to put an upper limit on how many edges these shapes can have, depending on their dimension and other properties. This new bound is tighter than previously known results. The authors thus resolved a question that people in math and computer science had been stuck on for some time.

What this means in practice

A theory result. No direct application yet.

Authors

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

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)$.