# zbMATH — the first resource for mathematics

On the monotone upper bound problem. (English) Zbl 1068.52019
The Monotone Upper Bound Problem asks for the maximum number $$M(d,n)$$ of vertices of a $$d$$-dimensional polytope with $$n$$ facets which could lie on a monotone path (that is, an edge-path that is strictly monotone with respect to a linear objective function). By McMullen’s Upper Bound Theorem $M(d,n)\leq M_{ubt}(d,n),$ where $$M_{ubt}(d,n)$$ denotes the number of vertices of a dual-to-cyclic d-dimensional polytope with n facets.
It was recently shown that equality holds for small dimensions, $$d\leq 4$$, and for small corank, $$n-d\leq 2$$. The authors carry out a detailed analysis of some cases of corank $$n-d=3$$ which yields the following result: In dimension $$d=6$$, a polytope with $$n=9$$ facets can have $$M_{ubt}(6,9)=30$$ vertices, but not more than $$M(6,9)\leq 29$$ vertices can lie on a monotone path.

##### MSC:
 52B55 Computational aspects related to convexity 52B35 Gale and other diagrams 90C05 Linear programming 05C20 Directed graphs (digraphs), tournaments 05C30 Enumeration in graph theory
polymake
Full Text:
##### References:
  DOI: 10.1112/S0025579300004873 · Zbl 0284.52001  Amenta N., Advances in Discrete and Computational Geometry pp 57– (1998)  Gärtner, B., Solymosi, J., Tschirschnitz, F., Valtr, P. and Welzl, E. ”One Line andnPoints.”. Proceedings 33rd Annual ACM Symposium on the Theory of Computing (STOC). pp.306–315. New York: ACM. [Gärtner et al. 01] · Zbl 1323.90038  Gawrilow E., ”Polymake: A Software Package for Analyzing Convex Polytopes.” (1998) · Zbl 0960.68182  DOI: 10.1007/978-3-0348-8438-9_2  Grünbaum B., Graduate Texts in Mathematics 221, (2003)  DOI: 10.1007/s00454-001-0085-0  Holt F., Advances in Discrete and Computational Geometry pp 201– (1998)  DOI: 10.1007/BF02773157 · Zbl 1009.52021  DOI: 10.1016/0097-3165(88)90064-7 · Zbl 0673.05087  DOI: 10.1137/0113062 · Zbl 0141.21303  Klee V., Inequalitites, III pp 159– (1972)  DOI: 10.1112/S0025579300002850 · Zbl 0217.46703  DOI: 10.1007/s004540010046 · Zbl 0956.05048  Morris W. D., Distinguishing Cube Orientations Arising from Linear Programs. (2002)  DOI: 10.1090/S0002-9904-1957-10103-7  Pfeifle, J. 2004.”Long Monotone Paths on Simple 4–Polytopes.”19 [Pfeifle 04], Preprint, arXiv: math.MG/ 0402247 · Zbl 1129.52301  Schrijver A., Theory of Linear and Integer Programming (1986) · Zbl 0665.90063  DOI: 10.1007/s004540010085 · Zbl 0982.52012  Ziegler G. M., Lectures on Polytopes (1998) · Zbl 0823.52002  DOI: 10.1007/978-3-642-56478-9_34
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.