Let G be a group which is finitely generated (see generators and relations for groups for all you ever wanted to know about this terminology). Let S be some finite subset of G which generates G: G = <S>. The Cayley graph of G with these generators is the graph Γ=(G,E) whose vertices are the elements of G, with edge set

E = { {u, g*u} : u∈G, g∈S }
That is, connect any 2 vertices of G with an edge iff they differ by one of the generators.

For example, take G=Z2. The set S={(1,0),(0,1)} generates G; its Cayley graph is the square grid which graph theorists usually call just Z2. The set {(1,0),(0,1),(1,1),(1,-1)} also generates G; its Cayley graph has additionally "diagonal" edges inside each square of the grid.

If G=F2 is the free group with 2 generators a,b, we can take S={a,b} which (suprise!) generates G. The Cayley graph is the 4-regular tree. Each element u∈G connects to a*u, b*u, a-1*u, b-1*u, and there can be no loops (multiplying the generators responsible for a loop in the Cayley graph yields 1∈G, and there are no non-trivial relations in the free group).

The Cayley graph describes a geometric structure on the group. It is, of course, dependent on the set of generators chosen. But any 2 Cayley graphs on the same group are quasi-isometric, so the "large-scale" geometry is not very different.

Finally, Cayley graphs provide an intuitive description of the group: the path from 1 to a given element exactly describes how to "construct" it by multiplying generators. The graph is highly regular: any neighbourhood N of a vertex u∈G must look exactly like a neighbourhood of 1∈G: after all, multiplication on the right by an element of G --- u-1 --- preserves edges, so N*u-1 is a neighbourhood of 1 which looks exactly like N.

Log in or register to write something here or to contact authors.