The Monotone Upper Bound Problem asks for the maximal number {\small
$M(d,n)$} of vertices on a strictly increasing edge-path on a simple {\small
$d$}-polytope with {\small $n$} facets. More specifically, it asks whether the
upper bound{\small
\[
M(d,n)\ \le\ M_{\rm ubt}(d,n)
\]}\!\!
¶ provided by McMullen's [McMullen 70] Upper Bound Theorem is tight, where
{\small $M_{\rm 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 {\small $M(d,n)\le
M_{\rm ubt}(d,n)$} holds with equality for small dimensions ({\small $d\le 4$}
[Pfeifle 04]) and for small corank ({\small $n\le d+2$} [Gärtner et al. 01]).
Here we prove that it is not tight in general: in dimension {\small
$d=6$}, a polytope with {\small $n=9$} facets can have {\small $ M_{\rm
ubt}(6,9)=30$} vertices, but not more than {\small $M(6,9)\le29$}
vertices can lie on a strictly increasing edge-path.
¶ The proof involves classification results about neighborly
polytopes of small corank, Kalai's [Kalai 88] concept of abstract objective
functions, the
Holt-Klee conditions [Holt and Klee 98],
explicit enumeration, Welzl's extended Gale diagrams [Welzl 01], and randomized
generation of instances, as well as nonrealizability proofs via a version of
the Farkas lemma.