Cayley graph

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley) and uses a specified, usually finite, set of generators for the group. It is a central tool in combinatorial and geometric group theory. In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley) and uses a specified, usually finite, set of generators for the group. It is a central tool in combinatorial and geometric group theory. Suppose that G {displaystyle G} is a group and S {displaystyle S} is a generating set of G {displaystyle G} . The Cayley graph Γ = Γ ( G , S ) {displaystyle Gamma =Gamma (G,S)} is a colored directed graph constructed as follows: In geometric group theory, the set S {displaystyle S} is usually assumed to be finite, symmetric (i.e. S = S − 1 {displaystyle S=S^{-1}} ) and not containing the identity element of the group. In this case, the uncolored Cayley graph is an ordinary graph: its edges are not oriented and it does not contain loops (single-element cycles). A different Cayley graph of D 4 {displaystyle D_{4}} is shown on the right. b {displaystyle b} is still the horizontal reflection and is represented by blue lines, and c {displaystyle c} is a diagonal reflection and is represented by pink lines. As both reflections are self-inverse the Cayley graph on the right is completely undirected. This graph corresponds to the presentation is depicted to the right. The generators used in the picture are the three matrices X , Y , Z {displaystyle X,Y,Z} given by the three permutations of 1, 0, 0 for the entries x , y , z {displaystyle x,y,z} . They satisfy the relations Z = X Y X − 1 Y − 1 ,   X Z = Z X ,   Y Z = Z Y {displaystyle Z=XYX^{-1}Y^{-1}, XZ=ZX, YZ=ZY} , which can also be understood from the picture. This is a non-commutative infinite group, and despite being a three-dimensional space, the Cayley graph has four-dimensional volume growth. The group G {displaystyle G} acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of G {displaystyle G} on its Cayley graph. Explicitly, an element h ∈ G {displaystyle hin G} maps a vertex g ∈ V ( Γ ) {displaystyle gin V(Gamma )} to the vertex h g ∈ V ( Γ ) {displaystyle hgin V(Gamma )} . The set of edges within the Cayley graph is preserved by this action: the edge ( g , g s ) {displaystyle (g,gs)} is transformed into the edge ( h g , h g s ) {displaystyle (hg,hgs)} . The left multiplication action of any group on itself is simply transitive, in particular, the Cayley graph is vertex transitive. This leads to the following characterization of Cayley graphs: To recover the group G {displaystyle G} and the generating set S {displaystyle S} from the Cayley graph Γ = Γ ( G , S ) {displaystyle Gamma =Gamma (G,S)} , select a vertex v 1 ∈ V ( Γ ) {displaystyle v_{1}in V(Gamma )} and label it by the identity element of the group. Then label each vertex v {displaystyle v} of Γ {displaystyle Gamma } by the unique element of G {displaystyle G} that transforms v 1 {displaystyle v_{1}} into v . {displaystyle v.} The set S {displaystyle S} of generators of G {displaystyle G} that yields Γ {displaystyle Gamma } as the Cayley graph is the set of labels of the vertices adjacent to the selected vertex. The generating set is finite (this is a common assumption for Cayley graphs) if and only if the graph is locally finite (i.e. each vertex is adjacent to finitely many edges). If one, instead, takes the vertices to be right cosets of a fixed subgroup H , {displaystyle H,} one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd–Coxeter process. Knowledge about the structure of the group can be obtained by studying the adjacency matrix of the graph and in particular applying the theorems of spectral graph theory.