page_title: Permutohedron
section_title: Other properties
hierarchical_section_title: Permutohedron / Other properties
caption_attribution_description: Cayley graph of S4 generated by the transpositions that swap neighbouring elements (a truncated octahedron like the permutohedron) This &#32;image&#32;was created with POV-Ray. trunc_octa_cayley.pov
context_page_description: In mathematics, the permutohedron of order n is an-dimensional polytope embedded in an n-dimensional space. Its vertex coordinates are the permutations of the first n natural numbers. The edges are the shortest possible connections between these points. Two permutations connected by an edge differ in two places, and the numbers on these places are neighbors.
  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.
context_section_description: The permutohedron is vertex-transitive: the symmetric group Sₙ 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 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 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.
caption: The permutohedron-like Cayley graph of S4 (see here for a comparison with the permutohedron)
exif: {}