Permutohedron

Example

Let $n \ge 1$. The permutohedron $\Pi_n$ is the convex hull in $\R^n$ of the $n!$ points $$(\sigma(1), \sigma(2), \dots, \sigma(n)),$$ where $\sigma$ runs over all permutations of $\set{1, \dots, n}$.

All these points satisfy $x_1 + \cdots + x_n = n(n+1)/2$, so $\Pi_n$ lies in a hyperplane, and it has dimension $n - 1$. Each of the $n!$ points is a vertex: the vector $c = (\sigma(1), \dots, \sigma(n))$ is maximised over the points uniquely at that point, by the rearrangement inequality. The facets correspond to the nonempty proper subsets $S \subset \set{1, \dots, n}$, with facet inequality $$\sum_{i \in S} x_i \ge \frac{\abs{S}(\abs{S}+1)}{2},$$ so there are $2^n - 2$ facets. Two vertices are joined by an edge exactly when one is obtained from the other by swapping the values $k$ and $k+1$ for some $k$. Hence every vertex lies in $n - 1$ edges and $\Pi_n$ is a simple polytope.

$\Pi_n$ is a zonotope: it is a translate of the Minkowski sum of the segments $[0, e_j - e_i]$ for $1 \le i < j \le n$.