Please Login to access more options.
Problem 29 (Cayley Graph Patterns)
In each scenario below, you should draw a Cayley graph.
- Let $X=\mathbb{Z}$, an infinite set. Consider the permutation $\phi_1:\mathbb{Z}\to \mathbb{Z}$ defined by $\phi_1(x)=x+1$. This permutation shifts elements in $\mathbb{Z}$ right one, with no wrap around. If we let $S=\{\phi_1\}$, give a rough sketch of the Cayley graph of $\text{span}(S)$. It's a rough sketch of the graph because there are infinitely many vertices.
- How would you change your graph in part 1 if instead you used $S=\{\phi_2,\phi_3\}$, where these are shifts right 2 and 3 respectively?
- Suppose that $X$ is a set, and that $S$ contains a single automorphism $s$ of $X$. Suppose also that we know $s^6$ is the identity (so following the arrow colored $c_s$ 6 times will return us to where we started). Construct a Cayley graph of $\text{span}(S)$. Is there more than one right answer to this?
- Suppose that we know $S$ contains two elements $a$ and $b$. We also know that $a^2$ and $b^4$ are both the identity. In addition, we know that $a\circ b=b\circ a$, so if we start somewhere and follow the arrows colored $c_a$ and then $c_b$, then we should end up at the same place if we followed the arrows colored $c_b$ and then $c_a$. Construct a graph that satisfies these relationships. We'll often write this as $$\left<a,b\mid a^2=id, b^4=id, a\circ b=b\circ a\right>.$$
The following pages link to this page.