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.

52B55 Computational aspects related to convexity
52B35 Gale and other diagrams
90C05 Linear programming
05C20 Directed graphs (digraphs), tournaments
05C30 Enumeration in graph theory
Full Text: DOI Euclid EuDML arXiv
[1] DOI: 10.1112/S0025579300004873 · Zbl 0284.52001
[2] Amenta N., Advances in Discrete and Computational Geometry pp 57– (1998)
[3] 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
[4] Gawrilow E., ”Polymake: A Software Package for Analyzing Convex Polytopes.” (1998) · Zbl 0960.68182
[5] DOI: 10.1007/978-3-0348-8438-9_2
[6] Grünbaum B., Graduate Texts in Mathematics 221, (2003)
[7] DOI: 10.1007/s00454-001-0085-0
[8] Holt F., Advances in Discrete and Computational Geometry pp 201– (1998)
[9] DOI: 10.1007/BF02773157 · Zbl 1009.52021
[10] DOI: 10.1016/0097-3165(88)90064-7 · Zbl 0673.05087
[11] DOI: 10.1137/0113062 · Zbl 0141.21303
[12] Klee V., Inequalitites, III pp 159– (1972)
[13] DOI: 10.1112/S0025579300002850 · Zbl 0217.46703
[14] DOI: 10.1007/s004540010046 · Zbl 0956.05048
[15] Morris W. D., Distinguishing Cube Orientations Arising from Linear Programs. (2002)
[16] DOI: 10.1090/S0002-9904-1957-10103-7
[17] Pfeifle, J. 2004.”Long Monotone Paths on Simple 4–Polytopes.”19 [Pfeifle 04], Preprint, arXiv: math.MG/ 0402247 · Zbl 1129.52301
[18] Schrijver A., Theory of Linear and Integer Programming (1986) · Zbl 0665.90063
[19] DOI: 10.1007/s004540010085 · Zbl 0982.52012
[20] Ziegler G. M., Lectures on Polytopes (1998) · Zbl 0823.52002
[21] 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.