Drums of high width
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Applications of mathematical programming (90C90)
This paper considers \textit{prismatoids}-polytopes with two disjoint facets that contain all the vertices. The \textit{width} of a prismatoid is the distance between the two disjoint facets in the facet-ridge graph. The paper provides a new family of 5-dimensional prismatoids with \(16k+24\) vertices and width at least \(5+k\). A first consequence of this construction is that, for any integer \(k\ge 1\), there exists a polytope of dimension \(d=16k+19\) with \(2d\) facets and diameter \(d+k\). Further define the \textit{excess width} as the function\N\[\Nf_{d}(n)=\max_{\text{\(d\)-dimensional \(n\)-vertex prismatoids \(P\)}} \mathrm{width}(P)-d\N\]\NAnother consequence is that the function \(f_{5}\) grows linearly in \(n\), answering a question of \textit{B. Matschke} et al. [Proc. Lond. Math. Soc. (3) 110, No. 3, 647--672 (2015; Zbl 1330.52015)].
This page was built for publication: Drums of high width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7006396)
