Please Login to access more options.

Problem 22 (Creating Cayley Graphs Of Simple Shift Permutations)

Let's make some Cayley graphs as they relate with the game of Scoring on simple shift permutations. To get Sage to make the graphs, you'll first have to write the simple shift permutation in disjoint cycle notation. As an example, if there are 6 letters in our alphabet $X=\{1,2,3,4,5,6\}$, then we could write the simple shift $\phi_2$ as $(2,4,6)(1,3,5)$. If player 1 chooses $\sigma_1=\phi_2$ and player 2 chooses $\sigma_2=\phi_3$, then the following Sage code visually provides a graph of $\text{span}(\{\sigma_1\})$ and then $\text{span}(\{\sigma_1,\sigma_2\})$. 

g1 =  PermutationGroup(["(2,4,6)(1,3,5)"])    
d1=g1.cayley_graph()                                                 
d1.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)   
print(g1.list())                                                     

g2 = PermutationGroup(["(2,4,6)(1,3,5)","(1,4)(2,5)(3,6)"]) 
d2=g2.cayley_graph()
d2.show(color_by_label=True, vertex_size=0.03, vertex_labels=True)
print(g2.list())

By hand, my first graph would contain two unconnected triangles. My second graph would look similar to the graph above.

  1. Suppose the alphabet is $X=\{1,2,3,4,5,6\}$. Player 1 chooses $\phi_1$. Draw the associated graph.
  2. Suppose the alphabet is $X=\{1,2,\ldots,10\}$. Player 1 chooses $\phi_5$. Player 2 chooses $\phi_4$. Draw the two associated graphs.
  3. Suppose the alphabet is $X=\{1,2,\ldots,12\}$. Player 1 chooses $\phi_5$. Draw the associated graph.
  4. Suppose the alphabet is $X=\{1,2,\ldots,12\}$. Player 1 chooses $\phi_6$. Player 2 chooses $\phi_2$. Player 1 then chooses $\phi_3$. Draw the three associated graphs. The first graph should consist of 6 arrows between pairs of vertices (Sage will only show you the segment connnecting $()$ and $\phi_6$). Your second graph should have 2 hexagons with arrows crossing in the middle. The last graph should connect the edges of the hexagons.

Here's a blank Sage cell that you can use to perform some computations. You'll probably want to copy code from above and make some changes.

The following pages link to this page.