Bremner D, Schewe L (2011)
Publication Status: Published
Publication Type: Journal article, Original article
Publication year: 2011
Publisher: AK Peters / Taylor & Francis
Book Volume: 20
Pages Range: 229-237
Journal Issue: 3
DOI: 10.1080/10586458.2011.564965
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. © Taylor & Francis Group, LLC.
APA:
Bremner, D., & Schewe, L. (2011). Edge-graph diameter bounds for convex polytopes with few facets. Experimental Mathematics, 20(3), 229-237. https://doi.org/10.1080/10586458.2011.564965
MLA:
Bremner, David, and Lars Schewe. "Edge-graph diameter bounds for convex polytopes with few facets." Experimental Mathematics 20.3 (2011): 229-237.
BibTeX: Download