Metraipolis › archive › dc_db5d5d395dac
Monotone Diameters of Lattice Polytopes — arXiv:2609.08647
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.08647
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:29:58.089Z
- SHA-256 of the archived text
44d97720a6969cdcb0f94488bdcbb84bef21f26dbe75dd2d3a95fe066c86cfd7- Stable URL of this page
https://metraipolis.com/documento/dc_db5d5d395dac
How to cite
Monotone Diameters of Lattice Polytopes — arXiv:2609.08647 — arXiv (en), https://arxiv.org/abs/2609.08647 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_db5d5d395dac (Metraipolis archive dc_db5d5d395dac, sha256 44d97720a6969cdcb0f94488bdcbb84bef21f26dbe75dd2d3a95fe066c86cfd7)
BibTeX
@misc{dcdb5d5d395dac,
title = {Monotone Diameters of Lattice Polytopes — arXiv:2609.08647},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.08647},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_db5d5d395dac; sha256 44d97720a6969cdcb0f94488bdcbb84bef21f26dbe75dd2d3a95fe066c86cfd7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08647. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.OC).
Categorie arXiv: Combinatorics (math.CO) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.08647 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:09:21.769Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).