12a. Cayley graphs

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

We discuss here the Cayley graphs of finite groups, and what can be done with them. We have already met these graphs in chapter 4, their definition being as follows:

Definition

Associated to any finite group [math]G= \lt S \gt [/math], with the generating set [math]S[/math] assumed to satisfy [math]1\notin S=S^{-1}[/math], is its Cayley graph, constructed as follows:

The vertices are the group elements [math]g\in G[/math].
Edges [math]g-h[/math] are drawn when [math]h=gs[/math], with [math]s\in S[/math].

As a first observation, the Cayley graph is indeed a graph, because our assumption [math]S=S^{-1}[/math] on the generating set shows that we have [math]g-h\implies h-g[/math], as we should, and also because our assumption [math]1\notin S[/math] excludes the self-edges, [math]g\not\!\!-\,g[/math].

Observe also that the Cayley graph depends, in a crucial way, on the generating set [math]S[/math] satisfying [math]1\notin S=S^{-1}[/math]. Indeed, if we choose for instance [math]S=G-\{1\}[/math], we obtain the complete graph with [math]N=|G|[/math] vertices, and this regardless of what our group [math]G[/math] is. Thus, the Cayley graph as constructed above is not exactly associated to the group [math]G[/math], but rather to the group [math]G[/math] viewed as finitely generated group, [math]G= \lt S \gt [/math].

In view of this, we will usually look for generating sets [math]S[/math] which are minimal, in order to perform our Cayley graph construction, and get non-trivial graphs. Here are now some examples, with minimal generating sets, that we know well from chapter 4:

Proposition

We have the following examples of Cayley graphs, each time with respect to the standard, minimal generating set satisfying [math]S=S^{-1}[/math]:

For [math]\mathbb Z_N[/math] we obtain the cycle graph [math]C_N[/math].
For [math]\mathbb Z_2\times\mathbb Z_3[/math] we obtain the prism [math]P(C_3)[/math].
For [math]\mathbb Z_2^N[/math] we obtain the hypercube graph [math]\square_N[/math].

Show Proof

This is something elementary, that we know well from chapter 4, with the generating set in question being [math]S=\{-1,1\}[/math] for the cyclic group [math]\mathbb Z_N[/math], written additively, unless we are in the case [math]N=2[/math], where this set simply becomes [math]S=\{1\}[/math], again written additively, and with the generating sets for products being obtained in the obvious minimal way, by taking the union of the generating sets of the components:

(1) For the group [math]\mathbb Z_N= \lt -1,1 \gt [/math], written additively, our condition for the edges [math]g-h[/math] reads [math]g=h\pm1[/math], so we are led to the cycle graph [math]C_N[/math], namely:

[[math]] \xymatrix@R=12pt@C=12pt{ &\bullet\ar@{-}[r]\ar@{-}[dl]&\bullet\ar@{-}[dr]\\ \bullet\ar@{-}[d]&&&\bullet\ar@{-}[d]\\ \bullet\ar@{-}[dr]&&&\bullet\ar@{-}[dl]\\ &\bullet\ar@{-}[r]&\bullet} [[/math]]

(2) For the group [math]\mathbb Z_2\times\mathbb Z_3= \lt (1,0),(0,1),(0,2) \gt [/math], again written additively, our condition for the edges takes the following form:

[[math]] (g,a)-(h,b)\Longleftrightarrow g=h,\, a=b\pm1\mbox{ \rm{or} }g=h+1,a=b [[/math]]

But this leads to the prism graph [math]P(C_3)[/math], which is as follows:

[[math]] \xymatrix@R=15pt@C=15pt{ &&&&\bullet\ar@{-}[ddl]\ar@{-}[ddr]\\ &\bullet\ar@{-}[ddl]\ar@{-}[ddr]\ar@{-}[urrr]\\ &&&\bullet\ar@{-}[rr]&&\bullet\\ \bullet\ar@{-}[rr]\ar@{-}[urrr]&&\bullet\ar@{-}[urrr] } [[/math]]

(3) Finally, for the group [math]\mathbb Z_2^N= \lt 1_1,\ldots,1_N \gt [/math], with [math]1_i[/math] standing for the standard generators of the components, our condition for the edges takes the following form:

[[math]] g-h\iff\exists!\,i,g_i\neq h_i [[/math]]

Now if we represent the elements of [math]\mathbb Z_2^N=(0,1)^N[/math] as points in [math]\mathbb R^N[/math], in the obvious way, we are led to the hypercube graph [math]\square_N[/math], which is as follows:

[[math]] \xymatrix@R=18pt@C=20pt{ &\bullet\ar@{-}[rr]&&\bullet\\ \bullet\ar@{-}[rr]\ar@{-}[ur]&&\bullet\ar@{-}[ur]\\ &\bullet\ar@{-}[rr]\ar@{-}[uu]&&\bullet\ar@{-}[uu]\\ \bullet\ar@{-}[uu]\ar@{-}[ur]\ar@{-}[rr]&&\bullet\ar@{-}[uu]\ar@{-}[ur] } [[/math]]

Thus, we are led to the conclusions in the statement.

■

The above result dates back to chapter 4, and time now to improve it, by using the product operations for graphs, that we learned in chapter 10. We have:

Theorem

Given two groups [math]G= \lt S \gt [/math] and [math]H= \lt T \gt [/math], we have

[[math]] G\times H= \lt S\times1,1\times T \gt [[/math]]

and at the level of the corresponding Cayley graphs, we have the formula

[[math]] X_{G\times H}=X_G\,\square\,X_H [[/math]]

involving the Cartesian product operation for graphs [math]\square[/math].

Show Proof

We have indeed a generating set, which satisfies the condition [math]1\notin S=S^{-1}[/math]. Now observe that when constructing the Cayley graph, the edges are as follows:

[[math]] (g,a)-(h,b)\Longleftrightarrow g=h,\, a-b\mbox{ \rm{or} }g-h,a=b [[/math]]

Thus, we obtain indeed a Cartesian product [math]X_{G\times H}=X_G\,\square\,X_H[/math], as claimed.

■

Along the same lines, let us record as well the following result, which is however rather anecdotical, first because the subgroup [math]K\subset G\times H[/math] appearing below might not equal the group [math]G\times H[/math] itself, and also because, even when it does, the generating set [math]S\times T[/math] that we use is much bigger than the generating set [math]S\times1,1\times T[/math] from Theorem 12.3:

Proposition

Given two groups [math]G= \lt S \gt [/math] and [math]H= \lt T \gt [/math], if we set

[[math]] K= \lt S\times T \gt \subset G\times H [[/math]]

then at the level of the corresponding Cayley graphs, we have the formula

[[math]] X_K=X_G\times X_H [[/math]]

involving the direct product operation for graphs [math]\times[/math].

Show Proof

As before, we have a set satisfying the condition [math]1\notin S=S^{-1}[/math]. Now observe that when constructing the Cayley graph, the edges are as follows:

[[math]] (g,a)-(h,b)\Longleftrightarrow g-h,\, a-b [[/math]]

Thus, we obtain in this case a direct product [math]X_K=X_G\times X_H[/math], as claimed.

■

As mentioned above, this latter result is something anecdotical, and we will not use it, in what follows. Thus, our convention for products will be the one in Theorem 12.3. We can now generalize the various computations from Proposition 12.2, as follows:

Theorem

For a finite abelian group, written as

[[math]] G=\mathbb Z_{N_1}\times\ldots\times\mathbb Z_{N_k} [[/math]]

and with standard generating set, the corresponding Cayley graph is:

[[math]] X_G=C_{N_1}\,\square\,\ldots\,\square\,C_{N_k} [[/math]]

That is, we obtain a Cartesian product of cycle graphs.

Show Proof

This follows indeed from Proposition 12.2 (1), and from Theorem 12.3.

■

Getting now to symmetry groups, as a first observation, we have:

Proposition

Given a finite group, [math]G= \lt S \gt [/math] with [math]1\notin S=S^{-1}[/math], we have an action of this group on its associated Cayley graph,

[[math]] G\curvearrowright X_G [[/math]]

and so [math]G\subset G(X_G)[/math]. However, this inclusion is not an isomorphism, in general.

Show Proof

We have several assertions here, the idea being as follows:

(1) Consider indeed the Cayley action of [math]G[/math] on itself, which is given by:

[[math]] G\subset S_G\quad,\quad g\to[h\to gh] [[/math]]

(2) Thus [math]G[/math] acts on the vertices of its Cayley graph [math]X_G[/math], and our claim is that the edges are preserved by this action. Indeed, given an edge, [math]h-hs[/math] with [math]s\in S[/math], a group element [math]g\in G[/math] will transform it into [math]gh-ghs[/math], which is an edge too.

(3) Thus, the first assertion holds indeed. As for the second assertion, this holds too, and in a very convincing way, for instance because for the groups in Proposition 12.2, the corresponding Cayley graphs and their symmetry groups are as follows:

[[math]] \mathbb Z_N\to C_N\to D_N [[/math]]

[[math]] \mathbb Z_2\times\mathbb Z_3\to P(C_3)\to D_6 [[/math]]

[[math]] \mathbb Z_2^N\to\square_N\to H_N [[/math]]

Thus, we are led to the conclusions in the statement.

■

In relation with the above, a first question would be that of suitably fine-tuning the construction of the Cayley graph [math]X_G[/math], as to have as end result [math]G=G(X_G)[/math], which would be something nice. We will discuss this later, the idea being that this can be done indeed, by adding orientation, or colors, or both, to the construction of the Cayley graph [math]X_G[/math].

As a second question now, we can try to understand the operation [math]G\to G(X_G)[/math], with our present definition for the Cayley graph [math]X_G[/math]. Many things can be said here, and to start with, we have the following result, generalizing our computation for [math]\mathbb Z_2^N[/math]:

Theorem

The symmetry group of the Cayley graph of [math]G=\mathbb Z_s^N[/math], which is

[[math]] X_G=C_s^{\,\square N} [[/math]]

according to our previous results, is the complex reflection group [math]H_N^s[/math]:

[[math]] G(X_G)=H_N^s [[/math]]

Thus, in this case, the operation [math]G\to G(X_G)[/math] is given by [math]\mathbb Z_s^N\to\mathbb Z_s^N\rtimes S_N[/math].

Show Proof

This is something that we discussed in chapter 4 at [math]s=2[/math], with the graph involved there being the hypercube [math]X_G=\square_N[/math]. In general the proof is similar, by using the theory of the complex reflection groups [math]H_N^s[/math], that we developed in chapter 9.

■

Many other things can be said, along these lines, for instance with a generalization of the computation [math]\mathbb Z_2\times\mathbb Z_3\to P(C_3)\to D_6[/math] too, and with a number of other results regarding the operation [math]G\to X_G\to G(X_G)[/math], for the finite abelian groups [math]G[/math]. We will leave doing some study here as an instructive exercise.

General references

Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].