Long monotone paths on simple 4-polytopes |
| |
Authors: | Julian Pfeifle |
| |
Institution: | (1) Institut de Matemàtica, Universitat de Barcelona, Gran Via de les Corts Catalanes 585, E-08007 Barcelona, Spain;(2) Present address: Department de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Edifici Omega, Campus Nord, Jordi Girona 1-3, E-08034 Barcelona, Spain |
| |
Abstract: | TheMonotone Upper Bound Problem (Klee, 1965) asks if the maximal numberM(d,n) of vertices in a monotone path along edges of ad-dimensional polytope withn facets can be as large as conceivably possible: IsM(d,n)=M ubt (d,n), the maximal number of vertices that ad-polytope withn facets can have according to the Upper Bound Theorem?We show that in dimensiond=4, the answer is “yes”, despite the fact that it is “no” if we restrict ourselves to the dual-to-cyclic polytopes. For eachn≥5, we exhibit a realization of a polar-to-neighborly 4-dimensional polytope withn facets and a Hamilton path through its vertices that is monotone with respect to a linear objective function.This constrasts an earlier result, by which no polar-to-neighborly 6-dimensional polytope with 9 facets admits a monotone Hamilton path. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|