Posts

Showing posts from September, 2023

Creating Cayley Graphs from Group Presentations

Image
Definitions: A Cayley graph is a directed graph showing how to get from any element of a group to any other using only a finite number of "generator" elements.  For example, in the group \mathbb{Z}_2\times\mathbb{Z}_2 we could use the generators a = (1,0) and b = (0,1) and we'd end up with a graph that looks like a square with arrows going round the edges. A Group presentation defines a group by specifying generators and relations between them.  For example the presentation \langle a,b \vert a^2=1,b^2=1,aba^{-1}b^{-1}=1\rangle specifies a group.  In fact the group it specifies is isomorphic to  \mathbb{Z}_2\times\mathbb{Z}_2 and we can prove this using the facts that a and b commute and both have order 2.  In this case it's easy to see what group we have but in general it's a bit more difficult.  A useful first step would be to be able to draw the Cayley graph automatically. Question: Is it possible to automatically generate a Cayley graph f...