Polynomial bound for the monotone diameter of lattice polytopes
The conjecture asserts that there exists a polynomial such that, for every and every lattice polytope , its monotone diameter satisfies , where monotone paths are required to increase with respect to a linear objective function.
References
Source: arXiv
Progress summary
A new unrefereed preprint claims an exponential counterexample in three or more dimensions, refuting the proposed polynomial bound while the lower-dimensional cases remain settled.
The conjecture asks whether monotone diameters of lattice polytopes admit a polynomial bound in the dimension and the box parameter . The reported counterexample at would refute the general claim and separates the known linear cases from the failure at .
Known results
- Half-integral polytopes have monotone diameter at most ; the general question was explicitly open in 2022.
- For -dimensional -level polytopes, the bound is .
- Under stated integral-description assumptions, a bound of is known.
Exponential counterexample at
A new arXiv preprint, Monotone Diameters of Lattice Polytopes, claims exponential monotone diameter for , together with related examples for unbounded polyhedra. If correct, this settles the proposed universal polynomial bound negatively; the preprint is unrefereed.
Current status (as of September 2026): The cases have known linear bounds, while the general polynomial-bound conjecture is claimed false at ; the counterexample remains unverified.
Sources
Solutions 0
No solutions have been posted yet.