Product Code Database
In mathematics, the permutohedron (also spelled permutahedron) of order is an -dimensional polytope embedded in an -dimensional space. Its vertex coordinates (labels) are the of the first . 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 . 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.)
The alternative spelling permut ahedron 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, uses that term for any polytope whose vertices have a bijection with the permutations of some set.
| , , facets, Face dimension . |
''''''
1 ''''''
1 '''14'''
1 '''30''' 150
|
The permutohedron of order has vertices, each of which is adjacent to others. The number of edges is , and their length is .
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 and 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 , because they correspond to non-empty proper of . The vertices of a facet corresponding to subset have in common, that their coordinates on places in are smaller than the rest., p. 105 (see chapter The Permutahedron).
For order 3 the facets are the 6 edges, and for order 4 they are the 14 faces. The coordinates on places where 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 . In its four vertices the coordinates on the last two places have the smallest values (namely 1 and 2). | ||||
More generally, the k-face of dimensions 0 (vertices) to (the permutohedron itself) correspond to the strict weak orderings of the set . So the number of all faces is the -th ordered Bell number.See, e.g., , p. 18. A face of dimension corresponds to an ordering with equivalence classes.
| The images above show the 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 , which represents . 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 interpreted as permutations are those forming the Cayley graph. { class="wikitable collapsible collapsed" !colspan="2" style="color: gray;" | 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 assigned to the facet, so the ordering is .
The images below show how the facets of the -permutohedron correspond to the simplex projection of the -hypercube. | |
|}
The number of faces of dimension in the permutohedron of order is given by the triangle :
|
|
.png/){kind=link}