Faces of the Permutahedron

Question

We define the Permutahedron as the convex hull of all permutations of the vector $(1,2,\dots,n)\in\mathbb R^n$. I am having trouble seeing why the number of $n-k$ dimensional faces of this polytope is given by $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind. More generally, why is the face lattice of the Permutahedron given by the partition lattice?

Answer 1

The vertices of the $n$-permutahedron are all the permutations of $(1,\dotsc,n)$ in $\mathbb{R}^n$. For instance, the 3-permutahedron has the 6 vertices $(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2)$, and $(3,2,1)$. Notice that all of these lie in the plane $x + y + z = 6$, so the 3-permutahedron is actually a 2-dimensional polytope (a hexagon.)

In general, all the permutations of $(1, \dotsc, n)$ lie in the hyperplane $\sum_{i=1}^n x_i = \frac{n^2 + n}{2}$, so the $n$-permutahedron is an $(n-1)$-dimensional polytope.

Each edge at a vertex $v$ connects it to another vertex whose coordinates are the same as $v$, except that two values differing by one are transposed. For instance, in the 3-permutahedron, $(2,1,3)$ is adjacent to $(1,2,3)$ and $(3,1,2)$. With $n$ coordinates, there are $n-1$ pairs of adjacent values. So every vertex of the $n$-permutahedron is in $n-1$ edges.

The reason why all this matters is that a $d$-dimensional polytope where every vertex is incident to $d$ edges is called simple, so permutahedra are simple. And in a simple polytope, every nonempty intersection of $k$ distinct facets is an $(d-k)$-face, and vice versa.

In general, any nonempty intersection of two distinct facets (i.e. $(d-1)$-faces of a $d$-dimensional polytope) has dimension $(d-2)$ or lower, and any nonempty intersection of 3 distinct facets has dimension $(d-3)$ or lower. But a nonempty intersection of 4 distinct facets could be a $(d-4)$-face, or a $(d-3)$-face; a nonempty intersection of 5 distinct facets could be a $(d-5)$-face or $(d-4)$-face or $(d-3)$-face. This doesn't happen in a simple polytope.

Now, each facet $F$ of a permutahedron is determined by a nonempty proper subset $S$ of the coordinate positions; the vertices of $F$ are all the points where all the coordinates in $S$ are smaller than all the coordinates not in $S$. There is one facet for each nonempty proper subset of $\{1,\dotsc,n\}$, so $2^n - 2$ in total.

Consider a nonempty intersection of two facets, corresponding to subsets $S$ and $S'$ of $\{1,\dotsc,n\}$, of sizes $j$ and $k$, where $j \leq k$. Since the numbers $1, \dotsc, j$ must occur in the positions $S$, and $1, \dotsc, j, \dotsc, k$ must occur in the positions $S'$, we must have $S \subset S'$. If $S = S'$, then the two facets are identical. So every nonempty intersection of two distinct facets is determined by two nested nonempty proper subsets, $\emptyset \subsetneq S \subsetneq S' \subsetneq \{1,\dotsc,n\}$. (The vertices in the intersection are all the points where the first $j$ numbers appear in the positions in $S$, the next $k - j$ numbers appear in $S' \setminus S$, and the rest are outside of $S'$.)

Similarly, a nonempty intersection of $k$ facets corresponds to $k$ nested proper subsets, $\emptyset \subsetneq S_1 \subsetneq \dotsb \subsetneq S_k \subsetneq \{1,\dotsc,n\}$.

So, the number of $(d-k)$-faces is the number of sequences of $k$ nonempty nested proper subsets. (Here, $d = n - 1$ is the dimension of the $n$-permutahedron.)

The Stirling number of the second kind $S(n,k)$ counts the partitions of $\{1,\dotsc,n\}$ into $k$ nonempty subsets. So $k!\, S(n,k)$ counts the partitions into $k$ nonempty subsets, counting the order of the subsets.

Given a partition of $\{1,\dotsc,n\}$ into $k+1$ nonempty subsets $K_1, \dotsc, K_{k+1}$, you can construct a sequence of $k$ nonempty nested proper subsets $$ \emptyset \; \subsetneq \; K_1 \; \subsetneq \; K_1 \cup K_2 \; \subsetneq \; K_1 \cup K_2 \cup K_3 \; \subsetneq \dotsb \subsetneq \; K_1 \cup \dotsb \cup K_{k+1}. $$ The last entry in that list is the whole set $\{1,\dotsc,n\}$, so there are only $k$ proper nonempty subsets. You can also go backwards from a sequence of $k$ nonempty nested proper subsets to make a partition into $k+1$ nonempty subsets; so this is a bijection.

Hence, $(k+1)!\,S(n,k+1)$ counts the number of $(n-1-k)$-faces of the $n$-permutahedron. So the number of $(n-k)$-faces is $k!\, S(n,k)$.