On the Monotone Upper Bound Problem

Details On the Monotone Upper Bound Problem On the Monotone Upper Bound Problem

2003-08-20

arxiv.org/abs/math/0308186v1

Mathematics

Metric Geometry

15 pages; 6 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Monotone Upper Bound Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Monotone Upper Bound Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Monotone Upper Bound Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-167248