Why is the permutohedron simple? 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.
 A: 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.
A: 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.
A: 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.
