On the monotone upper bound problem. (English) Zbl 1068.52019

Pfeifle, Julian; Ziegler, Günter M.

Exp. Math. 13, No. 1, 1-11 (2004).

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.

Reviewer: Carla Peri (Milano-Largo)

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

Keywords:

convex polytopes; monotone paths; upper bound problem; abstract objective functions; extended Gale diagrams

Software:

polymake

References:

[1]	DOI: 10.1112/S0025579300004873 · Zbl 0284.52001 · doi:10.1112/S0025579300004873
[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 · 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 · 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 · doi:10.1007/BF02773157
[10]	DOI: 10.1016/0097-3165(88)90064-7 · Zbl 0673.05087 · doi:10.1016/0097-3165(88)90064-7
[11]	DOI: 10.1137/0113062 · Zbl 0141.21303 · doi:10.1137/0113062
[12]	Klee V., Inequalitites, III pp 159– (1972)
[13]	DOI: 10.1112/S0025579300002850 · Zbl 0217.46703 · doi:10.1112/S0025579300002850
[14]	DOI: 10.1007/s004540010046 · Zbl 0956.05048 · doi:10.1007/s004540010046
[15]	Morris W. D., Distinguishing Cube Orientations Arising from Linear Programs. (2002)
[16]	DOI: 10.1090/S0002-9904-1957-10103-7 · 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 · doi:10.1007/s004540010085
[20]	Ziegler G. M., Lectures on Polytopes (1998) · Zbl 0823.52002
[21]	DOI: 10.1007/978-3-642-56478-9_34 · doi:10.1007/978-3-642-56478-9_34