More bounds on the diameters of convex polytopes - Mathematics > CombinatoricsReport as inadecuate

More bounds on the diameters of convex polytopes - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Finding a good bound on the maximal edge diameter $\Deltad,n$ of a polytopein terms of its dimension $d$ and the number of its facets $n$ is one of thebasic open questions in polytope theory \cite{BG}. Although some bounds areknown, the behaviour of the function $\Deltad,n$ is largely unknown. TheHirsch conjecture, formulated in 1957 and reported in \cite{GD}, states that$\Deltad,n$ is linear in $n$ and $d$: $\Deltad,n \leq n-d$. The conjectureis known to hold in small dimensions, i.e., for $d \leq 3$ \cite{VK}, alongwith other specific pairs of $d$ and $n$ Table ef{before}. However, theasymptotic behaviour of $\Deltad,n$ is not well understood: the best upperbound - due to Kalai and Kleitman - is quasi-polynomial \cite{GKDK}.In this article we will show that $\Delta4,12=7$ and present strongevidence for $\Delta5,12=\Delta6,13=7$. The first of these new values is ofparticular interest since it indicates that the Hirsch bound is not sharp indimension 4.

Author: David Bremner, Antoine Deza, William Hua, Lars Schewe


Related documents