More polytopes meeting the conjectured Hirsch bound

DOI10.1016/S0012-365X(99)00017-5MaRDI QIDQ1301832zbMATH OpenWikidataFDO

Authors Kerstin Fritzsche, Fred B. Holt

Publication date 11 September 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(99)00017-5

zbMATH Keywords

\(d\)-step conjecturecombinatorial properties of polytopesedge-diameterfast-slow blendingH-sharpnessHirsch boundHirsch conjecturetruncationwedging

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Review text

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.

Recommendations

• Many polytopes meeting the conjectured Hirsch bound
• More bounds on the diameters of convex polytopes
• Blending simple polytopes at faces
• Edge-graph diameter bounds for convex polytopes with few facets
• The Hirsch conjecture is true for (0,1)-polytopes

Cites work

• Counterexamples to the strong \(d\)-step conjecture for \(d\geq 5\)
• Diameters of Polyhedral Graphs
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3614496 (Why is no real title available?)
• Many polytopes meeting the conjectured Hirsch bound
• Some upper bounds for the diameters of convex polytopes
• The d-Step Conjecture and Its Relatives
• The d-step conjecture and Gaussian elimination
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes

Cited in

(14)

• A continuous d-step conjecture for polytopes
• Many polytopes meeting the conjectured Hirsch bound
• The hierarchy of circuit diameters and transportation polytopes
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• Blending simple polytopes at faces
• On the circuit diameter conjecture
• Two combinatorial properties of a class of simplicial polytopes
• Polyhedral surfaces in wedge products
• The diameter of the ridge-graph of a cyclic polytope
• Topological prismatoids and small simplicial spheres of large diameter
• More bounds on the diameters of convex polytopes
• Diameter and Curvature: Intriguing Analogies
• One-point suspensions and wreath products of polytopes and spheres
• Polytopes and arrangements: diameter and curvature

This page was built for publication: More polytopes meeting the conjectured Hirsch bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1301832)