Concept
In mathematics, the permutohedron 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. 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 (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.) According to , permutohedra were first studied by . The name permutoèdre was coined by . 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, uses that term for any polytope whose vertices have a bijection with the permutations of some set. 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 . 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 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 .
