On the Monotone Upper Bound Problem

DOI10.1080/10586458.2004.10504519MaRDI QIDQ4818674zbMATH OpenOpenAlexFDO

Authors Julian Pfeifle, Günter M. Ziegler

Publication date 1 October 2004

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0308186, https://projecteuclid.org/euclid.em/1086894086, https://eudml.org/doc/51521, http://hdl.handle.net/2117/7737

zbMATH Keywords

convex polytopesmonotone pathsabstract objective functionsextended Gale diagramsupper bound problem

Mathematics Subject Classification ID

Linear programming (90C05) Directed graphs (digraphs), tournaments (05C20) Computational aspects related to convexity (52B55) Enumeration in graph theory (05C30) Gale and other diagrams (52B35)

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

Recommendations

• Long monotone paths on simple 4-polytopes
• scientific article; zbMATH DE number 697092
• McMullen's conditions and some lower bounds for general convex polytopes
• The upper bound theorem for polytopes: An easy proof of its asymptotic version
• scientific article; zbMATH DE number 1241854

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• A simple way to tell a simple polytope from its graph
• Convex and linear orientations of polytopal graphs
• Entering and leaving \(j\)-facets
• Lectures on Polytopes
• Long monotone paths on simple 4-polytopes
• On the \(k\)-systems of a simple polytope
• One line and \(n\) points
• Paths on Polyhedra. I
• The maximum numbers of faces of a convex polytope
• The number of simplicial neighbourly d ‐polytopes with d +3 vertices
• polymake: a framework for analyzing convex polytopes

Cited in

(11)

• scientific article; zbMATH DE number 7203478 (Why is no real title available?)
• Cellular Strings on Polytopes
• The number of extreme points of tropical polyhedra
• A Mihalisin-Klee theorem for fans
• Random walks on polytopes of constant corank
• Computing monotone disjoint paths on polytopes
• On the length of monotone paths in polyhedra
• Monotone paths in planar convex subdivisions and polytopes
• Monotone diameter of bisubmodular polyhedra
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Long monotone paths on simple 4-polytopes

Describes a project that uses

Uses Software

• polymake

This page was built for publication: On the Monotone Upper Bound Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4818674)