Cayley graph

A Cayley graph is a mathematical tool used to visualize the structure of a group. In mathematics, a group is a set of elements governed by specific rules. A Cayley graph, also called a Cayley color graph or group diagram, encodes these abstract rules into a visual shape.

This encoding makes it easier to study the symmetry and patterns of the group. These graphs are essential in fields like combinatorial and geometric group theory. They also serve as important building blocks for creating expander graphs.

To construct a Cayley graph, you must first choose a generating set for the group. A generating set consists of specific elements that can produce every other element in the group through repeated operations. The construction begins by assigning a vertex to every single element in the group. Next, you assign a specific color to each generator in your set. For every element in the group, you draw a directed edge of a specific color to a new element.

This edge represents the result of applying that generator to the current element. If a generator is its own inverse, the edge is often drawn as an undirected line without an arrow.

Cayley graphs can take many different forms depending on the group and the generators used. If the generating set is not large enough to cover the whole group, the graph will be disconnected. In this case, each separate piece, or connected component, represents a coset of the subgroup. For the infinite cyclic group using the generator 1 and its inverse, the graph is simply an infinite path. If you use a finite cyclic group of order n, the graph forms a cycle. These specific types of graphs are known as circulant graphs. More complex groups, like the direct product of groups, create even more intricate structures like grids.

History shows that these ideas are rooted in the work of Arthur Cayley. His research led to Cayley's theorem, which suggests the fundamental link between groups and these graphs. One famous example involves the free group on two generators. The Cayley graph for this group is an infinite tree with no cycles.

Because there are no relations between the generators, you can never follow a path that leads back to your starting point. This specific structure is also known as a Bethe lattice or a Cayley tree. It plays a key role in the proof of the Banach-Tarski paradox.

There is a deep mathematical connection between the graph and the group's symmetry. The group actually acts on its own Cayley graph through left multiplication. This action moves vertices and edges around while keeping the colors and directions exactly the same. Because of this, Cayley graphs are vertex-transitive, meaning every vertex looks identical to the others.

You can actually reconstruct the entire group and its generators just by looking at an unlabeled directed graph. You simply pick one vertex to be the identity element and label the others based on the edges.

Advanced study of these graphs often involves looking at their adjacency matrices. The adjacency matrix is a grid of numbers that describes which vertices are connected to each other. By studying the eigenvalues of this matrix, mathematicians can learn about the group's properties. For example, in an Abelian group, the eigenvalues can be calculated using the group's characters.

These values can help identify if a graph is "integral," meaning all its eigenvalues are integers. This is a complex area of study that connects spectral graph theory to group theory.

In geometric group theory, the shape of the graph tells us about the group's nature. For infinite groups, we look at the "coarse geometry" of the Cayley graph. This means we study the large-scale structure rather than small details. For a finitely generated group, this geometric view is an intrinsic property that does not change with different generators. This allows mathematicians to treat groups as geometric objects that can be measured and mapped. By studying these connections, we see how algebra and geometry merge into one field.