More bounds on the diameters of convex polytopes

David Bremner, Antoine Deza*, William Hua, Lars Schewe

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Let Δ(d, n) be the maximum possible diameter of the vertex-edge graph over all d-dimensional polytopes defined by n inequalities. The Hirsch bound holds for particular n and d if Δ(d, n)≤n-d. Francisco Santos recently resolved a question open for more than five decades by showing that Δ(d, 2d)≥d+1 for d=43; the dimension was then lowered to 20 by Matschke, Santos and Weibel. This progress has stimulated interest in related questions. The existence of a polynomial upper bound for Δ(d, n) is still an open question, the best bound being the quasi-polynomial one due to Kalai and Kleitman in 1992. Another natural question is for how large n and d the Hirsch bound holds. Goodey showed in 1972 that Δ(4, 10)=5 and Δ(5, 11)=6, and more recently, Bremner and Schewe showed that Δ(4, 11)=Δ(6, 12)=6. Here, we show that Δ(4, 12)=Δ(5, 12)=7.

Original languageEnglish
Pages (from-to)442-450
Number of pages9
JournalOptimization Methods and Software
Volume28
Issue number3
Early online date13 Mar 2012
DOIs
Publication statusPublished - 1 Jun 2013

Keywords

  • combinatorics
  • convex polytopes
  • discrete geometry
  • linear optimization
  • pivoting methods

Fingerprint

Dive into the research topics of 'More bounds on the diameters of convex polytopes'. Together they form a unique fingerprint.

Cite this