Is a face of a sum of polyhedra a sum of their faces?

A polyhedron is the intersection of finitely many half-spaces. A polytope is a bounded polyhedron.

Let $$P_1,P_2$$ be two polytopes. It is known that any face $$F$$ of the Minkowski sum $$P_1+P_2$$ is of the form $$F_1+F_2$$, where $$F_1$$,$$F_2$$ are faces of $$P_1$$, respectively $$P_2$$. See for example Proposition 2.1 in https://doi.org/10.1016/j.jsc.2003.08.007

My question is, whether the same statement is true for polyhedra. Intuitively, I don't see why boundedness would make a difference here. Yet, I could not find any such result about polyhedra. Moreover, if this was true/easy to prove, I would expect that the result would be proved for polyhedra directly, not for polytopes. Are there counterexamples?

It seems that the following proof works.

Let $$n$$ be the dimension of the ambient space for $$A$$ and $$B$$, I will make the harmless assumption that this ambient space is $${\mathbb R}^n$$. Also, for two vectors $$u=(u_1,\ldots,u_d)$$ and $$v=(v_1,\ldots,v_d)$$ in $${\mathbb R}^d$$, I write $$u\geq v$$ in the coordinatewise sense, i.e. it means $$u_k\geq v_k$$ for every $$k\in [1..d]$$.

Let $${\cal F}$$ be a face of $$A+B$$. Thus, there is a linear map $$\phi : {\mathbb R}^n \to {\mathbb R}^d$$ and a constant $$m\in{\mathbb R}^d$$ such that $${\cal F}=\lbrace x\in A+B \ | \ \phi(x)=m\rbrace$$, and such that $$\phi(x)\geq m$$ for every $$x\in A+B$$. This latter statement means that $$\phi(a)+\phi(b) \geq m$$ for every $$a\in A$$ and $$b\in B$$.

Clearly we can assume both $$A$$ and $$B$$ to be nonempty, and take $$a_0\in A,b_0\in B$$. Then for $$a\in A$$, $$\phi(a)\geq m-\phi(b_0)$$. We know that $$A$$ can be written as the Minkowski sum of a polytope $$P_A=Conv(a_1,\ldots,a_p)$$ and a cone $$C_A=Pos(\alpha_1,\alpha_2,\ldots,\alpha_q)$$ (and similary, $$B$$ can be written as a sum of $$Conv(b_1,\ldots,b_r)$$ and $$Pos(\beta_1,\beta_2,\ldots,\beta_s)$$).

Then, clearly $$\phi$$ has a lower bound on $$A$$ iff each $$\phi(\alpha_k) \geq 0$$ for $$1\leq k \leq q$$. It follows that $$\phi$$ attains a minimum on $$A$$, and in fact it attains it on one of $$a_1,\ldots,a_p$$ : there is an index $$i\in[|1..p|]$$ such that $$\min_A(\phi)=\phi(a_i)$$. For the same reason, there is an index $$j\in[|1..r|]$$ such that $$\min_B(\phi)=\phi(b_j)$$.

If we put $${\cal F}_A=\lbrace a\in A | \phi(a)= \phi(a_i)\rbrace$$ and $${\cal F}_B=\lbrace b\in B | \phi(b)= \phi(b_j)\rbrace$$, then by construction $${\cal F}_A$$ is a face of $$A$$ and $${\cal F}_B$$ is a face of $$B$$, and $${\cal F}={\cal F}_A+{\cal F}_B$$ as wished.

• This seems to work, many thanks! Commented Dec 5, 2022 at 18:40