0
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The "slight indirectness" is important: the action of $G$ on itself by right multiplication is boring when drawn as a graph in this way: if you take $S = G$, the Cayley graph is the complete graph on the elements of $G$ with the arrow from $g$ to $h$ labelled by $g^{-1}h$. The point of the Cayley graph is to give information about how $S$ generates $G$. $\endgroup$ – Rob Arthan Oct 16 '16 at 0:12
1
$\begingroup$

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$).

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.