Many polytopes meeting the conjectured Hirsch bound

DOI10.1007/PL00009372MaRDI QIDQ1269445zbMATH OpenFDO

Authors Victor Klee, Fred B. Holt

Publication date 29 November 1999

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009372

zbMATH Keywords

Hirsch bound

Mathematics Subject Classification ID

Inequalities and extremum problems involving convexity in convex geometry (52A40) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11)

Review text

Let \(\Delta (d,n)\) denote the maximum edge-diameter of \(d\)-dimensional polytopes with \(n\) facets. W. M. Hirsch conjectured in 1957 that \(\Delta (d,n)\leq n-d\) for all \(n>d\geq 2\). While this conjecture remains unproved, the authors construct, by means of wedging, truncation and blending, suitable polytopes to prove that this upper bound for \(\Delta (d,n)\) is attained if not surpassed for many \(d\) and \(n\). In particular \(\Delta (d,n) \geq n-d\) for all \(n>d\geq 14\).

Recommendations

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

Cited in

(19)

• A continuous d-step conjecture for polytopes
• More polytopes meeting the conjectured Hirsch bound
• Linear programming, the simplex algorithm and simple polytopes
• The hierarchy of circuit diameters and transportation polytopes
• On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• The Hirsch conjecture is true for (0,1)-polytopes
• Maximal triangulations of a regular prism
• Blending simple polytopes at faces
• On the circuit diameter conjecture
• The diameter of the ridge-graph of a cyclic polytope
• A counterexample to the Hirsch conjecture
• Edge-graph diameter bounds for convex polytopes with few facets
• The width of five-dimensional prismatoids
• More bounds on the diameters of convex polytopes
• Diameter and Curvature: Intriguing Analogies
• One-point suspensions and wreath products of polytopes and spheres
• An update on the Hirsch conjecture
• Polytopes and arrangements: diameter and curvature

This page was built for publication: Many 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 Q1269445)