Cayley Graph - Examples

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 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 .
  • 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 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 torus.
  • A Cayley graph of the dihedral group D4 on two generators a and b is depicted to the left. Red arrows represent left-multiplication by element a. Since element b is self-inverse, the blue lines which represent left-multiplication by element b are undirected. Therefore the graph is mixed: it has eight vertices, eight arrows, and four edges. The Cayley table of the group D4 can be derived from the group presentation

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.

  • 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.
  • A Cayley graph of the discrete Heisenberg group \left\{ \begin{pmatrix} 1 & x & z\\ 0 & 1 & y\\ 0 & 0 & 1\\ \end{pmatrix},\ x,y,z \in \mathbb{Z}\right\}

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-commutative infinite group, and despite being three-dimensional in some sense, the Cayley graph has four-dimensional volume growth.

Read more about this topic:  Cayley Graph

Famous quotes containing the word examples:

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)

    “No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
    —André Breton (1896–1966)

    “There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
    —Bernard Mandeville (1670–1733)