Cayley graph

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group,[1] is a graph that encodes the abstract structure of a group.

It is a central tool in combinatorial and geometric group theory.

is an edge-colored directed graph constructed as follows:[2] Not every convention requires that

is disconnected and each connected component represents a coset of the subgroup generated by

is often assumed to be finite, especially in geometric group theory, which corresponds to

acts on itself by left multiplication (see Cayley's theorem).

In fact, all automorphisms of the colored directed graph

The following is a kind of converse to this: Sabidussi's Theorem — An (unlabeled and uncolored) directed graph

by graph automorphisms (i.e., preserving the set of directed edges).

If one instead takes the vertices to be right cosets of a fixed subgroup

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.

Conversely, for symmetric generating sets, the spectral and representation theory of

For a finitely generated group, this is independent of choice of finite set of generators, hence an intrinsic property of the group.

The coarse equivalence class of this space is an invariant of the group.

-regular, so spectral techniques may be used to analyze the expansion properties of the graph.

In particular for abelian groups, the eigenvalues of the Cayley graph are more easily computable and given by

, so we may use Cheeger's inequality to bound the edge expansion ratio using the spectral gap.

Representation theory can be used to construct such expanding Cayley graphs, in the form of Kazhdan property (T).

has property (T) and is generated by elementary matrices and this gives relatively explicit examples of expander graphs.

Using previous characterizations of the spectrum of Cayley graphs, note that

A result of Ahmady, Bell, and Mohar shows that all CIS groups are isomorphic to

, the symmetric generating sets (up to graph isomorphism) are The only subgroups of

that produces an integral graph is the complement of the trivial group.

[9] A slightly different notion is that of a Cayley integral group

The complete list of Cayley integral groups is given by

, the set of elements generating the cyclic group

A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph

Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of

(This solved a previously open problem from the Kourovka Notebook.)

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.