  We investigate the combinatorics of max-pooling layers, which are functions
that downsample input arrays by taking the maximum over shifted windows of
input coordinates, and which are commonly used in convolutional neural
networks. We obtain results on the number of linearity regions of these
functions by equivalently counting the number of vertices of certain Minkowski
sums of simplices. We characterize the faces of such polytopes and obtain
generating functions and closed formulas for the number of vertices and facets
in a 1D max-pooling layer depending on the size of the pooling windows and
stride, and for the number of vertices in a special case of 2D max-pooling.
