Free account · your comment posts right after signup
Also known as Cayley graph, Cayley diagram
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs make them particularly good candidates for constructing expander graphs.
Article
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color 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 set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs make them particularly good candidates for constructing expander graphs.
Contents
Definition
Let
G
{\displaystyle G}
be a group and
S
{\displaystyle S}
be a generating set of
G
{\displaystyle G}
. The Cayley graph
Γ
=
Γ
(
G
,
S
)
{\displaystyle \Gamma =\Gamma (G,S)}
is an edge-colored directed graph constructed as follows:
Each element
g
{\displaystyle g}
of
G
{\displaystyle G}
is assigned a vertex: the vertex set of
Γ
{\displaystyle \Gamma }
is identified with
G
Examples
Suppose that
G
=
Z
{\displaystyle G=\mathbb {Z} }
is the infinite cyclic group and the set
S
{\displaystyle S}
consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.
Similarly, if
G
=
Z
n
{\displaystyle G=\mathbb {Z} _{n}}
is the finite cyclic group of order
n
{\displaystyle n}
and the set
S
{\displaystyle S}
consists of two elements, the standard generator of
G
{\displaystyle G}
and its inverse, then the Cayley graph is the cycle
C
n
{\displaystyle C_{n}}
Characterization
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 h\in G}
maps a vertex
g
∈
V
(
Γ
)
{\displaystyle g\in V(\Gamma )}
to the vertex
h
g
∈
V
(
Γ
)
.
{\displaystyle hg\in V(\Gamma ).}
The set of edges of the Cayley graph and their color is preserved by this action: the edge
Elementary properties
The Cayley graph
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
depends in an essential way on the choice of the set
S
{\displaystyle S}
of generators. For example, if the generating set
S
{\displaystyle S}
has
k
{\displaystyle k}
elements then each vertex of the Cayley graph has
k
{\displaystyle k}
incoming and
k
{\displaystyle k}
outgoing directed edges. In the case of a symmetric generating set
S
{\displaystyle S}
with
r
{\displaystyle r}
Schreier coset graph
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.
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. Conversely, for symmetric generating sets, the spectral and representation theory of
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
are directly tied together: take
ρ
1
,
…
,
ρ
k
{\displaystyle \rho _{1},\dots ,\rho _{k}}
a complete set of irreducible representations of
G
,
{\displaystyle G,}
and let
ρ
i
(
S
)
=
∑
s
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.
Signal Processing
In addition to their role in pure mathematics, Cayley graphs have applications in signal processing and harmonic analysis. The adjacency matrix of a Cayley graph constructed over a finite group encodes the algebraic structure of the group, and its eigenvalues correspond to the spectral coefficients in the basis defined by the group's irreducible representations. For the cyclic group, this recovers the discrete Fourier transform; for the dihedral group, the discrete cosine transform.
Expansion properties
When
S
=
S
−
1
{\displaystyle S=S^{-1}}
, the Cayley graph
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
is
|
S
|
{\displaystyle |S|}
-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
An integral graph is one whose eigenvalues are all integers. While the complete classification of integral graphs remains an open problem, the Cayley graphs of certain groups are always integral.
Using previous characterizations of the spectrum of Cayley graphs, note that
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
is integral iff the eigenvalues of
ρ
(
S
)
{\displaystyle \rho (S)}
are integral for every representation
ρ
{\displaystyle \rho }
of
G
{\displaystyle G}
.
Cayley integral simple group
A group
G
{\displaystyle G}
is Cayley integral simple (CIS) if the connected Cayley graph
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
is integral exactly when the symmetric generating set
S
{\displaystyle S}
is the complement of a subgroup of
G
{\displaystyle G}
. A result of Ahmady, Bell, and Mohar shows that all CIS groups are isomorphic to
A slightly different notion is that of a Cayley integral group
G
{\displaystyle G}
, in which every symmetric subset
S
{\displaystyle S}
produces an integral graph
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
. Note that
S
{\displaystyle S}
no longer has to generate the entire group.
The complete list of Cayley integral groups is given by
Z
2
n
×
Z
3
m
,
Z
2
n
×
Normal and Eulerian generating sets
Given a general group
G
{\displaystyle G}
, a subset
S
⊆
G
{\displaystyle S\subseteq G}
is normal if
S
{\displaystyle S}
is closed under conjugation by elements of
G
{\displaystyle G}
(generalizing the notion of a normal subgroup), and
S
{\displaystyle S}
is Eulerian if for every
s
∈
S
{\displaystyle s\in S}
, the set of elements generating the cyclic group
⟨
s
⟩
{\displaystyle \langle s\rangle }
is also contained in
S
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.
Article from Wikipedia (CC BY-SA 4.0), where it is maintained by volunteer editors.
.
{\displaystyle G.}
Each element
s
{\displaystyle s}
of
S
{\displaystyle S}
is assigned a color
c
s
{\displaystyle c_{s}}
.
For every
g
∈
G
{\displaystyle g\in G}
and
s
∈
S
{\displaystyle s\in S}
, there is a directed edge of color
c
s
{\displaystyle c_{s}}
from the vertex corresponding to
g
{\displaystyle g}
to the one corresponding to
g
s
{\displaystyle gs}
.
Not every convention requires that
S
{\displaystyle S}
generate the group. If
S
{\displaystyle S}
is not a generating set for
G
{\displaystyle G}
, then
Γ
{\displaystyle \Gamma }
is disconnected and each connected component represents a coset of the subgroup generated by
S
{\displaystyle S}
.
If an element
s
{\displaystyle s}
of
S
{\displaystyle S}
is its own inverse,
s
=
s
−
1
,
{\displaystyle s=s^{-1},}
then it is typically represented by an undirected edge.
The set
S
{\displaystyle S}
is often assumed to be finite, especially in geometric group theory, which corresponds to
Γ
{\displaystyle \Gamma }
being locally finite and
G
{\displaystyle G}
being finitely generated.
The set
S
{\displaystyle S}
is sometimes assumed to be symmetric (
S
=
S
−
1
{\displaystyle S=S^{-1}}
) and not containing the group identity element. In this case, the uncolored Cayley graph can be represented as a simple undirected graph.
. More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs.
The Cayley graph of the direct product of groups (with the cartesian product of generating sets as a generating set) is the cartesian product of the corresponding Cayley graphs. Thus the Cayley graph of the abelian group
Z
2
{\displaystyle \mathbb {Z} ^{2}}
with the set of generators consisting of four elements
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
The Cayley graph of the free group on two generators
a
{\displaystyle a}
and
b
{\displaystyle b}
corresponding to the set
S
=
{
a
,
b
,
a
−
1
,
b
−
1
}
{\displaystyle S=\{a,b,a^{-1},b^{-1}\}}
is depicted at the top of the article, with
e
{\displaystyle e}
being the identity. Travelling along an edge to the right represents right multiplication by
a
,
{\displaystyle a,}
while travelling along an edge upward corresponds to the multiplication by
b
.
{\displaystyle b.}
Since the free group has no relations, the Cayley graph has no cycles: it is the 4-regular infinite tree. It is a key ingredient in the proof of the Banach–Tarski paradox.
More generally, the Bethe lattice or Cayley tree is the Cayley graph of the free group on
n
{\displaystyle n}
generators. A presentation of a group
G
{\displaystyle G}
by
n
{\displaystyle n}
generators corresponds to a surjective homomorphism from the free group on
n
{\displaystyle n}
generators to the group
G
,
{\displaystyle G,}
defining a map from the Cayley tree to the Cayley graph of
G
{\displaystyle G}
. Interpreting graphs topologically as one-dimensional simplicial complexes, the simply connected infinite tree is the universal cover of the Cayley graph; and the kernel of the mapping is the fundamental group of the Cayley graph.
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 embedded in a three-dimensional space, the Cayley graph has four-dimensional volume growth.
(
g
,
g
s
)
{\displaystyle (g,gs)}
is mapped to the edge
(
h
g
,
h
g
s
)
{\displaystyle (hg,hgs)}
, both having color
c
s
{\displaystyle c_{s}}
. In fact, all automorphisms of the colored directed graph
Γ
{\displaystyle \Gamma }
are of this form, so that
G
{\displaystyle G}
is isomorphic to the symmetry group of
Γ
{\displaystyle \Gamma }
.
The left multiplication action of a group on itself is simply transitive, in particular, Cayley graphs are vertex-transitive. The following is a kind of converse to this:
To recover the group
G
{\displaystyle G}
and the generating set
S
{\displaystyle S}
from the unlabeled directed graph
Γ
{\displaystyle \Gamma }
, 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 maps
v
1
{\displaystyle v_{1}}
to
v
.
{\displaystyle v.}
The set
S
{\displaystyle S}
of generators of
G
{\displaystyle G}
that yields
Γ
{\displaystyle \Gamma }
as the Cayley graph
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
is the set of labels of out-neighbors of
v
1
{\displaystyle v_{1}}
. Since
Γ
{\displaystyle \Gamma }
is uncolored, it might have more directed graph automorphisms than the left multiplication maps, for example group automorphisms of
G
{\displaystyle G}
which permute
S
{\displaystyle S}
.
elements, the Cayley graph is a regular directed graph of degree
r
.
{\displaystyle r.}
Cycles (or closed walks) in the Cayley graph indicate relations among the elements of
S
.
{\displaystyle S.}
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
P
{\displaystyle {\mathcal {P}}}
is equivalent to solving the Word Problem for
P
{\displaystyle {\mathcal {P}}}
.
If
f
:
G
′
→
G
{\displaystyle f:G'\to G}
is a surjective group homomorphism and the images of the elements of the generating set
S
′
{\displaystyle S'}
for
G
′
{\displaystyle G'}
are distinct, then it induces a covering of graphs
generators, all of order different from 2, and the set
S
{\displaystyle S}
consists of these generators together with their inverses, then the Cayley graph
Γ
(
G
,
S
)
{\displaystyle \Gamma (G,S)}
is covered by the infinite regular tree of degree
2
k
{\displaystyle 2k}
corresponding to the free group on the same set of generators.
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 (removal of any element and, if present, its inverse from the generating set leaves a set which is not generating), the vertex connectivity is equal to the degree. The edge connectivity is in all cases equal to the degree.
