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?
Best Answer
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.