On the diameter of lattice polytopes

Alberto Del Pia, Carla Michini

Abstract

In this paper we show that the diameter of a d-dimensional lattice polytope in [0,k]^n is at most (k - 1/2) d. This result implies that the diameter of a d-dimensional half-integral polytope is at most 3/2 d. We also show that for half-integral polytopes the latter bound is tight for any d.
BibTeX
@inproceedings{pia2016diameter,
  author = {Alberto Del Pia and Carla Michini},
  title = {{On the diameter of lattice polytopes}},
  booktitle = {Discret. Comput. Geom},
  year = {2016},
  url = {https://openreview.net/forum?id=uCqlYCUPdF6},
}

Loading related content...

Figure