Cayley graph


Cayley graph

In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a discrete group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley) and uses a particular, usually finite, set of generators for the group. It is a central tool in combinatorial and geometric group theory.

Definition

Suppose that G is a group and S is a generating set. The Cayley graph Gamma=Gamma(G,S) is a colored directed graph constructed as follows.

* Each element g of G is assigned a vertex: the vertex set V(Gamma) of Gamma is identified with G.
* Each generator s of S is assigned a color c_s.
* For any gin G, sin S, the vertices corresponding to the elements g and gs are joined by a directed edge of colour c_s. Thus the edge set E(Gamma) consists of pairs of the form (g, gs), with sin S providing the color.

In geometric group theory, the set S is usually assumed to be finite, "symmetric", i.e. S=S^{-1}, and not containing the identity element of the group. In this case, the Cayley graph is an ordinary graph: its edges are not oriented and it does not contain loops.

Examples

* Suppose that "G" = Z 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 "G" = Z"n" is the finite cyclic group 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 cycle "C""n".

* The Cayley graph of the direct product of groups is the cartesian product of the corresponding Cayley graphs. Thus the Cayley graph of the abelian group Z2 with the set of generators consisting of four elements (±1, ±1) is the infinite grid on the plane R2, while for the direct product Z"n" × Z"m" with similar generators the Cayley graph is the "n" by "m" finite grid on a torus.

* The Cayley graph of the dihedral group "D"4 on two generators α and β is depicted to the right. Red arrows represent left-multiplication by element α. Since element β is self-inverse, 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 table of the group "D"4 can be derived from the group presentation

: langle alpha, eta | alpha^4 = eta^2 = e, alpha eta = eta alpha^3 angle.

* The Cayley graph of the free group 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 element. 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 cycles. This Cayley graph is a key ingredient in the proof of the Banach–Tarski paradox.

Characterization

The group G acts on itself by the left multiplication (see Cayley's theorem). This action may be viewed as the action of G on its Cayley graph. Explicitly, an element hin G maps a vertex gin V(Gamma) to the vertex hgin V(Gamma). The set of edges of the Cayley graph is preserved by this action: the edge (g,gs) is transformed into the edge (hg,hgs). The left multiplication action of any group on itself is simply transitive, in particular, the Cayley graph is vertex transitive. This leads to the following characterization of Cayley graphs:

: "A graph Gamma is a Cayley graph of a group G if and only if it admits a simply transitive action of G by graph automorphisms (i.e. preserving the set of edges)".

To recover the group G and the generating set S from the Cayley graph Gamma=Gamma(G,S), select a vertex v_1in V(Gamma) and label it by the identity element of the group. Then label each vertex v of Gamma by the unique element of G that trasforms v_1 into v. The set S of generators of G that yields Gamma 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 s of the generating set is its own inverse, s=s^{-1}, then it is generally represented by an undirected edge.

* The Cayley graph Gamma(G,S) depends in an essential way on the choice of the set S of generators. For example, if the generating set S has k elements then each vertex of the Cayley graph has k incoming and k outgoing directed edges. In the case of a symmetric generating set S with r elements, the Cayley graph is a regular graph of degree r.

* Cycles (or "closed walks") in the Cayley graph indicate relations between the elements of S. In the more elaborate construction of the Cayley complex of a group, closed paths corresponding to relations are "filled in" by polygons.

* If f: G' o G is a surjective group homomorphism and the images of the elements of the generating set S' for G' are distinct, then it induces a covering of graphs

:: ar{f}: Gamma(G',S') o Gamma(G,S),quad where S=f(S').

: In particular, if a group G has k generators, all of order different from 2, and the set S consists of these generators together with their inverses, then the Cayley graph Gamma(G,S) is covered by the infinite regular tree of degree 2k corresponding to the free group on the same set of generators.
* A graph Gamma(G,S) can be constructed even if the set S does not generate the group G. However, it is disconnected 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 S.

* For any Cayley graph, considered as undirected, the vertex connectivity is equal to the degree of the graph. [cite book|title=Technical Report TR-94-10|author=Babai, L.|year=1996|publisher=University of Chicago [http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps] ]

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.

Connection to group 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.

See also

* Bethe lattice
* Vertex-transitive graph
* Generating set of a group
* Presentation of a group
* Lovász conjecture
* Cube-connected cycles

Notes


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Cayley graph — noun A graph (collection of vertices and edges) encoding information about a group and its generators …   Wiktionary

  • Cayley-Baum — Bethe Gitter für z=3 Ein Bethe Gitter (nach Hans Bethe), auch Cayley Baum (nach Arthur Cayley) genannt, ist ein zusammenhängender, wirbelfreier Graph, bei dem jeder Knoten mit z anderen Knoten verbunden ist (z wird auch Koordinationszahl genannt) …   Deutsch Wikipedia

  • Graph theory — In 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 …   Wikipedia

  • Cayley, Arthur — ▪ British mathematician born August 16, 1821, Richmond, Surrey, England died January 26, 1895, Cambridge, Cambridgeshire  English mathematician and leader of the British school of pure mathematics that emerged in the 19th century. The interested… …   Universalium

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Cayley's formula — 2^{2 2}=1 tree with 2 vertices,3^{3 2}=3 trees with 3 vertices and 4^{4 2}=16trees with 4 vertices.In mathematics, Cayley s formula is a result in graph theory named after Arthur Cayley. It states that if n is an integer bigger than 1, the number …   Wikipedia

  • Distance-regular graph — Graph families defined by their automorphisms distance transitive distance regular strongly regular …   Wikipedia

  • Vertex-transitive graph — 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 : V(G) → V(G) such that : f (v1) = v2. In other words, a graph is vertex transitive if its automorphism group …   Wikipedia

  • Möbius–Kantor graph — Named after August Ferdinand Möbius and S. Kantor Vertices 16 …   Wikipedia

  • Petersen graph — Infobox graph name = Petersen graph image caption = The Petersen graph is most commonly drawn as a pentagon with a pentagram inside, with five spokes. namesake = Julius Petersen vertices = 10 edges = 15 radius = 2 diameter = 2 girth = 5 chromatic …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.