More polytopes meeting the conjectured Hirsch bound Original Research Article

In 1957, W.M. Hirsch conjectured that every (convex) d-polytope with n facets has edge-diameter at most n−d. Recently, Holt and Klee constructed polytopes which meet this bound for a number of pairs (d,n) with d⩽13 and for all pairs (d,n) with d⩾14. These constructions involve a judicious use of truncation, wedging, and blending on polytopes which already meet the Hirsch bound. In this paper we extend these techniques to construct polytopes of edge-diameter n−d for all (d,n) with d⩾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⩽2d.