In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, a
Cayley graph, also known as a
Cayley colour graph, is a
graphIn mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
that encodes the structure of a
discrete groupIn mathematics, a discrete group is a group G equipped with the discrete topology. With this topology G becomes a topological group. A discrete subgroup of a topological group G is a subgroup H whose relative topology is the discrete one...
. Its definition is suggested by
Cayley's theoremIn group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group on G...
(named after
Arthur CayleyArthur Cayley was a British mathematician. He helped found the modern British school of pure mathematics.As a child, Cayley enjoyed solving complex math problems for amusement. He entered Trinity College, Cambridge, where he excelled in Greek, French, German, and Italian, as well as mathematics...
) and uses a specified, usually finite,
set of generatorsIn abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses....
for the group. It is a central tool in
combinatorialIn mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group, by generators and relations...
and
geometric group theoryGeometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act .Another important...
.
Suppose that is a
groupIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
and is a
generating setIn abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses....
. The Cayley graph is a colored
directed graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows .It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of...
constructed as follows.
- Each element of is assigned a vertex: the vertex set of is identified with
- Each generator of is assigned a color .
- For any the vertices corresponding to the elements and are joined by a directed edge of colour Thus the edge set consists of pairs of the form with providing the color.
In geometric group theory, the set is usually assumed to be finite,
symmetric, i.e.
In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, a
Cayley graph, also known as a
Cayley colour graph, is a
graphIn mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
that encodes the structure of a
discrete groupIn mathematics, a discrete group is a group G equipped with the discrete topology. With this topology G becomes a topological group. A discrete subgroup of a topological group G is a subgroup H whose relative topology is the discrete one...
. Its definition is suggested by
Cayley's theoremIn group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group on G...
(named after
Arthur CayleyArthur Cayley was a British mathematician. He helped found the modern British school of pure mathematics.As a child, Cayley enjoyed solving complex math problems for amusement. He entered Trinity College, Cambridge, where he excelled in Greek, French, German, and Italian, as well as mathematics...
) and uses a specified, usually finite,
set of generatorsIn abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses....
for the group. It is a central tool in
combinatorialIn mathematics, combinatorial group theory is the theory of free groups, and the concept of a presentation of a group, by generators and relations...
and
geometric group theoryGeometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act .Another important...
.
Definition
Suppose that is a
groupIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
and is a
generating setIn abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses....
. The Cayley graph is a colored
directed graphA directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows .It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of...
constructed as follows.
- Each element of is assigned a vertex: the vertex set of is identified with
- Each generator of is assigned a color .
- For any the vertices corresponding to the elements and are joined by a directed edge of colour Thus the edge set consists of pairs of the form with providing the color.
In geometric group theory, the set is usually assumed to be finite,
symmetric, i.e. and not containing the identity element of the group. In this case, the uncolored Cayley graph is an ordinary
graphIn mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
: its edges are not oriented and it does not contain loops iff .
Examples
- Suppose that is the infinite cyclic group and the set S consists of the standard generator 1 and its inverse (−1 in the additive notation) then the Cayley graph is an infinite chain.
- Similarly, if is the finite cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
of order n and the set S consists of two elements, the standard generator of G and its inverse, then the Cayley graph is the cycleIn graph theory, a cycle graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called C
n...
.
- The Cayley graph of the direct product
In mathematics, one can often define a direct product of objectsalready known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set....
of groups is the cartesian productIn graph theory, the Cartesian product G H of graphs G and H is a graph such that* the vertex set of G H is the Cartesian product V × V; and...
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 on the plane , while for the direct product with similar generators the Cayley graph is the finite grid on a torusIn geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with and not touching the circle. Examples of tori include the surfaces of doughnuts and inner tubes. The solid contained by the surface is known as a toroid...
.
- The Cayley graph of the dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
D4 on two generators α and β is depicted to the left. Red arrows represent left-multiplication by element α. Since element β is self-inverseA Cayley table, after the 19th century British mathematician Arthur Cayley, 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 multiplication table...
, the blue lines which represent left-multiplication by element β are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The Cayley tableA Cayley table, after the 19th century British mathematician Arthur Cayley, 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 multiplication table...
of the group D4 can be derived from the group presentationIn mathematics, one method of defining a group is by a presentation. One specifies a set S of generators so that every element of the group can be written as a product of some of these generators, and a set R of relations among those generators...
- The Cayley graph of the free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses .A related but different notion is a free abelian group.- History...
on two generators a, b corresponding to the set S = {a, b, a−1, b−1} is depicted at the top of the article, and e represents the identity elementIn mathematics, an identity element is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them...
. Travelling along an edge to the right represents right multiplication by a, while travelling along an edge upward corresponds to the multiplication by b. Since the free group has no relations, the Cayley graph has no cyclesCycle in graph theory and computer science has several meanings:* A closed walk, with repeated vertices allowed. See path ....
. This Cayley graph is a key ingredient in the proof of the Banach–Tarski paradoxThe Banach–Tarski paradox is a theorem in set theoretic geometry which states that a solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, which can then be put back together in a different way to yield two identical copies of the original ball...
.
- A Cayley graph of the discrete Heisenberg group
is depicted to the right. The generators used in the picture are the three matrices
X, Y, Z given by the three permutations of 1, 0, 0 for the entries
x, y, z. They satisfy the relations
, which can also be read off from the picture. This is a
non-commutativeIn mathematics, a nonabelian group, also sometimes called a non-commutative group, is a group such that there are at least two elements a and b of G such that a * b ≠ b * a...
infinite group, and despite being three-dimensional in some sense, the Cayley graph has four-dimensional
volume growthIn group theory, the growth rate of a group with respect to a symmetric generating set describes the size of balls in the group. Every element in the group can be written as a product of generators, and the growth rate counts the number of elements that can be written as a product of length...
.
Characterization
The group
actsIn algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
on itself by the left multiplication (see
Cayley's theoremIn group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group on G...
). This action 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 is preserved by this action: the edge is transformed into the edge . The left multiplication action of any group on itself is simply transitive, in particular, the Cayley graph is
vertex transitiveIn the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismsuch that...
. This leads to the following characterization of Cayley graphs:
- Sabidussi Theorem: A graph is a Cayley graph of a group if and only if it admits a simply transitive action of by graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
s (i.e. preserving the set of edges).
To recover the group and the generating set from the Cayley 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 transforms into The set of generators of that yields 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).
Elementary properties
- If a member of the generating set is its own inverse, , then it is generally represented by an undirected edge.
- 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 graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency...
of degree
- Cycles
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
(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 polygonIn geometry a polygon is traditionally a plane figure that is bounded by a closed path or circuit, composed of a finite sequence of straight line segments . These segments are called its edges or sides, and the points where two edges meet are the polygon's vertices or corners...
s.
- If is a surjective group homomorphism
In mathematics, given two groups and , a group homomorphism from to is a function h : G → H such that for all u and v in G it holds that...
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 mathematics, more specifically graph theory, a tree is a graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
of degree corresponding to the free groupIn mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses .A related but different notion is a free abelian group.- History...
on the same set of generators.
- A graph can be constructed even if the set does not generate the group However, it is disconnected
In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems...
and is not considered to be a Cayley graph. In this case, each connected component of the graph represents a coset of the subgroup generated by .
- For any Cayley graph, considered as undirected, the vertex connectivity
In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems...
is at least equal to 2/3 of the degreeIn graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex is denoted The maximum degree of a graph G, denoted by Δ, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by δ, is...
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 connectivityIn mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems...
is in all cases equal to the degree.
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 graphIn the area of mathematics called combinatorial group theory, the Schreier coset graph is a graph associated to a group G, a generating set { xi : i in I }, and a subgroup H ≤ G. The vertices of the graph are the right cosets Hg = { hg : h in G } for g in G. The edges of the graph are...
, which is at the basis of
coset enumerationIn mathematics, coset enumeration is the problem of counting the cosets of a subgroup H of a group G given in terms of a presentation. As a by-product, one obtains a permutation representation for G on the cosets of H...
or the Todd-Coxeter process.
Connection to group theory
Insights into the structure of the group can be obtained by studying the
adjacency matrixIn mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of the graph and in particular applying the theorems of
spectral graph theoryIn mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of its adjacency matrix or Laplacian matrix....
.
Geometric group theory
For infinite groups, the coarse geometry of the Cayley graph is fundamental to
geometric group theoryGeometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups act .Another important...
. 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 metricIn group theory, a word metric on a group is a way to measure distance between any two elements of . As the name suggests, the word metric is a metric on , assigning to any two elements , of a distance that measures how efficiently their difference can be expressed as a word whose letters come...
(the natural distance on the Cayley graph), which determines a
metric spaceIn mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
. The coarse equivalence class of this space is an invariant of the group.
Bethe lattice
The
Bethe latticeA Bethe lattice or Cayley tree, introduced by Hans Bethe in 1935, is a connected cycle-free graph where each node is connected to z neighbours, where z is called the coordination number. It can be seen as a tree-like structure emanating from a central node, with all the nodes arranged in shells...
or
Cayley tree, is the Cayley graph of the free group on
n generators. A presentation of a group
G by
n generators corresponds to a surjective map from the free group on
n generators to the group
G, and at the level of Cayley graphs to a map from the Cayley tree to the Cayley graph. This can also be interpreted (in
algebraic topologyAlgebraic topology is a branch of mathematics which uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism...
) as the universal cover of the Cayley graph, which is not in general simply connected.
See also
- Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismsuch that...
- Generating set of a group
In abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses....
- Lovász conjecture
In graph theory, the Lovász conjecture is a classical problem on Hamiltonian paths in graphs. It says:The original article of Lovász stated the result in the opposite, butthis version became standard...
- Cube-connected cycles
In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel computing.- Definition :...
- Algebraic graph theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...