Why is the permutohedron simple?

Question

I am working with the permutohedron in $\mathbb{R}^n$ which is defined as the convex hull of $n!$ vectors as follows: $$\Pi_n := conv\{(\sigma(1), \ldots, \sigma(n))\ |\ \sigma \text{ permutation of } [n]\}$$

I want to show that this polytope is simple and $n-1$ dimensional. To prove that $dim(\Pi_n)= n-1$ was easy. I further proved that $\Pi_n$ has exactly $n!$ vertices as expected.

But why is the permutohedron simple, i.e. why has every vertex exactly $n-1$ neighbors?

I've read that the vertices form an edge if they differ in a transposition between two elements that differ by 1. Unfortunately, I was not able to prove that (this would yield the simplicity). How does one prove that? Thanks a lot

P.S.: I already checked this thread, however it hasn't received any answers yet.

Answer 1

By @anomaly's comment, you only need to count the edges at any one vertex. Notice further that the projection which simply drops the $n$th coordinate is injective and dimension-preserving on the vertices of the permutahedron, so the convex hull in the first $n-1$ dimensions has the same combinatorial structure as the original permutahedron. In this structure, the set of points with greatest ($n-1$)st coordinate is clearly both (a) on the convex hull and (b) a copy of the order $n-1$ permutahedron. So by induction each vertex of it has $n-2$ edges in that same layer; we just have to find at least one vertex of it that has only a single edge in which the ($n-1$)st coordinate changes. But in particular, looking along the $n-1$st coordinate, the vertices which consist of all permutations of (1,2,...,$n-2$) followed by $n$ lie directly "above" the same permutation of (1,2,...,$n-2$) followed by $n-1$, so they must each have a single additional edge in the overall convex hull, parallel to the $n-1$st axis. This completes the proof.

Answer 2

Here is proof using Minkowski sums.

We work with permutations of $(0, \ldots, n-1)$ instead of $(1,\ldots, n)$. This is clearly equivalent, just subtract 1 from every coordinate. As usual the basis vector is $e_i$ is the one with $i$th coordinate equal $1$ and all the others equal to zero.

Step 1, permutahedron as a zonotope (sum of segments): The permutahedron is the Minkowski sum of $\frac{n(n-1)}{2}$ segments with vertices $e_i, e_j$ with $i< j$.

Proof: Permutahedron is the Newton polytope of the determinant of matrix $A_{ij}=t_i^{j-1}$ (indeed, this determinant is sum over permutations $\sigma$ of $(1,\ldots, n)$ of $sign(\sigma)\prod_i t_i^{\sigma(i)-1}$, so the Newton polytope is by definition the convex hull of $(\sigma(1)-1, \ldots, \sigma(n)-1)$, i.e. the permutahedron we are working with).

This matrix is the Vandermonde matrix, so the determinant is the Vandermonde determinant $\prod_{i> j} (t_i-t_j)$. The Newton polytope of a product is the Minkowski sum of the Newton polytopes of the terms (this follows directly from the definitions, since when monomials multiply their powers add). Since the Newton polytope of $t_i-t_j$ is the segments with vertices $e_i, e_j$ the Step 1 follows.

Step 2, the vertices and the edges:

The vertices $V$ of the Minkowski sum are a subset of the $\Sigma V=${sums of vertices of the summands}. That is, every vertex is obtained by choosing for each $i<j$ one of the $e_i$ or $e_j$ and summing all the choices. Not all the resulting sums are vertices -- many lie in the interior. However, you have already proved that the vertices are precisely all $n!$ points $(\sigma(0), \ldots, \sigma(n-1))$. The point is that the edges of the Minkowski sum are a subset of $\Sigma E$=the set of segments obtained by summing vertices of all but one of the summands and an edge of the remaining summand; such a segment is an edge precisely when it connects two points that are actually in $V$ (and not just in $\Sigma V$). Now we are home free: the two points that any such edge connects differ by switching one of the $e_i$ summands to the other vertex of the some segment i.e. to some other $e_j$; that means subtracting 1 from the $i$th coordinate and adding it to the $j$th coordinate. The only case that this transitions from one permutation to another is when $\sigma(i)=k+1$ and $\sigma(j)=k$ for some $k=0, 1, \ldots, n-1$, and in all those cases the resulting segment does in fact connect two permutations/vertices. That is, there are exactly $n-1$ edges from every vertex.

Answer 3

Here is a direct proof.

Consider $P_n$ which is defined as the convex polyhedron cut out inside $V=\{\sum_i x_i=1+\ldots +n={n+1\choose 2}\}$ by the half-spaces $H_I$ indexed by non-empty proper subsets $I\subset \{1, \ldots, n\}$ where $H_I=\{ (x_1, \ldots, x_n)| \sum_{i\in I} x_i \geq 1+\ldots+|I|= {|I|+1\choose 2}\}$. We will study the face lattice of $P_n$. We will identify the face lattice of $P_n$ with the graded partially ordered set $SC$ where the elements of $SC$ are chains of unequal non-empty proper subsets $\emptyset \subset I_1 \subset I_2\subset \ldots \subset I_k \subset \{1, 2, \ldots, n\}$ partially ordered by refinement, and graded via the length of the chain.

In particular this will identify the vertices of $P_n$ with maximal chains of subsets; then it is easy to see that they are precisely the vertices of $\Pi_n$, proving that the two polyhedra are the same.

Assuming this description of the face lattice of $\Pi_n=P_n$, proving that it is a simple polytope is easy: every vertex corresponds to a maximal (length $n-1$) chain, and is a refinement of $n-1$ chains of length $n-2$ (obtained from it by removing exactly one of $I_k$s), thus has degree $n-1$.

So the task is to prove that the face lattice of $P_n$ is as described.

We denote the hyperplane bounding $H_I$ by $V_I$.

Step 1, facets.

Claim 1: For each $I$, there is a facet $F_I$ of $P_n$ contained in $V_I$.

Proof: Given $I$ we construct $p_I \in P_n\cap V_I$ which is not in any other $V_J$. Such $p_I$ is not the interior of $P_n$ and not in any higher codimension face, so must in the facet that is in $V_I$. To get $p_I$, we take the point with each coordinates $x_i$ equal to either $\frac{{|I|+1 \choose 2}}{|I|}$ if $i\in I$ or to $\frac{{n+1\choose 2}-{|I|+1 \choose 2}}{n-|I|}$ if $i\notin I$. $\square$

Since every facet of an $H$ polytope is contained in some defining hyperplane, we have identified all the facets.

We build a map $\phi$ of posets from $SC$ to face lattice of $P_n$ by sending $\emptyset \subset I_1 \subset I_2\subset \ldots \subset I_k \subset \{1, 2, \ldots, n \}$ to $\cap F_{I_k}$. Our goal is to show that $\phi$ is an isomorphism of graded lattices.

Step 2: Now we check that $\phi$ is surjective.

Claim 2: Unless ($I\subseteq J$ or $J\subseteq I$) we have $V_I\cap V_J\cap H_{I\cup J}\cap H_{I\cap J}=\emptyset$, implying $F_I\cap F_j=\emptyset$.

Proof: Write out the inequalities and equations and observe that they are inconsistent.$\square$

This means that every proper face $F$ of $P_n$ is an intersection of facets $F_{I_k}$ with $I_k$ forming a chain of subsets, i.e. $F$ is in the image of $\phi$.

Step 3. Now we check that $\phi$ is injective.

It is enough to see that the image of $\phi$ contains all the vertices (coatoms), since every element is a join of vertices.

Observation 2: Any maximal chain $C$ of subsets (of length $n-1$) is of the form $\emptyset \subset I_\sigma^1=\{\sigma(1)\} \subset I_\sigma^2=\{\sigma(1), \sigma(2)\} \subset \ldots \subset I_\sigma^{n-1}=\{\sigma(1), \ldots, \sigma(n-1) \}$ for some permutation $\sigma$. (This is clear: the $i$th subset in a maximal chain will have size $i$, and just define $\sigma$ to make the above true.) Then $\phi(C)=p_\sigma=(\sigma(1), \ldots, \sigma(n))$. (Proof: $p\in {I_\sigma^{n-1}}$ implies $x_{\sigma(n)}=n$; given which $p\in {I_\sigma^{n-1}}$ implies $x_{\sigma(n-1)}=n-1$; etc.).

Corollary: For any permutation $\sigma$ we have $p_\sigma=(\sigma(1), \ldots, \sigma(n)) \in P$. (This is also easy to see directly).

Hence $\phi$ is surjective, vertices of $P_n$ correspond to maximal chains and are exactly the vertices of $\Pi_n$, and we are done.