 The Cayley graph of the free group on two generators a and b In mathematics, a Cayley graph, named after Arthur Cayley, is a graph that encodes the structure of a group. It is a central tool in combinatorial and geometric group theory. Image File history File links Cayley_graph_of_F2. ...
Image File history File links Cayley_graph_of_F2. ...
The Cayley graph of the free group on two generators a and b 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...
Euclid, detail from The School of Athens by Raphael. ...
Arthur Cayley (August 16, 1821 - January 26, 1895) was a British mathematician. ...
In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ...
Geometric group theory and combinatorial group theory are two closely related branches of mathematics, which study infinite discrete groups. ...
Geometric group theory and combinatorial group theory are two closely related branches of mathematics, which study infinite discrete groups. ...
Let G be a group, and let S be a generating set for G. The Cayley graph of G with respect to S has a vertex for every element of G, with an edge from g to gs for all elements  and  . 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. ...
Example
For example, the Cayley graph of the free group on two generators a and b is depicted to the right. (Note that e represents the identity element.) Travelling right along an edge represents multiplying on the right by a, while travelling up corresponds to multiplying by b. Since the free group has no relations, the graph has no cycles. The Cayley graph of the free group on two generators a and b 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...
In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...
In mathematics, a finitary relation is defined by one of the formal definitions given below. ...
Variations The above definition gives a connected, directed graph. There are a number of slight variations on the definition: - Usually S is not allowed to contain the identity element e.
- If the set S doesn't generate the whole group, the Cayley graph isn't connected.
- In some contexts, left multiplication is used instead of right. That is, edges go from g to sg.
- In many contexts, the generating set is assumed to be symmetric, meaning that s − 1 is in S whenever s is. In this case, the graph is undirected.
The Sabidussi Theorem G acts on itself by multiplication on the left. This action induces an action of G on its Cayley graph. Explicitly, an element h sends a vertex g to the vertex hg, and the edge (g,gs) to the edge (hg,hgs). Since the action of G on itself is transitive, any Cayley graph is vertex-transitive. The Sabidussi theorem gives a characterization of Cayley graphs: Graph X is a Cayley graph if and only if the automorphism group of X contains a subgroup G acting regularly on the vertex set of X. In mathematics, a symmetry group describes all symmetries of objects. ...
In grammar, a verb is transitive if it takes an object. ...
In mathematics, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism f : G → G such that f ( v1 ) = v2. ...
Schreier coset graph If one, instead, takes the vertices to be right cosets of a fixed subgroup H, one obtains a related construction, the Schreier coset graph, which is at the basis of coset enumeration or the Todd-Coxeter process. In mathematics, coset enumeration is the problem of counting the cosets of a subgroup H of a group G given in terms of a presentation. ...
The Todd-Coxeter algorithm, discovered by Todd and Coxeter in 1936, is a procedure that can solve the coset enumeration problem. ...
Connection to graph theory Insights into 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. In mathematics and computer science, the adjacency matrix for a finite graph on n vertices is an n × n matrix where the nondiagonal entry aij is the number of edges joining vertex and vertex , and the diagonal entry aii is either twice the number of loops at vertex or just...
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the eigenvalues and eigenvectors of its adjacency matrix. ...
A standard Cayley graph for the direct product of groups is the cartesian product of the corresponding Cayley graphs. For instance, a cycle Cn is a Cayley graph for the cyclic group Zn. Therefore the cartesian product  , (an n by m grid on torus) is a Cayley graph for the direct product  . In mathematics, one can often define a direct product of objects already known, giving a new one. ...
In mathematics, the Cartesian product (or direct product) of two sets X and Y, denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y: The Cartesian product is named after René Descartes...
In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ...
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 a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na...
A torus. ...
See also |
Feeds |
Contact