# A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

arXiv: https://arxiv.org/abs/1502.02265 · HTML: https://mlsanity.com/paper/1502.02265/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2015.

## Built on by (most cited first, 1 of 1)

- [Enumeration of max-pooling responses with generalized permutohedra](https://mlsanity.com/paper/2209.14978/) (2022)

## Abstract (arXiv)

We derive tight expressions for the maximum number of k-faces, 0≤k≤d-1, of the Minkowski sum, P1+...+Pr, of r convex d-polytopes P1,...,Pr in ℝd, where d≥2 and r<d, as a (recursively defined) function on the number of vertices of the polytopes. Our results coincide with those recently proved by Adiprasito and Sanyal [2]. In contrast to Adiprasito and Sanyal's approach, which uses tools from Combinatorial Commutative Algebra, our approach is purely geometric and uses basic notions such as f- and h-vector calculus and shellings, and generalizes the methodology used in [15] and [14] for proving upper bounds on the f-vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum P1+...+Pr as a section of the Cayley polytope C of the summands; bounding the k-faces of P1+...+Pr reduces to bounding the subset of the (k+r-1)-faces of C that contain vertices from each of the r polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds.