8
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ What is $conv$? Convex hull? $\endgroup$
    – anomaly
    Apr 23, 2019 at 12:35
  • 1
    $\begingroup$ Exploit the symmetry of the construction to show that every vertex has the same number of neighbors, then count the total number of edges of the object. $\endgroup$
    – anomaly
    Apr 23, 2019 at 12:36

3 Answers 3

2
+50
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for your nice answers, but I selected @glen-whitney 's answer as it seemed more intuitive to me! $\endgroup$
    – Doc
    Apr 29, 2019 at 13:07
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.