Computational determination of the largest lattice polytope diameter (Q5918843)

The diameter of a (convex) polytope is the diameter of the graph consisting of the polytope's vertices and edges. Understanding the diameter of a polytope is of interest for a variety of reasons, such as in relation to the (now-disproved) Hirsch conjecture or in relation to the simplex method in optimization. This article studies polytopes whose vertices are lattice points, that is, elements of \(\mathbb{Z}^d\) for some \(d\), and where each vertex takes its coordinates from \(\{0,1,\dots,k\}\) for some fixed \(k\). Such a polytope is called a lattice \((d,k)\)-polytope. Let \(\delta(d,k)\) denote the maximum diameter among all lattice \((d,k)\)-polytopes. Deza, Manoussakis, and Onn [\textit{A. Deza} et al., Discrete Comput. Geom. 60, No. 1, 27--39 (2018; Zbl 1406.52029)] previously proved that \(\delta(d,k) \geq \lfloor (k+1)d/2 \rfloor\) for all \(k < 2d\) and conjectured this bound to be an equality. The cases of \(\delta(2,k)\) and \(\delta(d,2)\) have been previously established, so any remaining cases requires \(d,k \geq 3\). In this article, the authors prove that the conjecture holds when \((d,k) = (3,4)\) and when \((d,k) = (3,5)\). The authors recognize that certain known conditions drastically reduce the space of lattice \((d,k)\)-polytope one must search through and apply their algorithm to \((d,k) = (3,4)\) and \((d,k) = (3,5)\).