Pushing the boundaries of polytopal realizability

David Bremner, Antoine Deza, William Hua, Lars Schewe

Research output: Contribution to conferencePaperpeer-review

Abstract / Description of output

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


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

Cite this