Each element of is assigned a vertex: the vertex set of is identified with
Each generator of is assigned a color.
For any and the vertices corresponding to the elements and are joined by a directed edge of colour Thus the edge set consists of pairs of the form with providing the color.
In geometricgroup theory, the set is usually assumed to be finite, symmetric 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.
Examples
Suppose that is the infinite cyclic group and the set consists of the standard generator 1 and its inverse then the Cayley graph is an infinite path.
Similarly, if is the finite cyclic group of order and the set consists of two elements, the standard generator of and its inverse, then the Cayley graph is the cycle. More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs.
A Cayley graph of the dihedral group on two generators and is depicted to the left. Red arrows represent composition with. Since is self-inverse, the blue lines, which represent composition with, are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The Cayley table of the group can be derived from the group presentation
The Cayley graph of the free group on two generators and corresponding to the set is depicted at the top of the article, and represents the identity element. Travelling along an edge to the right represents right multiplication by while travelling along an edge upward corresponds to the multiplication by Since the free group has no relations, the Cayley graph has no cycles. This Cayley graph is a 4-regular infinite tree and is a key ingredient in the proof of the Banach–Tarski paradox.
The group acts on itself by left multiplication. This may be viewed as the action of on its Cayley graph. Explicitly, an element maps a vertex to the vertex The set of edges within the Cayley graph is preserved by this action: the edge is transformed into the edge. 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 and the generating set from the Cayley graph select a vertex and label it by the identity element of the group. Then label each vertex of by the unique element of that transforms into The set of generators of that yields as the Cayley graph is the set of labels of the vertices adjacent to the selected vertex. The generating set is finite if and only if the graph is locally finite.
Elementary properties
If a member of the generating set is its own inverse, then it is typically represented by an undirected edge.
The Cayley graph depends in an essential way on the choice of the set of generators. For example, if the generating set has elements then each vertex of the Cayley graph has incoming and outgoing directed edges. In the case of a symmetric generating set with elements, the Cayley graph is a regular directed graph of degree
Cycles in the Cayley graph indicate relations between the elements of In the more elaborate construction of the Cayley complex of a group, closed paths corresponding to relations are "filled in" by polygons. This means that the problem of constructing the Cayley graph of a given presentation is equivalent to solving the Word Problem for.
If is a surjectivegroup homomorphism and the images of the elements of the generating set for are distinct, then it induces a covering of graphs
A graph can be constructed even if the set does not generate the group However, it is disconnected and is not considered to be a Cayley graph. In this case, each connected component of the graph represents a coset of the subgroup generated by
For any finite Cayley graph, considered as undirected, the vertex connectivity is at least equal to 2/3 of the degree of the graph. If the generating set is minimal, the vertex connectivity is equal to the degree. The edge connectivity is in all cases equal to the degree.
If one, instead, takes the vertices to be right cosets of a fixed subgroup one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd–Coxeter process.
Connection to group theory
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. The genus of a group is the minimum genus for any Cayley graph of that group.
Geometric group theory
For infinite groups, the coarse geometry of the Cayley graph is fundamental to geometric group theory. For a finitely generated group, this is independent of choice of finite set of generators, hence an intrinsic property of the group. This is only interesting for infinite groups: every finite group is coarsely equivalent to a point, since one can choose as finite set of generators the entire group. Formally, for a given choice of generators, one has the word metric, which determines a metric space. The coarse equivalence class of this space is an invariant of the group.
History
Cayley graphs were first considered for finite groups by Arthur Cayley in 1878. Max Dehn in his unpublished lectures on group theory from 1909–10 reintroduced Cayley graphs under the name Gruppenbild, which led to the geometric group theory of today. His most important application was the solution of the word problem for the fundamental group of surfaces with genus ≥ 2, which is equivalent to the topological problem of deciding which closed curves on the surface contract to a point.
Bethe lattice
The Bethe lattice or infinite Cayley tree is the Cayley graph of the free group on generators. A presentation of a group by generators corresponds to a surjective map from the free group on generators to the group and at the level of Cayley graphs to a map from the infinite Cayley tree to the Cayley graph. This can also be interpreted as the universal cover of the Cayley graph, which is not in general simply connected.
