BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Improved upper bounds on the diameter of lattice polytopes. Deza, Antoine


Let $D(d,k)$ denote the largest possible diameter over all polytopes which vertices are drawn from $\{ 0,1,...,k\}^d$. In 1989, Naddef showed that $D(d,1)=d$. This result was generalized in 1992 by Kleinschmidt and Onn who proved that $D(d,k) \leq kd$, before Del Pia and Michini tightened in 2016 the inequality to $D(d,k) \leq (k-1/2)d$ for $k\geq 2$. We show that $D(d,k) \leq (k-2/3)d$ for $k \geq 3$. In addition, we show that $D(4,3)=8$, which substantiates the conjecture stating that $D(d,k) \leq (k+1)d/2$, and is achieved by a Minkowski sum of lattice vectors. Based on a joint work with Lionel Pournin, Universit\'e Paris 13.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International