0xDE (11011110) wrote,

A different kind of permutation polyhedron

The permutohedron (convex hull of permutations of (1,2,3,4), in the 3d subspace x+y+z+w=10 of R4) provides a convenient geometric representation of the permutations on four items, as the 24 vertices of a truncated octahedron. But the same 24-vertex graph that forms the skeleton of the permutohedron is also a Cayley graph of the symmetric group of permutations on four items, if one labels the vertices differently (by the inverses of their permutohedron labels) and uses as group generators the transpositions of adjacent items.

A different 24-vertex polyhedron, the truncated cube, also has a standard representation as a Cayley graph, of a different group: it is an example of the cube-connected cycles network, a Cayley graph of the group that acts on binary strings by cyclic shifts and bit-flipping.

But the truncated cube is itself in a different way the Cayley graph of the symmetric group. The generators are transpositions of the first two permutation elements and rotations of the last three elements. Behold:

truncated cube as Cayley graph of symmetric group


I guess this means the CCC action on three-bit strings can be encoded by permutations on four items somehow? The first element in the permutation and the parity of the permutation together encode which bits have been flipped, and the rotation of the remaining permutation items encodes the rotation of the bitstring, but I'm not seeing a way of describing this correspondence clearly.

ETA: Although both truncated cubes are Cayley graphs of groups generated by order-2 and order-3 elements, they are not isomorphically labeled as Cayley graphs. In the permutation Cayley graph, the triangles are all oriented the same way as each other, while in the CCC Cayley graph, the triangles alternate orientations. That is, the permutation group has the presentation <x, y | x2, y3, (xy)4>, while the CCC group has the presentation <x, y | x2, y3, (xyxy-1)2>. Perhaps this difference explains the difficulty in relating the CCC action to permutations.
Tags: permutohedron
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments