Inner diagonals of convex polytopes. (English) Zbl 0948.52003

Bremner, David; Klee, Victor

J. Comb. Theory, Ser. A 87, No. 1, 175-197 (1999).

For \(1\leqslant i\leqslant d,\) an \(i\)-diagonal of a \(d\)-polytope \(P\) is a segment \([x,y]\) whose ends are vertices of \(P\) and whose carrier in \(P\) is of dimension \(i.\) The number of \(i\)-diagonals is denoted by \(\delta_i(P).\) Thus \(\delta_1(P)\) is the number of edges and \(\delta_d(P)\) is the number of inner diagonals. The focus here is on \(\delta_d(P).\)
The paper’s main results are as follows:
(a) Within the class of \(d\)-polytopes that have a given number \(v\) of vertices, the maximum of \(\delta_d(P)\) is \(\binom v2-dv+\binom{d+1}{2}.\) For \(d\geqslant 4\) this maximum is attained by the stacked polytopes and only by them.
(b) Within the class of \(d\)-polytopes that have a given number \(f\geqslant 2d\) of facets, the maximum of \(\delta_d(P)\) is attained by certain simple \(d\)-polytopes.
(c) For each simplicial 3-polytope with \(f\) facets \(\delta_3(P)=(f^2-6f+8)/8,\) while for simple 3-polytopes \(\delta_3(P)\) ranges from \(f^2-9f+20\) to (when \(f\geqslant 14\)) \(2f^2-21f+64.\)

Reviewer: Serguey M.Pokas (Odessa)

MSC:

52B11

\(n\)-dimensional polytopes

Keywords:

convex polytope; 3-polytope; \(d\)-polytope; simple polytope; simplicial polytope; combinatorial type; \(p\)-vector; \(i\)-diagonal; wedge; inner diagonal; estranged vertex-pairs

References:

[1]	Avis, D., Generating rooted triangulations without repetitions, Algorithmica, 16, 618-632 (1996) · Zbl 0860.68107
[2]	Barnette, D., A proof of the lower bound conjecture for convex polytopes, Pacific J. Math., 46, 349-354 (1973) · Zbl 0264.52006
[3]	Carathéodory, C., Über die Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Palermo, 32, 193-217 (1911) · JFM 42.0429.01
[4]	Eberhard, V., Zur Morphologie der Polyeder (1891), Teubner: Teubner Leipzig · JFM 23.0544.03
[5]	Eggleston, H. G.; Grünbaum, B.; Klee, V., Some semicontinuity theorems for convex polytopes and cell-complexes, Comment. Math. Helv., 39, 165-188 (1964) · Zbl 0137.41802
[6]	Fisher, J. C., An existence theorem for simple convex polyhedra, Discrete Math., 7, 75-97 (1974) · Zbl 0271.52008
[7]	D. Gale, Neighborly and cyclic polytopes, in Convexity (V. Klee, Ed.), Proc. Sympos. Pure Math., Vol. 7, pp. 225-232.; D. Gale, Neighborly and cyclic polytopes, in Convexity (V. Klee, Ed.), Proc. Sympos. Pure Math., Vol. 7, pp. 225-232. · Zbl 0137.41801
[8]	Grünbaum, B., Convex Polytopes (1967), Wiley-Interscience: Wiley-Interscience London
[9]	Grünbaum, G., Polytopal graphs, (Fulkerson, D. R., Studies in Graph Theory. Studies in Graph Theory, MAA Studies in Mathematics, 12 (1975), Math. Assoc. of America: Math. Assoc. of America Washington), 201-224 · Zbl 0323.05104
[10]	Grünbaum, B.; Motzkin, T. S., The number of hexagons and the simplicity of geodesics on certain polyhedra, Canad. J. Math., 15, 744-751 (1963) · Zbl 0121.37605
[11]	Grünbaum, B.; Sreedharan, V. P., An enumeration of simplicial 4-polytopes with 8 vertices, J. Combin. Theory, 2, 437-465 (1967) · Zbl 0156.43304
[12]	Jendrol’, S., On the face-vectors of trivalent convex polyhedra, Math. Slovaca, 33, 165-180 (1983) · Zbl 0515.52004
[13]	Jucovič, E., On polyhedral realizability of certain sequences, Canad. Math. Bull., 12, 31-39 (1969) · Zbl 0185.48402
[14]	Kalai, G., Rigidity and the lower bound theorem, I, Invent. Math., 88, 125-151 (1987) · Zbl 0624.52004
[15]	Kalai, G., Some aspects of the combinatorial theory of convex polytopes, (Bisztriczky, T.; McMullen, P.; Schneider, R.; Ivić Weiss, A., Polytopes: Abstract, Convex and Computational (1993), Kluwer: Kluwer Dordrecht), 205-229 · Zbl 0804.52006
[16]	Keiding, H., On the maximal number of Nash equilibria in an \(n\)×\(n\) bimatrix game, Games Econom. Behav., 21, 148-160 (1997) · Zbl 0911.90352
[17]	Klee, V., On the number of vertices of a convex polytope, Canad. J. Math., 16, 701-720 (1964) · Zbl 0128.17201
[18]	Mani, P., Inner illumination of convex polytopes, Comment. Math. Helv., 49, 65-73 (1974) · Zbl 0275.52004
[19]	McLennan, A.; Park, I.-U., Generic 4×4 two person games have at most 15 Nash equilibria, Games Econom. Behavior, 26, 111-130 (1999) · Zbl 0930.91003
[20]	Rosenfeld, M., Inner illumination of convex polytopes, Elem. Math., 30, 27-28 (1975) · Zbl 0297.52004
[21]	Roudneff, J.-P., An inequality for 3-polytopes, J. Combin. Theory Ser. B, 42, 156-166 (1987) · Zbl 0576.05021
[22]	Stanley, R., Generalized \(h\)-vectors, intersection cohomology of toric varieties, and related results, (Nagata, M.; Matsumura, H., Commutative Algebra and Combinatorics. Commutative Algebra and Combinatorics, Advanced Studies in Pure Mathematics, 11 (1987), Kinokuniya: Kinokuniya Tokyo), 187-213
[23]	Steinitz, E.; Rademacher, H., Vorlesungen über die Theorie der Polyeder (1934), Springer-Verlag: Springer-Verlag Berlin · Zbl 0325.52001
[24]	von Stengel, B., New maximal numbers of equilibria in bimatrix games, Discrete Comput. Geom., 21, 557-568 (1999) · Zbl 0956.91003
[25]	Whiteley, W., Infinitesimally rigid polyhedra. I. Statics of frameworks, Trans. Amer. Math. Soc., 285, 431-465 (1984) · Zbl 0518.52010
[26]	Ziegler, G., Lectures on Polytopes (1994), Springer-Verlag: Springer-Verlag New York