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.
| Original language | English |
|---|---|
| Publication status | Published - 1 Dec 2011 |
| Event | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Duration: 10 Aug 2011 → 12 Aug 2011 |
Conference
| Conference | 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 |
|---|---|
| Country/Territory | Canada |
| City | Toronto, ON |
| Period | 10/08/11 → 12/08/11 |