Recent Progress on the Combinatorial Diameter of Polyhedra and Simplicial Complexes

摘要

The Hirsch Conjecture, understood in a broad sense, asked what is the maximum possible combinatorial diameter of a convex polyhedron of dimension d and with n facets. Let us denote this number H(n, d). Although the original conjecture H(n, d) ≤ n-d has been disproved, the underlying problem is still wide open: 1. The known counter-examples violate the conjecture only by a constant and small factor (25% in the case of unbounded polyhedra, 5% for bounded polytopes).