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.
Definition.
Suppose that formula_1 is a group and formula_2 is a generating set of formula_1. The Cayley graph formula_4 is a colored directed graph constructed as follows:
In geometric group theory, the set formula_2 is usually assumed to be finite, symmetric (i.e. formula_22) 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).
Characterization.
The group formula_1 acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of formula_1 on its Cayley graph. Explicitly, an element formula_59 maps a vertex formula_60 to the vertex formula_61 The set of edges within the Cayley graph is preserved by this action: the edge formula_62 is transformed into the edge formula_63. 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 formula_1 and the generating set formula_2 from the Cayley graph formula_69 select a vertex formula_70 and label it by the identity element of the group. Then label each vertex formula_71 of formula_8 by the unique element of formula_1 that transforms formula_74 into formula_75 The set formula_2 of generators of formula_1 that yields formula_8 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).
Schreier coset graph.
If one, instead, takes the vertices to be right cosets of a fixed subgroup formula_116 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 (or the trivial group), since one can choose as finite set of generators the entire group.
Formally, for a given choice of generators, one has the word metric (the natural distance on the Cayley graph), 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 (group diagram), 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 formula_26 generators. A presentation of a group formula_1 by formula_26 generators corresponds to a surjective map from the free group on formula_26 generators to the group formula_121 and at the level of Cayley graphs to a map from the infinite Cayley tree to the Cayley graph. This can also be interpreted (in algebraic topology) as the universal cover of the Cayley graph, which is not in general simply connected.