×

More polytopes meeting the conjectured Hirsch bound. (English) Zbl 0944.52004

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.

MSC:

52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Adler, Lower bounds for maximum diameters of polytopes, in: M. Balinski (Ed.), Pivoting and Extensions, Math. Programming Studies, vol. 1, 1974, pp. 11-19.; I. Adler, Lower bounds for maximum diameters of polytopes, in: M. Balinski (Ed.), Pivoting and Extensions, Math. Programming Studies, vol. 1, 1974, pp. 11-19. · Zbl 0395.90050
[2] Altshuler, A.; Bokowski, J.; Steinberg, L., The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes, Diskrete Math., 31, 115-124 (1980) · Zbl 0468.52008
[3] G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.; G.B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.
[4] Dantzig, G. B., Eight unsolved problems from mathematical programming, Bull. Amer. Math. Soc., 70, 499-500 (1964)
[5] Goodey, P. R., Some upper bounds for the diameter of convex polytopes, Israeli J. Math., 11, 380-385 (1972) · Zbl 0235.52009
[6] F.B. Holt, Maximal nonrevisiting paths in simple polytopes, manuscript, 1998.; F.B. Holt, Maximal nonrevisiting paths in simple polytopes, manuscript, 1998.
[7] Holt, F. B.; Klee, V., Counterexamples to the strong \(d\)-step conjecture for \(d ⩾ 5\), Discrete Comput. Geom., 19, 33-46 (1998) · Zbl 0899.52007
[8] Holt, F. B.; Klee, V., Many polytopes meeting the conjectured Hirsch bound, Discrete Comput. Geom., 20, 1-17 (1998) · Zbl 0926.52013
[9] Klee, V., Diameters of polyhedral graphs, Can. J. Math., 16, 602-614 (1964) · Zbl 0121.37701
[10] Klee, V.; Kleinschmidt, P., The \(d\)-step conjecture and its relatives, Math. Oper. Res., 12, 718-755 (1987) · Zbl 0632.52007
[11] Klee, V.; Walkup, D. W., The \(d\)-step conjecture for polyhedra of dimension \(d<6\), Acta Math., 117, 53-78 (1967) · Zbl 0163.16801
[12] Lagarias, J. C.; Prahbu, N.; Reeds, J. A., The \(d\)-step conjecture and Gaussian elimination, Discrete Comput. Geom., 18, 53-82 (1997) · Zbl 0883.52008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.