Permutohedron

The permutohedron of order 4

In mathematics, the permutohedron (also spelled permutahedron) of order Template:Mvar is an Template:Math-dimensional polytope embedded in an Template:Mvar-dimensional space. Its vertex coordinates (labels) are the permutations of the first Template:Mvar natural numbers. The edges identify the shortest possible paths (sets of transpositions) that connect two vertices (permutations). Two permutations connected by an edge differ in only two places (one transposition), and the numbers on these places are neighbors (differ in value by 1).

The image on the right shows the permutohedron of order 4, which is the truncated octahedron. Its vertices are the 24 permutations of Template:Math. Parallel edges have the same edge color. The 6 edge colors correspond to the 6 possible transpositions of 4 elements, i.e. they indicate in which two places the connected permutations differ. (E.g. red edges connect permutations that differ in the last two places.)

History

According to Template:Harvs, permutohedra were first studied by Template:Harvs. The name permutoèdre was coined by Template:Harvs. They describe the word as barbaric, but easy to remember, and submit it to the criticism of their readers.

The alternative spelling permutahedron is sometimes also used. Permutohedra are sometimes called permutation polytopes, but this terminology is also used for the related Birkhoff polytope, defined as the convex hull of permutation matrices. More generally, Template:Harvs uses that term for any polytope whose vertices have a bijection with the permutations of some set.

Vertices, edges, and facets

Template:Color, Template:Color, facets, Template:Color Face dimension Template:Math.

Template:Color Template:Color Template:Color Template:Color Template:Color Template:Color Template:Color Template:Color Template:Color Template:Color 1 Template:Color Template:Color Template:Color Template:Color 1 14 Template:Color Template:Color Template:Color Template:Color 1 30 150 Template:Color Template:Color Template:Color

The permutohedron of order Template:Math has Template:Math vertices, each of which is adjacent to Template:Math others. The number of edges is Template:Math, and their length is Template:Math.

Two connected vertices differ by swapping two coordinates, whose values differ by 1. The pair of swapped places corresponds to the direction of the edge. (In the example image the vertices Template:Math and Template:Math are connected by a blue edge and differ by swapping 2 and 3 on the first two places. The values 2 and 3 differ by 1. All blue edges correspond to swaps of coordinates on the first two places.)

The number of facets is Template:Math, because they correspond to non-empty proper subsets Template:Math of Template:Math. The vertices of a facet corresponding to subset Template:Math have in common, that their coordinates on places in Template:Math are smaller than the rest.

Facet examples
For order 3 the facets are the 6 edges, and for order 4 they are the 14 faces. The coordinates on places Template:Math where Template:Math are marked with a dark background. It can be seen, that they are smaller than the rest. The square on top corresponds to the subset Template:Math. In its four vertices the coordinates on the last two places have the smallest values (namely 1 and 2).
order 3		order 4
1-element subsets	2-element subsets	1-element subsets	2-element subsets	3-element subsets
		Error creating thumbnail:	File:Permutohedron 4 subsets 2 (first).svg	Error creating thumbnail:

More generally, the faces of dimensions 0 (vertices) to Template:Math (the permutohedron itself) correspond to the strict weak orderings of the set Template:Math. So the number of all faces is the Template:Math-th ordered Bell number. A face of dimension Template:Math corresponds to an ordering with Template:Math equivalence classes.

Face examples
order 3	order 4
File:Weak orderings 3 Hasse.svg
The images above show the face lattices of the permutohedra of order 3 and 4 (without the empty faces). Each face center is labelled with a strict weak ordering. E.g. the square on top as Template:Nowrap, which represents Template:Math. The orderings are partially ordered by refinement, with the finer ones being on the outside. Moving along an edge toward the inside means merging two neighbouring equivalence classes. The vertex labels Template:Nowrap interpreted as permutations Template:Nowrap are those forming the Cayley graph. Facets among the faces The before mentioned facets are among these faces, and correspond to orderings with two equivalence classes. The first one is used as the subset Template:Math assigned to the facet, so the ordering is Template:Math. The images below show how the facets of the Template:Math-permutohedron correspond to the simplical projection of the Template:Math-cube. The binary coordinate labels correspond to the subsets Template:Math, e.g. 0011 to Template:Math. (The vertex projected to the center does not correspond to a facet. Nor does its opposite vertex in the Template:Math-cube, which is not part of the projection.) File:Tetrahedral tesseract shadow with bit patterns (first).svg

The number of faces of dimension Template:Math in the permutohedron of order Template:Math is given by the triangle Template:Math Template:OEIS: $$T(n,k)=k!\cdot \left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$$ with $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$ representing the Stirling numbers of the second kind.

It is shown on the right together with its row sums, the ordered Bell numbers.

Other properties

File:Symmetric group 4; Cayley graph 1,2,6 (1-based).png

The permutohedron-like Cayley graph of Template:Math (see here for a comparison with the permutohedron)

The permutohedron is vertex-transitive: the symmetric group Template:Math acts on the permutohedron by permutation of coordinates.

The permutohedron is a zonotope; a translated copy of the permutohedron can be generated as the Minkowski sum of the Template:Math line segments that connect the pairs of the standard basis vectors.Template:Sfnp

The vertices and edges of the permutohedron are isomorphic to one of the Cayley graphs of the symmetric group, namely the one generated by the transpositions that swap consecutive elements. The vertices of the Cayley graph are the inverse permutations of those in the permutohedron. The image on the right shows the Cayley graph of Template:Math. Its edge colors represent the 3 generating transpositions: Template:Color, Template:Color, Template:Color.

This Cayley graph is Hamiltonian; a Hamiltonian cycle may be found by the Steinhaus–Johnson–Trotter algorithm.

Tessellation of the space

Template:Multiple image The permutohedron of order Template:Mvar lies entirely in the Template:Math-dimensional hyperplane consisting of all points whose coordinates sum to the number:

$$1+2+\dots +n=\frac{n(n+1)}{2}$$

Moreover, this hyperplane can be tiled by infinitely many translated copies of the permutohedron. Each of them differs from the basic permutohedron by an element of a certain Template:Math-dimensional lattice, which consists of the Template:Mvar-tuples of integers that sum to zero and whose residues (modulo Template:Mvar) are all equal: $$\begin{array}{cc}& x_1+x_2+\dots +x_n=0\\ & x_1\equiv x_2\equiv \dots \equiv x_n(\mathrm{mod}n).\end{array}$$

This is the lattice $A_{n-1}^{*}$, the dual lattice of the root lattice $A_{n-1}$. In other words, the permutohedron is the Voronoi cell for $A_{n-1}^{*}$. Accordingly, this lattice is sometimes called the permutohedral lattice.Template:Sfnp

Thus, the permutohedron of order 4 shown above tiles the 3-dimensional space by translation. Here the 3-dimensional space is the affine subspace of the 4-dimensional space Template:Tmath with coordinates Template:Math that consists of the 4-tuples of real numbers whose sum is 10,

$$x+y+z+w=10.$$

One easily checks that for each of the following four vectors,

$$(1,1,1,-3),(1,1,-3,1),(1,-3,1,1),(-3,1,1,1),$$

the sum of the coordinates is zero and all coordinates are congruent to 1 (mod 4). Any three of these vectors generate the translation lattice.

The tessellations formed in this way from the order-2, order-3, and order-4 permutohedra, respectively, are the apeirogon, the regular hexagonal tiling, and the bitruncated cubic honeycomb. The dual tessellations contain all simplex facets, although they are not regular polytopes beyond order-3.

Examples

Order 2	Order 3	Order 4	Order 5	Order 6
2 vertices	6 vertices	24 vertices	120 vertices	720 vertices
File:Permutohedron order 2.svg	Error creating thumbnail:	File:Permutohedron.svg	File:Omnitruncated 5Cell as Permutohedron.svg	File:Omnitruncated Hexateron as Permutohedron.svg
line segment	hexagon	truncated octahedron	omnitruncated 5-cell	omnitruncated 5-simplex

See also

• Associahedron
• Cyclohedron
• Permutoassociahedron

References

• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation Googlebook, 370–381 Also online on the KNAW Digital Library at http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
• Template:Citation.
• Template:Citation.

Further reading

• Template:Citation.
• Template:Citation
• Template:Citation

External links

• Template:Mathworld