Pushing the boundaries of polytopal realizability

Bremner D, Deza A, Hua W, Schewe L (2011)


Publication Status: Published

Publication Type: Conference contribution, Conference Contribution

Publication year: 2011

Pages Range: 193-198

Conference Proceedings Title: Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011

Event location: Toronto, ON CA

URI: https://www.scopus.com/record/display.uri?eid=2-s2.0-84882934180&origin=inward

Abstract

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.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Bremner, D., Deza, A., Hua, W., & Schewe, L. (2011). Pushing the boundaries of polytopal realizability. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 (pp. 193-198). Toronto, ON, CA.

MLA:

Bremner, David, et al. "Pushing the boundaries of polytopal realizability." Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011, Toronto, ON 2011. 193-198.

BibTeX: Download