  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\"artner 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.
