|
|
|
|
|
Cayley GraphIn 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. Let be a group, and let be a generating set for . The Cayley graph of with respect to has a vertex for every element of , with an edge from to for all elements and . For example, the Cayley graph of the free group on two generators and is depicted to the right. (Note that represents the identity element.) Travelling right along an edge represents multiplying on the right by , while travelling up corresponds to multiplying by . Since the free group has no relations, the graph has no cycles. The above definition gives a connected, directed graph. There are a number of slight variations on the definition: - If the set 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 to .
- In many contexts, the generating set is assumed to be symmetric, meaning that is in whenever is. In this case, the graph is undirected.
acts on itself by multiplication on the left. This action induces an action of on its Cayley graph. Explicitly, an element sends a vertex to the vertex , and the edge to the edge . Since the action of on itself is transitive, any Cayley graph is vertex-transitive. If one takes the vertices to instead 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. 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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|