To cover a permutohedron

Abstract

The permutohedron $P_n$ of order $n$ is a polytope embedded in ${\mathbb{R}}^n$ whose vertex coordinates are permutations of the first $n$ natural numbers. It is obvious that $P_n$ lies on the hyperplane $H_n$ consisting of points whose coordinates sum up to $n(n+1)/2$. We prove that if the vertices of $P_n$ are contained in the union of $m$ affine hyperplanes different from $H_n$, then $m\ge n$ when $n\ge 3$ is odd, and $m\ge n-1$ when $n\ge 4$ is even. This result has been established by Pawlowski in a more general form. Our proof is shorter, rather different, and gives an algebraic criterion for a non-standard permutohedron generated by $n$ distinct real numbers to require at least $n$ non-trivial hyperplanes to cover its vertices.