To Cover a Permutohedron

The permutohedron 𝑃 𝑛 of order 𝑛 is a polytope embedded in ℝ 𝑛 whose vertex coordinates are permutations of the first 𝑛 natural numbers. It is obvious that 𝑃 𝑛 lies on the hyperplane H 𝑛 consisting of points whose coordinates sum up to 𝑛(𝑛 + 1)/2. We prove that if the vertices of 𝑃 𝑛 are contained in the union of 𝑚 affine hyperplanes different from H 𝑛 , then 𝑚 ≥ 𝑛 when 𝑛 ≥ 3 is odd, and 𝑚 ≥ 𝑛 − 1 when 𝑛 ≥ 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 𝑛 distinct real numbers to require at least 𝑛 non-trivial hyperplanes to cover its vertices.