In mathematics, the permutohedron (also spelled permutahedron) of order n is an (n − 1)-dimensional polytope embedded in an n-dimensional space. Its vertex coordinates (labels) are the permutations of the first n natural numbers. 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 (1, 2, 3, 4). 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 Günter M. Ziegler (1995), permutohedra were first studied by Pieter Hendrik Schoute (1911). The name permutoèdre was coined by Georges Th. Guilbaud and Pierre Rosenstiehl (1963). 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, V. Joseph Bowman (1972) uses that term for any polytope whose vertices have a bijection with the permutations of some set.
Vertices, edges, and facets
The permutohedron of order n has n! vertices, each of which is adjacent to n − 1 others. The number of edges is (n − 1) n!/2, and their length is √2. Two vertices that are connected by an edge differ by a swap of 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 (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 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 2n − 2, because they correspond to non-empty proper subsets S of {1 ... n}. 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}. So the number of all faces is the n-th ordered Bell number. A face of dimension d corresponds to an ordering with k = n − d equivalence classes.
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):
T ( n , k ) = k ! ⋅ { n k } {\displaystyle T(n,k)=k!\cdot \left\{{n \atop k}\right\}} with { n k } {\displaystyle \textstyle \left\{{n \atop 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
The permutohedron is vertex-transitive: the symmetric group Sn 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 n(n − 1)/2 line segments that connect the pairs of the standard basis vectors. The vertex-edge graph of the permutohedron is the Bruhat graph, which is a Cayley graph of the symmetric group 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 S4. Its edge colors represent the 3 generating transpositions: (1, 2), (2, 3), (3, 4). This Cayley graph is Hamiltonian; a Hamiltonian cycle may be found by the Steinhaus–Johnson–Trotter algorithm.
Tessellation of the space
The permutohedron of order n lies entirely in the (n − 1)-dimensional hyperplane consisting of all points whose coordinates sum to the number:
1 + 2 + … + n = n ( n + 1 ) 2 {\displaystyle 1+2+\ldots +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 (n − 1)-dimensional lattice, which consists of the n-tuples of integers that sum to zero and whose residues (modulo n) are all equal:
… excerpt ends here. Continue reading the full article.
