Cayley graph

The Cayley graph of the free group on two generators a and b
Graph families defined by their automorphisms
distance-transitive\boldsymbol{\rightarrow}distance-regular\boldsymbol{\leftarrow}strongly regular
\boldsymbol{\downarrow}
symmetric (arc-transitive)\boldsymbol{\leftarrow}t-transitive, t  2skew-symmetric
\boldsymbol{\downarrow}
(if connected)
vertex- and edge-transitive
\boldsymbol{\rightarrow}edge-transitive and regular\boldsymbol{\rightarrow}edge-transitive
\boldsymbol{\downarrow}\boldsymbol{\downarrow}\boldsymbol{\downarrow}
vertex-transitive\boldsymbol{\rightarrow}regular\boldsymbol{\rightarrow}(if bipartite)
biregular
\boldsymbol{\uparrow}
Cayley graph\boldsymbol{\leftarrow}zero-symmetricasymmetric

In mathematics, a Cayley graph, also known as a Cayley colour graph, Cayley diagram, group diagram, or colour group[1] is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley) and uses a specified, 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:[2]

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 uncolored Cayley graph is an ordinary graph: its edges are not oriented and it does not contain loops (single-element cycles).

Examples

Cayley graph of the dihedral group Dih4 on two generators a and b
On two generators of Dih4, which are both self-inverse
 \langle a, b | a^4 = b^2 = e, a b = b a^3 \rangle. \,

A different Cayley graph of Dih4 is shown on the right. b is still the horizontal reflection and represented by blue lines; c is a diagonal reflection and represented by green lines. As both reflections are self-inverse the Cayley graph on the right is completely undirected. This graph corresponds to the presentation

 \langle b, c | b^2 = c^2 = e, bcbc = cbcb \rangle. \,
Part of a Cayley graph of the Heisenberg group. (The coloring is only for visual aid.)

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  Z^{}_{}=XYX^{-1}Y^{-1},\  XZ=ZX,\  YZ=ZY , which can also be understood from the picture. This is a non-commutative infinite group, and despite being a three-dimensional space, the Cayley graph has four-dimensional volume growth.

Characterization

The group G acts on itself by left multiplication (see Cayley's theorem). This may be viewed as the action of G on its Cayley graph. Explicitly, an element h\in G maps a vertex g\in V(\Gamma) to the vertex hg\in V(\Gamma). The set of edges within 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:

Sabidussi Theorem: 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).[4]

To recover the group G and the generating set S from the Cayley graph \Gamma=\Gamma(G,S), select a vertex v_1\in 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 transforms 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

 \bar{f}: \Gamma(G',S')\to \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.

Schreier coset graph

Main article: 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

Knowledge about 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.

Geometric group theory

For infinite groups, the coarse geometry of the Cayley graph is fundamental to geometric group theory. 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 metric (the natural distance on the Cayley graph), which determines a metric space. The coarse equivalence class of this space is an invariant of the group.

History

The Cayley Graph was first considered for finite groups by Arthur Cayley in 1878.[2] Max Dehn in his unpublished lectures on group theory from 1909–10 reintroduced Cayley graphs under the name Gruppenbild (group diagram), which led to the geometric group theory of today. His most important application was the solution of the word problem for the fundamental group of surfaces with genus ≥ 2, which is equivalent to the topological problem of deciding which closed curves on the surface contract to a point.[6]

Bethe lattice

Main article: Bethe lattice

The Bethe lattice 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 topology) as the universal cover of the Cayley graph, which is not in general simply connected.

See also

Notes

  1. 1 2 Magnus, Wilhelm; Karrass, Abraham; Solitar, Donald (2004) [1966]. Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Courier. ISBN 978-0-486-43830-6.
  2. 1 2 Cayley, Arthur (1878). "Desiderata and suggestions: No. 2. The Theory of groups: graphical representation". Amer. J. Math. 1 (2): 174–6. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical Papers 10: 403–405.
  3. Theron, Daniel Peter (1988), An extension of the concept of graphically regular representations, Ph.D. thesis, University of Wisconsin, Madison, p. 46, MR 2636729.
  4. Sabidussi, Gert (October 1958). "On a Class of Fixed-Point-Free Graphs". Proceedings of the American Mathematical Society 9 (5): 800–4. doi:10.1090/s0002-9939-1958-0097068-7. JSTOR 2033090.
  5. See Theorem 3.7 of Babai, László (1995). "Chapter 27: Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, R. L.; Grötschel, M.; Lovász, L. Handbook of Combinatorics. Amsterdam: Elsevier. pp. 1447–1540.
  6. Dehn, Max (2012) [1987]. Papers on Group Theory and Topology. Springer-Verlag. ISBN 1461291070. Translated from the German and with introductions and an appendix by John Stillwell, and with an appendix by Otto Schreier.

External links

This article is issued from Wikipedia - version of the Wednesday, April 27, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.