More polytopes meeting the conjectured Hirsch bound (Q1301832): Difference between revisions

Let \(\Delta(d,n)\) be the maximum edge-diameter among all \((d,n)\)-polytopes (\((d,n)\)-polytope means a simple \(d\)-dimensional polytope with precisely \(n\) facets). In 1957, W.~M.~Hirsch conjectured that \(\Delta(d,n)\leqslant n-d\) for all \(n >d\geqslant 2.\) A pair \((d,n)\) is said to be H-sharp if \(\Delta(d,n)\geqslant n-d.\) It is well known that all \((d,n)\) with \(d <n\leqslant 2d\) are H-sharp, that \(\Delta(2,n)=\lfloor n/2\rfloor\), \(\Delta(3,n)=\lfloor 2n/3\rfloor\) and thus for \(d\leqslant 3\), \(n\leqslant 2d\) is also necessary for H-sharpness. Of the 1142 combinatorial types of \((4,9)\)-polytopes only one has diameter 5, demonstrating that \((4,9)\) is H-sharp. That one is denoted by \(Q_4.\) Recently, Holt and Klee constructed various pairs \((d,n)\) with \(d\leqslant 13\) which are H-sharp, but the most important result was the fact that when \(d\geqslant 14,\) the pairs \((d,n)\) is H-sharp for all \(n>d.\) These constructions involve a judicious use of truncation, wedging, and blending on polytopes which already meet the Hirsch bound. In this paper, these techniques are extended to construct polytopes of edge-diameter \(n - d\) for all \((d,n)\) with \(d\geqslant 8.\) The improvement from \(d = 14\) to \(d = 8\) follows from identifying circumstances in which the results for wedging when \(n > 2d\) can be extended to the cases \(n\leqslant 2d.\) A tabulation of all H-sharp pairs \((d,n)\) for \(d<8\) which can be obtained by applying the mentioned three basic operations to \(d\)-simplex or to \(Q_4\) is given.