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 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.
Original language | English |
---|---|
Pages (from-to) | 229-237 |
Number of pages | 9 |
Journal | Experimental mathematics |
Volume | 20 |
Issue number | 3 |
Early online date | 22 Aug 2011 |
DOIs | |
Publication status | Published - 5 Sept 2011 |
Keywords / Materials (for Non-textual outputs)
- Diameter
- Hirsh conjecture
- Oriented matroids
- Polytopes
- Satisfiability