In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group
is a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
that encodes the abstract structure of a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
. Its definition is suggested by
Cayley's theorem
In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group.
More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose eleme ...
(named after
Arthur Cayley
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific United Kingdom of Great Britain and Ireland, British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, C ...
), and uses a specified
set of generators for the group. It is a central tool in
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
and
geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such group (mathematics), groups and topology, topological and geometry, geometric pro ...
. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of
expander graphs
In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applicati ...
.
Definition
Let
be a
group
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
and
be a
generating set
In mathematics and physics, the term generator or generating set may refer to any of a number of related concepts. The underlying concept in each case is that of a smaller set of objects, together with a set of operations that can be applied to ...
of
. The Cayley graph
is an
edge-colored directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
constructed as follows:
[ In his Collected Mathematical Papers 10: 403–405.]
* Each element
of
is assigned a vertex: the vertex set of
is identified with
* Each element
of
is assigned a color
.
* For every
and
, there is a directed edge of color
from the vertex corresponding to
to the one corresponding to
.
Not every source 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 sometimes assumed to be
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
(i.e.
) and not containing the identity element of the group. In this case, the uncolored Cayley graph can be represented as a simple undirected
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
.
In
geometric group theory
Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such group (mathematics), groups and topology, topological and geometry, geometric pro ...
, the set
is often assumed to be finite which corresponds to
being locally finite.
Examples
* Suppose that
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.
* Similarly, if
is the finite
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
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.
* The Cayley graph of the
direct product of groups
In mathematics, specifically in group theory, the direct product is an operation that takes two groups and and constructs a new group, usually denoted . This operation is the group-theoretic analogue of the Cartesian product of sets and is one ...
(with the
cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of generating sets as a generating set) is the
cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of the corresponding Cayley graphs. Thus the Cayley graph of the abelian group
with the set of generators consisting of four elements
is the infinite
grid
Grid, The Grid, or GRID may refer to:
Common usage
* Cattle grid or stock grid, a type of obstacle is used to prevent livestock from crossing the road
* Grid reference, used to define a location on a map
Arts, entertainment, and media
* News g ...
on the plane
, while for the direct product
with similar generators the Cayley graph is the
finite grid on a
torus
In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle.
If the axis of revolution does not tou ...
.
* A Cayley graph of the
dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ge ...
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 Named after the 19th century British mathematician Arthur Cayley, a Cayley table describes the structure of a finite group by arranging all the possible products of all the group's elements in a square table reminiscent of an addition or multiplicat ...
of the group
can be derived from the
group presentation
In mathematics, a presentation is one method of specifying a group. A presentation of a group ''G'' comprises a set ''S'' of generators—so that every element of the group can be written as a product of powers of some of these generators—and ...
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
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
on two generators
and
corresponding to the set
is depicted at the top of the article, and
represents the
identity element
In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
. 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
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
and is a key ingredient in the proof of the
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be p ...
.
* 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
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...
infinite group, and despite being a three-dimensional space, the Cayley graph has four-dimensional
volume growth.
Characterization
The group
acts
The Acts of the Apostles ( grc-koi, Πράξεις Ἀποστόλων, ''Práxeis Apostólōn''; la, Actūs Apostolōrum) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message ...
on itself by left multiplication (see
Cayley's theorem
In group theory, Cayley's theorem, named in honour of Arthur Cayley, states that every group is isomorphic to a subgroup of a symmetric group.
More specifically, is isomorphic to a subgroup of the symmetric group \operatorname(G) whose eleme ...
). 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
. The left multiplication action of a group on itself is
simply transitive
In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism g ...
, in particular, Cayley graphs are
vertex-transitive
In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...
. 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
.
Elementary properties
* 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 (or ''closed walks'') 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
polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
s. 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 ]surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
group homomorphism
In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that
: h(u*v) = h(u) \cdot h(v)
wh ...
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
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
of degree corresponding to the free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
on the same set of generators.
* For any finite Cayley graph, considered as undirected, the vertex connectivity
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
is at least equal to 2/3 of the degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
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.
* If is the left-regular representation with matrix form denoted