Cayley graph explained
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. 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 makes them particularly good candidates for constructing expander graphs.
Definition
Let
be a
group and
be a
generating set of
. The Cayley graph
is an
edge-colored directed graph constructed as follows:
[2]
of
is assigned a vertex: the vertex set of
is identified with
of
is assigned a color
.
and
, there is a directed edge of color
from the vertex corresponding to
to the one corresponding to
.
Not every convention requires that
generate the group. If
is not a generating set for
, then
is
disconnected and each connected component represents a coset of the subgroup generated by
.
If an element
of
is its own inverse,
then it is typically represented by an undirected edge.
The set
is often assumed to be finite, especially in
geometric group theory, which corresponds to
being locally finite and
being finitely generated.
The set
is sometimes assumed to be
symmetric (
) and not containing the group
identity element. In this case, the uncolored Cayley graph can be represented as a simple undirected
graph.
Examples
is the infinite cyclic group and the set
consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path.
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.
with the set of generators consisting of four elements
is the infinite
grid on the plane
, while for the direct product
with similar generators the Cayley graph is the
finite grid on a
torus.
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 A different Cayley graph of
is shown on the right.
is still the horizontal reflection and is represented by blue lines, and
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
and
corresponding to the set
is depicted at the top of the article, with
being the identity. 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: 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
generators. A
presentation of a group
by
generators corresponds to a surjective
homomorphism from the free group on
generators to the group
defining a map from the Cayley tree to the Cayley graph of
. 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.
- A Cayley graph of the discrete Heisenberg group is depicted to the right. The generators used in the picture are the three matrices
given by the three permutations of 1, 0, 0 for the entries
. They satisfy the relations
, 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.
[4] Characterization
The group
acts on itself by left multiplication (see
Cayley's theorem). 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 of the Cayley graph and their color is preserved by this action: the edge
is mapped to the edge
, both having color
. In fact, all
automorphisms of the colored directed graph
are of this form, so that
is isomorphic to the
symmetry group of
.
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
and the generating set
from the unlabeled directed 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 maps
to
The set
of generators of
that yields
as the Cayley graph
is the set of labels of out-neighbors of
. Since
is uncolored, it might have more directed graph automorphisms than the left multiplication maps, for example group automorphisms of
which permute
.
Elementary properties
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 (or closed walks) in the Cayley graph indicate relations among 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
.
[1]
is a
surjective group homomorphism and the images of the elements of the generating set
for
are distinct, then it induces a covering of graphs
where
In particular, if a group
has
generators, all of order different from 2, and the set
consists of these generators together with their inverses, then the Cayley graph
is covered by the infinite regular
tree of degree
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.[5]
- If
is the left-regular representation with
matrix form denoted
, the adjacency matrix of
is
.
of the group
induces an
eigenvector of the
adjacency matrix of
. The associated
eigenvalue is
which, when
is Abelian, takes the form
for integers
In particular, the associated eigenvalue of the trivial character (the one sending every element to 1) is the degree of
, that is, the order of
. If
is an Abelian group, there are exactly
characters, determining all eigenvalues. The corresponding orthonormal basis of eigenvectors is given by
vj=\tfrac{1}{\sqrt{|G|}}\begin{pmatrix}1&e2\pi&e2 ⋅ &e3 ⋅ & … &e(|G|-1)2\pi\end{pmatrix}.
It is interesting to note that this eigenbasis is independent of the generating set
. More generally for symmetric generating sets, take
a complete set of irreducible representations of
and let
with eigenvalue set
. Then the set of eigenvalues of
is exactly
where eigenvalue
appears with multiplicity
for each occurrence of
as an eigenvalue of
Schreier coset graph
See main article: article and Schreier coset graph.
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. Conversely, for symmetric generating sets, the spectral and representation theory of
are directly tied together: take
a complete set of irreducible representations of
and let
with eigenvalues
. Then the set of eigenvalues of
is exactly
where eigenvalue
appears with multiplicity
for each occurrence of
as an eigenvalue of
The genus of a group is the minimum genus for any Cayley graph of that group.[6]
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.
Expansion properties
When
, the Cayley graph
is
-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
with top eigenvalue equal to
, 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). The following statement holds:[7]
For example the group
has property (T) and is generated by
elementary matrices and this gives relatively explicit examples of expander graphs.
Integral classification
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
is integral iff the eigenvalues of
are integral for every representation
of
.
Cayley integral simple group
A group
is Cayley integral simple (CIS) if the connected Cayley graph
is integral exactly when the symmetric generating set
is the complement of a subgroup of
. A result of Ahmady, Bell, and Mohar shows that all CIS groups are isomorphic to
, or
for primes
.
[8] It is important that
actually generates the entire group
in order for the Cayley graph to be connected. (If
does not generate
, the Cayley graph may still be integral, but the complement of
is not necessarily a subgroup.)
In the example of
, the symmetric generating sets (up to graph isomorphism) are
is a
-cycle with eigenvalues
2,\tfrac{\sqrt{5}-1}{2},\tfrac{\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2},\tfrac{-\sqrt{5}-1}{2}
is
with eigenvalues
The only subgroups of
are the whole group and the trivial group, and the only symmetric generating set
that produces an integral graph is the complement of the trivial group. Therefore
must be a CIS group.
The proof of the complete CIS classification uses the fact that every subgroup and homomorphic image of a CIS group is also a CIS group.
Cayley integral group
A slightly different notion is that of a Cayley integral group
, in which every symmetric subset
produces an integral graph
. Note that
no longer has to generate the entire group.
The complete list of Cayley integral groups is given by
, and the dicyclic group of order
, where
and
is the quaternion group.
[8] The proof relies on two important properties of Cayley integral groups:
- Subgroups and homomorphic images of Cayley integral groups are also Cayley integral groups.
- A group is Cayley integral iff every connected Cayley graph of the group is also integral.
Normal and Eulerian generating sets
Given a general group
, a subset
is normal if
is closed under
conjugation by elements of
(generalizing the notion of a normal subgroup), and
is Eulerian if for every
, the set of elements generating the cyclic group
is also contained in
.A 2019 result by Guo, Lytkina, Mazurov, and Revin proves that the Cayley graph
is integral for any Eulerian normal subset
, using purely representation theoretic techniques.
[9] The proof of this result is relatively short: given
an Eulerian normal subset, select
pairwise nonconjugate so that
is the union of the
conjugacy classes
. Then using the characterization of the spectrum of a Cayley graph, one can show the eigenvalues of
are given by
taken over irreducible characters
of
. Each eigenvalue
in this set must be an element of
for
a primitive
root of unity (where
must be divisible by the orders of each
). Because the eigenvalues are algebraic integers, to show they are integral it suffices to show that they are rational, and it suffices to show
is fixed under any automorphism
of
. There must be some
relatively prime to
such that
for all
, and because
is both Eulerian and normal,
\sigma(\chi(xi))=\chi(xj)
for some
. Sending
bijects conjugacy classes, so
and
have the same size and
merely permutes terms in the sum for
. Therefore
is fixed for all automorphisms of
, so
is rational and thus integral.
Consequently, if
is the alternating group and
is a set of permutations given by
, then the Cayley graph
is integral. (This solved a previously open problem from the Kourovka Notebook.) In addition when
is the symmetric group and
is either the set of all transpositions or the set of transpositions involving a particular element, the Cayley graph
is also integral.
History
Cayley graphs were first considered for finite groups by Arthur Cayley in 1878.[2] 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.[10]
See also
External links
Notes and References
- Book: Wilhelm Magnus . Wilhelm . Magnus . Abraham . Karrass . Baumslag–Solitar group . Donald . Solitar . Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations . 2004 . 1966 . Courier . 978-0-486-43830-6 .
- Arthur . Cayley. American Journal of Mathematics . 1878. 1. 2. 174–6. Desiderata and suggestions: No. 2. The Theory of groups: graphical representation . 2369306. 10.2307/2369306. In his Collected Mathematical Papers 10: 403–405.
- Theron . Daniel Peter . 2636729 . 46 . University of Wisconsin, Madison . Ph.D. thesis . An extension of the concept of graphically regular representations . 1988. .
- Bartholdi . Laurent . Ceccherini-Silberstein . Tullio . Salvatori . Maura . Sava-Huss . Ecaterina . 1512.07044 . Growth of groups and wreath products . 978-1-316-60440-3 . 3644003 . 1–76 . Cambridge Univ. Press, Cambridge . London Math. Soc. Lecture Note Ser. . Groups, graphs and random walks: Selected papers from the workshop held in Cortona, June 2–6, 2014 . 436 . 2017.
- See Theorem 3.7 of Book: Babai, László. 27. Automorphism groups, isomorphism, reconstruction. Handbook of Combinatorics. 1447–1540. Ronald L.. Graham. Ronald Graham. Martin. Grötschel. Martin Grötschel . László. Lovász. László Lovász. László Babai. Elsevier. 1 . 9780444823465 . 1995. http://people.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf.
- White . Arthur T. . On the genus of a group . . 173 . 1972 . 203–214 . 0317980 . 10.1090/S0002-9947-1972-0317980-2. free .
- Proposition 1.12 in Lubotzky. Alexander . Alexander Lubotzky . Expander graphs in pure and applied mathematics . . 2012 . 49 . 113–162 . 1105.2389. 10.1090/S0273-0979-2011-01359-3 . free.
- Ahmady. Azhvan . Bell. Jason. Mohar. Bojan. Bojan Mohar. Integral Cayley graphs and groups. SIAM Journal on Discrete Mathematics. 28. 2. 685–701. 2014. 1307.6155 . 10.1137/130925487 . 207067134.
- Guo. W.. Lytkina. D.V.. Mazurov. V.D.. Revin. D.O.. Integral Cayley graphs. Algebra and Logic . 2019. 58 . 4 . 297–305 . 10.1007/s10469-019-09550-2. 1808.01391 . 209936465 .
- Book: Dehn, Max . Max Dehn. Papers on Group Theory and Topology . Springer-Verlag . 2012 . 1987 . 978-1461291077 . Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.