Nice embedding of the permutohedron of order $n$ in ${\mathbb R}^{n-1}$

Question

The permutohedron $P_n$ of order $n$ ($n\geqslant 2$) is the convex hull of the points $P_\pi=(\pi(1),\dots,\pi(n))$ where $\pi$ ranges over all permutations of $\{1,2,\dots,n\}$. Obviously, since these points are all in the plane with equation $x_1+\dots+x_n=\frac{n(n+1)}{2}$, the polytope $P_n$ has dimension at most $n-1$. If I am not wrong, its dimension is exactly $n-1$.

Is it possible to find a "nice" embedding of $P_n$ in ${\mathbb R}^{n-1}$? "Nice" means here a simple description of the vertices. Since I am mostly interested in the combinatorics of polytopes, my question can be formulated as: is there a $(n-1)$-polytope in ${\mathbb R}^{n-1}$ with a description of vertices is as simple as possible and that is combinatorially equaivalent to $P_n$?

Answer 1

Here is a way to obtain a projection with « not too ugly » coordinates with Mathematica:

1. You generate the points in $\mathbb{R}^n$ with Permutations[{1,...,n}];
2. You apply the rotation matrix RotationMatrix[{{1,...,1},{0,...,0,1}}] to your points;
3. You forget the last coordinate, which is now the same for all points.

For the 3-dimensional permutohedron, you obtain the following coordinates which are « not too ugly »: {{-2, -1, 0}, {-(5/3), -(2/3), 4/3}, {-2, 0, -1}, {-(4/3), 2/3, 5/ 3}, {-(5/3), 4/3, -(2/3)}, {-(4/3), 5/3, 2/3}, {-1, -2, 0}, {-(2/3), -(5/3), 4/3}, {0, 1, 2}, {-1, 0, -2}, {-(2/3), 4/ 3, -(5/3)}, {0, 2, 1}, {0, -2, -1}, {2/3, -(4/3), 5/3}, {1, 0, 2}, {0, -1, -2}, {2/3, 5/3, -(4/3)}, {1, 2, 0}, {4/ 3, -(5/3), -(2/3)}, {5/3, -(4/3), 2/3}, {2, 0, 1}, {4/ 3, -(2/3), -(5/3)}, {5/3, 2/3, -(4/3)}, {2, 1, 0}}

This gives the following symmetric picture:

For the combinatorial part, Saneblidze-Umble have a subdivision of the cube which is combinatorially equivalent to the permutohedron, which might be of interest: https://arxiv.org/pdf/math/0209109.pdf

Answer 2

I'll start by admitting I don't know any good $(n-1)$-dimensional realizations of the permutohedron $P_n$. Well, it turns out the permutohedron is an "omnitrucated simplex", but the coordinates are still not very pleasant, and not very enlightening.

As consolation, I'll offer my preferred method of working with the combinatorial structure of the permutohedron.

The permutohedron turns out to belong to a class of combinatorial polytopes called graph associahedra, and you can find the paper by Carr and Devadoss here. This paper by Devadoss gives more details on how exactly the permutohedron is a graph associahedron (but note: his realization is still "one dimension too large" for your purposes). This paper, although focused on a generalization of graph associahedra, has a still more detailed account of the permutohedron, as well as more nice pictures.

Here's a picture I created, showing the facets of $P_4$ as "tubes" (=connected subgraphs) of the complete graph $K_4$ (the missing hexagonal facet is labeled with the "outer" triangle of $K_4$):

The faces corresponding to the intersection of some facets are simply the set containing the corresponding tubes, a so-called "tubing" (= set of compatible tubes).

The "spark notes" version is that:

$k$-dimensional faces of the permutohedron $P_n$ are in bijection with chains of subsets of $[n] = \{1, 2, \ldots, n\}$ of length $n - k$, if we include $[n]$ in the chain (but never $\varnothing$). The face lattice is isomorphic to the partially order set of chains of $[n]$, ordered by reverse inclusion. For example, the chain

$$\{3\} \subset \{1, 3\} \subset \{1, 3, 4\} \subset [4]$$

of length $4$ determines a $4 - 4 = 0$ dimensional face of $P_4$; a vertex (the vertex associated with $(3, 1, 4, 2) \in \Bbb R^4$). Adjacent vertices are obtained by replacing one subset in the chain. Thus, the three adjacent vertices are

\begin{align*} \{1\} &\subset \{1, 3\} \subset \{1, 3, 4\} \subset [4]\\ \{3\} &\subset \{1, 4\} \subset \{1, 3, 4\} \subset [4]\\ \{3\} &\subset \{1, 3\} \subset \{1, 2, 3\} \subset [4]. \end{align*}

Because of this description, we can also pick out facets (faces of codimension $1$) rather easily: they're in bijection with proper, nonempty subsets of $[n]$. Still thinking of $P_4$, let us choose $\{1, 3\}$, and examine its corresponding facet.

Its vertices are just those maximal (= length $4$ here) chains containing $\{1, 3\}$, and the edges those chains of length $3 = 4 - 1$ and two vertices share an edge if they differ by a single subset. Let's take a walk around the vertices of $\{1, 3\}$, starting (arbitrarily) at the chain $$\{3\} \subset \{1, 3\} \subset \{1, 3, 4\} \subset [4]$$ mentioned above:

\begin{array}{|c|c|r|}\hline \text{Vertex} & \text{Edge} & \text{Description} \\ \hline \{3\} \subset \{1, 3\} \subset \{1, 3, 4\} \subset [4] & \\ &\{1, 3\} \subset \{1, 3, 4\} \subset [4] &\text{remove }\{3\}\\ \{1\} \subset \{1, 3\} \subset \{1, 3, 4\} \subset [4] & &\text{add }\{1\}\\ &\{1\} \subset \{1, 3\} \subset [4] &\text{remove }\{1,3,4\}\\ \{1\} \subset \{1, 3\} \subset \{1, 2, 3\} \subset [4] & &\text{add }\{1,2,3\}\\ &\{1, 3\} \subset \{1, 2, 3\} \subset [4] &\text{remove }\{1\}\\ \{3\} \subset \{1, 3\} \subset \{1, 2, 3\} \subset [4] & &\text{add }\{3\}\\ & \{3\} \subset \{1, 3\} \subset [4] & \text{remove }\{1,2,3\}\\ \{3\} \subset \{1, 3\} \subset \{1, 3, 4\} \subset [4] & & \text{add }\{1,3,4\} \\ \hline \end{array}

If we label the vertices of our complete graph $K_4$ with elements of $[4]$ starting with $1$ at the top, increasing as we move clockwise, with $4$ in the center, then the facet we traced is the square in the top left corner of the above drawing.

As you can see, I'm quite a fan of the permutohedron. The fact that the permutohedron has a combinatorial interpretation makes it particularly nice to study, combinatorially.

Answer 3

There is a very simple formula. If $v(\sigma)\in\Bbb R^d$ is the vertex that corresponds to the permutation $\sigma:\{1,...,d+1\}\to\{1,...,d+1\}$, then you can choose its coordinates as

$$v_i(\sigma)=\sigma(d+1)+\sigma(i),\quad\text{for $i\in\{1,...,d\}$}.$$

---

If you want a standard permutahedron, centered at the origin and with all edges of the same length, then you can use

$$v_i(\sigma) = \frac{d+2}2 -\frac{\sigma(d+1)}{\sqrt{d+1}}-\sigma(i)\Big(1-\frac1{\sqrt{d+1}}\Big).$$

All edges are of length $$\sqrt2\Big(1-\frac1{\sqrt{d+1}}\Big).$$

---

If you use the Mathematica code with the second formula

vert[d_] := Table[
   (d+2)/2-s[[d+1]]/Sqrt[d+1]-s[[i]](1-1/Sqrt[d+1]),
{s,Permutations[Range[d+1]]}, {i,1,d}]

then vert[1] gives you the points $1/2-1/\sqrt2$ and $-1/2+1/\sqrt2$.

And if you use ConvexHullMesh to plot vert[2] and vert[3] you find