More bounds on the diameters of convex polytopes
Journal Articles
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
Finding a good bound on the maximal edge diameter $\Delta(d,n)$ of a polytope
in terms of its dimension $d$ and the number of its facets $n$ is one of the
basic open questions in polytope theory \cite{BG}. Although some bounds are
known, the behaviour of the function $\Delta(d,n)$ is largely unknown. The
Hirsch conjecture, formulated in 1957 and reported in \cite{GD}, states that
$\Delta(d,n)$ is linear in $n$ and $d$: $\Delta(d,n) \leq n-d$. The conjecture
is known to hold in small dimensions, i.e., for $d \leq 3$ \cite{VK}, along
with other specific pairs of $d$ and $n$ (Table \ref{before}). However, the
asymptotic behaviour of $\Delta(d,n)$ is not well understood: the best upper
bound -- due to Kalai and Kleitman -- is quasi-polynomial \cite{GKDK}.
In this article we will show that $\Delta(4,12)=7$ and present strong
evidence for $\Delta(5,12)=\Delta(6,13)=7$. The first of these new values is of
particular interest since it indicates that the Hirsch bound is not sharp in
dimension 4.