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 d = 6. This implies that for all pairs (d, n) with n - d ≤ 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 ≤ 6. We prove this result by establishing this bound for a more general structure, so-called matroid polytopes, by reduction to a small number of satisfiability problems.
- Hirsh conjecture
- Oriented matroids