Cayley Graph intuition

Question

I'm having trouble understanding why my intuition of what a Cayley Graph is, is not compatible with the actual definition. Can someone let me know where my logic is flawed?

I was presented with definition:
"The Cayley graph for $G$ with respect to $S$ is a directed graph with edge labels given by the following data: The vertex set is the set of elements of $G$, and there is a directed edge from $g \rightarrow gs$ for every $g \in G$ and $s \in S$. Finally, we label the edge from $g \rightarrow gs$ by the element $s$ of $G$."

But the Cayley graph, from my understanding, is supposed to graph the relations between the elements of the set under the action of the group G(?). So I think that the definition should be that:

The Cayley graph for $G$ with respect to $S$ is a directed graph with edge labels given by the following data: The vertex set is the set of elements of $S$, and there is a directed edge from $s \rightarrow gs$ for every $g \in G$ and $s \in S$. Finally, we label the edge from $s \rightarrow gs$ by the element $g$ of $G$.

Answer 1

You are trying to define a graph with:

• vertex set $S$
• edge set $(s,gs)$ for all $s\in S$ and $g\in G$

But how can $(s,gs)$ be an edge if $gs$ is not a vertex, i.e. not in $S$?

A relation between the elements of $S$ (ignoring inverses for simplicity) would be an equation

$$s_1s_2\cdots s_p=s_1's_2'\cdots\cdots s_q' $$

where $s_1,\cdots,s_p,s_1',\cdots,s_q'$ are all elements of $S$. What this equation represents in the Cayley graph is that we can go from $e$ to the element $x$ appearing on both sides of the equation via two different paths along edges.

If you want a better feel for Cayley graphs, try computing the Cayley graph for the cyclic group of order three and the dihedral group of order ten (using a rotation and flip for $S$).

Answer 2

What is missing from the definition you quote is that $S$ is supposed to be a set of generators for $G$, such that each element of $G$ can be written as a product of elements of $S$ (or their inverses) in at least one way.

The Cayley graph represents the action of $G$ on itself by right multiplication. It does so slightly indirectly in that only the actions of some of the elements of $G$ (namely, the ones in $S$) are shown explicitly -- but since $S$ generates $G$, you can find the action of any element of $G$ by writing it as a product of generators and then following the edges labeled by those generators, in seqence.

And "writing the element as a product of generators" simply corresponds to finding a path through the graph from $e$ to the chosen element, and looking at the labels on the way.

Answer 3

If the group $G$ acted on a set $S$, then you could define the graph you describe. However, that isn't the Cayley graph for a generating set $S$ of a group $G$. The Cayley graph shows how the generating set $S$ acts on $G$ and is defined exactly as in your quotation except that $s \in G$ right at the end should read $s \in S$. The Cayley graph gives information about how $S$ generates $G$.