Edge-graph diameter bounds for convex polytopes with few facets

David Bremner*, Lars Schewe

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)229-237
Number of pages9
JournalExperimental mathematics
Volume20
Issue number3
Early online date22 Aug 2011
DOIs
Publication statusPublished - 5 Sep 2011

Keywords

  • Diameter
  • Hirsh conjecture
  • Oriented matroids
  • Polytopes
  • Satisfiability

Fingerprint

Dive into the research topics of 'Edge-graph diameter bounds for convex polytopes with few facets'. Together they form a unique fingerprint.

Cite this