Please Login to access more options.

Problem 41 (Translating By An Arrow In A Cayley Graph Is An Automorphism)

Let $X$ be a set and let $S$ be a set of permutations of $X$. Let $H=\text{span}(S)$ and let $\mathcal{G}$ be the Cayley graph $(H,S)$, so we know $(x,y)$ is an arrow colored $c_t$ where $t\in S$ if and only if $y=t \circ x$. Pick an element $s\in S$ (one of the elements used to create arrows). Prove that the function $f_s:H\to H$ defined by $f_s(\sigma)=\sigma\circ s$ is an automorphism of the Cayley graph. You must show the following three things:

  1. The function $f_s$ is a permutation. (State the inverse and show it is the inverse.)
  2. If $(x,y)$ is an arrow colored $c_t$, then $(f_s(x),f_s(y))$ is an arrow colored $c_t$. In other words, if $t\circ x=y$, then explain why $t\circ f_s(x) = f_s(y)$.
  3. If $(f_s(x),f_s(y))$ is an arrow colored $c_t$, then $(x,y)$ is an arrow colored $c_t$.

The following pages link to this page.