Monotone Diameters of Lattice Polytopes

Source 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 \geq 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.