Left and right multiplication for Cayley graphs

950 Views Asked by At

Correct me if I am wrong but I have written down the following:

Let $X$ be a finite group, with subset $S$ and corresponding Cayley graph $G$.

The edge set for a Cayley graph is defined such that two vertices $g, h \in G$ are joined by a directed edge from $g$ to $h$ if $gh^{-1} \in S$. Then $gh^{-1}h = g$. So a directed edge only occurs if $g = sh $ in $X$.

From this, I see that left multiplication of an element in $S$ sends a directed edge into that element, would I be correct in saying that right multiplication of an element in $S$ sends the directed edge away from the element, i.e: $(g,h)$ is an edge if from $g$ to $gs = h$.

If so this would be easier to imagine as multiplication by elements in the generating set send the corresponding vertices to the product of that element with a generator.

Is there any way to prove this? I know it works for the Dihedral group but am not sure if it is true for the general case.

I have used the definition on Wolfram Alpha for a Cayley graph.

Thanks in advance

1

There are 1 best solutions below

4
On

Expanding on Derek's comment (we both read between the lines that by "sending edges" you were getting at possible Cayley graph isomorphisms induced by left or right multiplication).

The left-right asymmetry is a little confusing. If our Cayley graph edges are defined (as in the Wolfram article) by left multiplication, then right multiplication will give graph isomorphisms. However, if our Cayley graph edges are defined (as by Derek) by right multiplication, then left multiplication will give graph isomorphisms. But we cannot have it both ways: for a fixed Cayley graph definition it will not generally be the case that left and right multiplications are graph isomorphisms.

Using the Wolfram definition, from the existence of edge $$ x \stackrel{s}{\rightarrow} y, $$ it follows at once that $sx=y$ and thus $s(xg)=yg$, so there exists edge $$ xg \stackrel{s}{\rightarrow} yg. $$ Thus each $g \in X$ "sends edges" to other edges in the true sense of a graph isomorphism. (It gives two maps, one on vertices and one on edges that respects the graph incidence).

Consider the simplest case of dihedral group $D_3$, where $S$ is made up of $60^{\circ}$ rotation $a$ and vertical reflection $b$. Below is the Cayley graph for $(D_3, S)$.

                      Cayley graph of dihedral group $D_3$

Here's a simple counterexample: While edge $e \stackrel{a}{\rightarrow} a$, is sent via right multiplication by $b$ to edge $b \stackrel{a}{\rightarrow} ab$, no edge exists of the form $$ b \stackrel{a}{\rightarrow} ba, $$ since $ab\neq ba$. Thus left multiplication by $b$ does not yield a well-defined graph morphism: it permutes the vertices but not the vertices and edges in concert.