Computational determination of the largest lattice polytope diameter (Q5918843): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 07:10, 5 March 2024
scientific article; zbMATH DE number 7206530
Language | Label | Description | Also known as |
---|---|---|---|
English | Computational determination of the largest lattice polytope diameter |
scientific article; zbMATH DE number 7206530 |
Statements
Computational determination of the largest lattice polytope diameter (English)
0 references
29 May 2020
0 references
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)\).
0 references
lattice polytope
0 references
edge-graph diameter
0 references
enumeration algorithm
0 references