| Edge-Graph Diameter Bounds for Convex Polytopes with Few Facets (2008) | |||||||||
Abstract | |||||||||
| We show that the edge graph of a 6-dimensional polytope with 12 facets has diameter at most 6, thus verifying the d-step conjecture of Klee and Walkup in the case of d=6. This implies that for all pairs (d,n) with n-d \leq 6 the diameter of the edge graph of a d-polytope with n facets is bounded by 6, which proves the Hirsch conjecture for all n-d \leq 6. We show this result by showing this bound for a more general structure -- so-called matroid polytopes -- by reduction to a small number of satisfiability problems.. Comment: 8 pages; fix typos in table 2, add reference | |||||||||
Publication details | |||||||||
| |||||||||