Permutohedron
In mathematics, the permutohedron (also spelled permutahedron) of order n is an (n − 1)-dimensional polytope embedded in an n-dimensional space.
The edges identify the shortest possible paths (sets of transpositions) that connect two vertices (permutations).
The image on the right shows the permutohedron of order 4, which is the truncated octahedron.
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.
According to Günter M. Ziegler (1995), permutohedra were first studied by Pieter Hendrik Schoute (1911).
They describe the word as barbaric, but easy to remember, and submit it to the criticism of their readers.
More generally, V. Joseph Bowman (1972) uses that term for any polytope whose vertices have a bijection with the permutations of some set.
(In the example image the vertices (3, 2, 1, 4) and (2, 3, 1, 4) are connected by a blue edge and differ by swapping 2 and 3 on the first two places.
The vertices of a facet corresponding to subset S have in common, that their coordinates on places in S are smaller than the rest.
More generally, the faces of dimensions 0 (vertices) to n − 1 (the permutohedron itself) correspond to the strict weak orderings of the set {1 ... n}.
[5] A face of dimension d corresponds to an ordering with k = n − d equivalence classes.
Each face center is labelled with a strict weak ordering.
Moving along an edge toward the inside means merging two neighbouring equivalence classes.
The vertex labels a | b | c | d interpreted as permutations (a, b, c, d) are those forming the Cayley graph.
The before mentioned facets are among these faces, and correspond to orderings with two equivalence classes.
The images below show how the facets of the n-permutohedron correspond to the simplical projection of the n-cube.
The number of faces of dimension d = n − k in the permutohedron of order n is given by the triangle T (sequence A019538 in the OEIS):
It is shown on the right together with its row sums, the ordered Bell numbers.
The permutohedron is a zonotope; a translated copy of the permutohedron can be generated as the Minkowski sum of the n(n − 1)/2 line segments that connect the pairs of the standard basis vectors.
[6] 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 permutohedron of order n lies entirely in the (n − 1)-dimensional hyperplane consisting of all points whose coordinates sum to the number:
Each of them differs from the basic permutohedron by an element of a certain (n − 1)-dimensional lattice, which consists of the n-tuples of integers that sum to zero and whose residues (modulo n) are all equal:
[8] Thus, the permutohedron of order 4 shown above tiles the 3-dimensional space by translation.
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.
