Edge-graph diameter bounds for convex polytopes with few facets. (English) Zbl 1266.52017
Summary: We show that the edge graph of a 6-dimensional polytope with 12 facets has diameter at most 6, thus verifying the \(d\)-step conjecture of Klee and Walkup in the case \(d=6\). This implies that for all pairs \((d,n)\) with \(n-d\leq 6\), the diameter of the edge graph of a \(d\)-polytope with \(n\) facets is bounded by 6, which proves the Hirsch conjecture for all \(n-d\leq 6\). We prove this result by establishing this bound for a more general structure, so-called matroid polytopes, by reduction to a small number of satisfiability problems.
MSC:
| 52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 52C40 | Oriented matroids in discrete geometry |
Software:
nautyReferences:
| [1] | Björner [Björner et al. 99] Anders, Oriented Matroids, 2nd ed., Encyclopedia of Mathematics and Its Applications 46 (1999) |
| [2] | DOI: 10.1016/j.ejc.2008.12.006 · Zbl 1229.05060 · doi:10.1016/j.ejc.2008.12.006 |
| [3] | Bremner [Bremner et al. 05] David, ”Path Complexes and Polytope Diameters” (2005) · Zbl 1114.68421 |
| [4] | Eén [Eén and Sörensson 03] Niklas, SAT (2003) pp 502– (2004) |
| [5] | DOI: 10.1007/BF02761464 · Zbl 0235.52009 · doi:10.1007/BF02761464 |
| [6] | Grünbaum [Grünbaum 03] Branko, Convex Polytopes, 2nd ed., Graduate Texts in Mathematics 221 (2003) |
| [7] | DOI: 10.1016/j.disc.2004.02.006 · Zbl 1113.52028 · doi:10.1016/j.disc.2004.02.006 |
| [8] | DOI: 10.4153/CJM-1964-061-2 · Zbl 0121.37701 · doi:10.4153/CJM-1964-061-2 |
| [9] | DOI: 10.1287/moor.12.4.718 · Zbl 0632.52007 · doi:10.1287/moor.12.4.718 |
| [10] | DOI: 10.1007/BF02395040 · Zbl 0163.16801 · doi:10.1007/BF02395040 |
| [11] | McKay, [McKay 05] Brendan D. 2005. ”Nauty.” Available online (http://cs.anu.edu.au/people/bdm/nauty/). |
| [12] | Santos, [Santos 10] Francisco. 2010. ”A Counterexample to the Hirsch Conjecture.” arXiv:1006.2814v1 · Zbl 1237.52008 |
| [13] | Schewe [Schewe 07] Lars, ”Satisfiability Problems in Discrete Geometry.” (2007) · Zbl 1128.52013 |
| [14] | DOI: 10.1007/s00454-009-9222-y · Zbl 1187.52023 · doi:10.1007/s00454-009-9222-y |
| [15] | Schuchert [Schuchert 95] Peter, ”Matroid-Polytope und Einbettungen kombinatorischer Mannigfaltigkeiten.” (1995) · Zbl 0859.52004 |
| [16] | Ziegler [Ziegler 95] Günter M., Lectures on Polytopes. Graduate Texts in Mathematics 152 (1995) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
