The maximum number of faces of the Minkowski sum of two convex polytopes (Q309640): Difference between revisions

The paper studies the maximum number of \(k\)-faces the Minkowski sum of two \(d\)-dimensional polytopes can have for any \(k\in\{0,1,\ldots,d-1\}\). Firstly, the \textit{Cayley polytope} \(P\) of two \(d\)-polytopes \(P_1\) and \(P_2\) is the \((d+1)\)-dimensional polytope in \({\mathbb R}^{d+1}\) obtained by taking the convex hull of \(P_1\) embedded in the hyperplane \(x_1 = 0\) and \(P_2\) embedded in the hyperplane \(x_1 = 1\). Secondly, a polytope \(Q\) is said to be \textit{\((k,V_1)\)-bineighborly} if the vertex set \(V\) of \(Q\) has a partition \(V = V_1\cup V_2\) such that for every proper subsets \(S_1\subseteq V_1\) and \(S_2\subseteq V_2\) with \(|S_1|+|S_2|\leq k\), the union \(S_1\cup S_2\) is the vertex set of a \((|S_1|+|S_2|-1)\)-face of \(Q\). The main result of this paper is the following theorem: Let \(P_1\) and \(P_2\) be two \(d\)-polytopes with \(n_1\geq d+1\) and \(n_2\geq d+1\) vertices respectively. For any \(k\in\{1,\ldots,d\}\) the number \(f_{k-1}(P_1+P_2)\) of \((k-1)\)-faces of the Minkowski sum \(P_1+P_2\) is bounded from above in the following way \[ \begin{multlined} f_{k-1}(P_1+P_2) \leq f_k(C_{d+1}(n_1+n_2))\\ - \sum_{i=0}^{\lfloor (d+1)/2\rfloor}\binom{d+1-i}{k+1-i} \left(\binom{n_1-d-2+i}{i}+\binom{n_2-d-2+i}{i}\right), \end{multlined} \] where \(C_{d+1}(n_1+n_2)\) denotes the cyclic \((d+1)\)-polytope with \(n_1+n_2\) vertices. In addition, (i) equality holds for all \(k\in \{1,\ldots,l\}\) iff \(l\leq \lfloor (d-1)/2\rfloor\) and the Cayley polytope \(P\) is \((l+1,V_1)\)-bineighborly, (ii) for even \(d\geq 2\) equality holds for all \(k\in \{1,\ldots,d\}\) iff \(P\) is \(\lfloor d/2 \rfloor\)-neighborly and (iii) for odd \(d\geq 3\) equality holds for all \(k\in \{1,\ldots,d\}\) iff \(P\) is \((\lfloor (d+1)/2 \rfloor,V_1)\)-bineighborly. The proof is analogous to that of the Upper Bound Theorem by McMullen from 1970 [\textit{P. McMullen}, Mathematika 17, 179--184 (1970; Zbl 0217.46703)]. These bounds are all shown to be tight in the last section of the paper. The three figures in the paper are interesting, intricate and explanatory.