Pushing the boundaries of polytopal realizability

David Bremner, Antoine Deza, William Hua, Lars Schewe

Research output: Contribution to conferencePaperpeer-review


Let Δ(d, n) be the maximum possible diameter of the vertex-edge graph over all d-dimensional polytopes de- fined 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 Matchske, 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 Δ (4, 11) = Δ 6, 12) = 6. Here we show that (4, 12) = Δ (5, 12) = 7 and present strong evidence that Δ (6, 13) = 7.

Original languageEnglish
Publication statusPublished - 1 Dec 2011
Event23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada
Duration: 10 Aug 201112 Aug 2011


Conference23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
CityToronto, ON

Fingerprint Dive into the research topics of 'Pushing the boundaries of polytopal realizability'. Together they form a unique fingerprint.

Cite this