On the Monotone Upper Bound Problem
| dc.creator | Pfeifle, Julian | |
| dc.creator | Ziegler, Günter M. | |
| dc.date | 2003-08-20 | |
| dc.date.accessioned | 2026-07-07T05:00:30Z | |
| dc.date.available | 2026-07-07T05:00:30Z | |
| dc.description | The Monotone Upper Bound Problem asks for the maximal number M(d,n) of vertices on a strictly-increasing edge-path on a simple d-polytope with n facets. More specifically, it asks whether the upper bound M(d,n)<=M_{ubt}(d,n) provided by McMullen's (1970) Upper Bound Theorem is tight, where M_{ubt}(d,n) is the number of vertices of a dual-to-cyclic d-polytope with n facets. It was recently shown that the upper bound M(d,n)<=M_{ubt}(d,n) holds with equality for small dimensions (d<=4: Pfeifle, 2003) and for small corank (n<=d+2: Gärtner et al., 2001). Here we prove that it is not tight in general: In dimension d=6 a polytope with n=9 facets can have M_{ubt}(6,9)=30 vertices, but not more than 26 <= M(6,9) <= 29 vertices can lie on a strictly-increasing edge-path. The proof involves classification results about neighborly polytopes, Kalai's (1988) concept of abstract objective functions, the Holt-Klee conditions (1998), explicit enumeration, Welzl's (2001) extended Gale diagrams, randomized generation of instances, as well as non-realizability proofs via a version of the Farkas lemma. | |
| dc.description | 15 pages; 6 figures | |
| dc.identifier | https://arxiv.org/abs/math/0308186 | |
| dc.identifier | http://arxiv.org/abs/math/0308186 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68348 | |
| dc.subject | Metric Geometry | |
| dc.subject | Combinatorics | |
| dc.subject | 52B05 (Primary) 52-04(Secondary) | |
| dc.title | On the Monotone Upper Bound Problem | |
| dc.type | text |