Monotone Diameters of Lattice Polytopes
Abstract
An influential 1989 result of Naddef shows that the diameters of 0/1-polytopes are at most their dimension. This was extended shortly after by Kleinschmidt and Onn to any lattice polytope in [0,k]d, where they showed a bound of at most dk. Naddef's argument easily extends to the monotone setting motivated by the simplex method, where one requires paths to increase with respect to a linear objective function. However, the Kleinschmidt-Onn argument does not. In fact, no argument in the 30 years since has managed to fill that gap. Prior to this work, it remained open whether the monotone diameter is bounded by a polynomial in d and k with no lower bounds suggesting any separation between the worst-case diameter and worst-case monotone diameter. Linear upper bounds hold for k=1 and k=2. However, we exhibit a sharp threshold for this question at k = 3 by constructing for each d ≥ 1 a lattice polytope in [0,3]6d with monotone diameter at least 2d−1. In particular, the polynomial bound does not hold. Furthermore, we show that Naddef's result does not extend to the unbounded setting by exhibiting a family of unbounded polyhedra with 0/1-vertices and diameter exponential in their dimension.
Related
- Quasi-polynomial valuations of lattice polytopes
- Weighted lattice point enumeration in lecture hall order polytopes
- Ehrhart Properties under Operations on Lattice Polytopes
- Unimodular defect and antipodal lattice points of smooth reflexive polytopes
- Characterization of k-highest weight and ĝ-dominant tableaux via $1−0$-slack recording tableaux in the quantum Littlewood-Richardson rule and lattice points in flagged hive polytopes
BibTeX
@misc{black2026monotone,
title = {{Monotone Diameters of Lattice Polytopes}},
author = {Alexander E. Black},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08647},
eprint = {2609.08647},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08647},
}
RIS
TY - UNPB
TI - Monotone Diameters of Lattice Polytopes
AU - Alexander E. Black
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08647
UR - https://arxiv.org/abs/2609.08647
AB - An influential 1989 result of Naddef shows that the diameters of 0/1-polytopes are at most their dimension. This was extended shortly after by Kleinschmidt and Onn to any lattice polytope in [0,k]^d, where they showed a bound of at most dk. Naddef's argument easily extends to the monotone setting motivated by the simplex method, where one requires paths to increase with respect to a linear objective function. However, the Kleinschmidt-Onn argument does not. In fact, no argument in the 30 years since has managed to fill that gap. Prior to this work, it remained open whether the monotone diameter is bounded by a polynomial in d and k with no lower bounds suggesting any separation between the worst-case diameter and worst-case monotone diameter. Linear upper bounds hold for k=1 and k=2. However, we exhibit a sharp threshold for this question at k = 3 by constructing for each d ≥ 1 a lattice polytope in [0,3]^6d with monotone diameter at least 2^d−1. In particular, the polynomial bound does not hold. Furthermore, we show that Naddef's result does not extend to the unbounded setting by exhibiting a family of unbounded polyhedra with 0/1-vertices and diameter exponential in their dimension.
ER -