On the Monotone Upper Bound Problem

2003/08/20 by Julián Pfeifle, Julian Pfeifle, Günter M. Ziegler +2
Computer Science · Engineering · Mathematics · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Optimization and Packing Problems #math.CO #math.MG #msc:52B05

paper · pdf · doi:10.48550/arxiv.math/0308186

15 pages; 6 figures

arxiv created 2003/08/20 · arxiv updated 2009/12/01

Abstract

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.

Related

• Long monotone paths on simple 4-polytopes
• A refined lower bound theorem for d-polytopes with at most 2d vertices
• Almost simplicial polytopes I. The lower and upper bound theorems
• A lower bound theorem for d-polytopes with 2d+1 vertices
• More bounds on the diameters of convex polytopes