4d. Cayley graphs

[math] \newcommand{\mathds}{\mathbb}[/math]

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 have kept the best for the end. We have the following notion, that we already met in a vague form in chapter 1, and which is something quite far-reaching:

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].

We will see in what follows that most of the graphs that we met so far are Cayley graphs, and in addition, with [math]G[/math] being abelian in most cases. Before starting with the examples, however, let us point out that the Cayley graph depends, in a crucial way, on the generating set [math]S[/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 order to construct now examples, let us start with the simplest finite groups that we know. The simplest such group is the cyclic group [math]\mathbb Z_N[/math], and we have:

Proposition

The [math]N[/math]-gon graph, 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]]

is the Cayley graph of [math]\mathbb Z_N= \lt \pm 1 \gt [/math], with [math]\mathbb Z_N[/math] being written here additively.

Show Proof

This is clear, because in additive notation, our condition for the edges [math]g-h[/math] reads [math]g=h\pm1[/math], so we are led to the [math]N[/math]-gon graph in the statement.

■

The next thing that we can do is to look at the products of cyclic groups. In the simplest case here, that of a product of the group [math]\mathbb Z_2[/math] with itself, we obtain:

Theorem

The square graph, namely

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

is the Cayley graph of [math]\mathbb Z_2\times\mathbb Z_2[/math], with generating set [math]S=\{(1,0),(0,1)\}[/math].

Show Proof

This is something which requires a bit of thinking. We must first draw the 4 elements of [math]\mathbb Z_2\times\mathbb Z_2[/math], and this is best done by using their coordinates, as follows:

[[math]] \xymatrix@R=17pt@C=17pt{ 10&&11\\ \\ 00&&10 } [[/math]]

Now let us construct the edges. In additive notation, our condition for the edges [math](a,b)-(c,d)[/math] reads either [math](a,b)=(c,d)+(1,0)[/math] or [math](a,b)=(c,d)+(0,1)[/math], which amounts in saying that the passage [math](a,b)\to(c,d)[/math] appears by modifying one coordinate, and keeping the other coordinate fixed. We conclude from this that the edges are as follows:

[[math]] \xymatrix@R=20pt@C=20pt{ 10\ar@{-}[dd]\ar@{-}[rr]&&11\ar@{-}[dd]\\ \\ 00\ar@{-}[rr]&&10 } [[/math]]

Now by removing the vertex labels, we obtain the usual square, as claimed.

■

What comes next? Obviously, more complicated products of cyclic groups. Here the situation ramifies a bit, and as our next basic example, we have:

Proposition

The prism graph, namely

[[math]] \xymatrix@R=20pt@C=20pt{ &&&&\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]]

appears as Cayley graph of the group [math]\mathbb Z_2\times\mathbb Z_3[/math].

Show Proof

This follows a bit as before, for the square, and we will leave the details here, including of course finding the correct generating set [math]S[/math], as an instructive exercise.

■

As a main example now, obtained by staying with [math]\mathbb Z_2[/math], we have:

Theorem

The cube graph, namely

[[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]]

is the Cayley graph of [math]\mathbb Z_2^3[/math], with generating set [math]S=\{(1,0,0),(0,1,0),(0,0,1)\}[/math].

Show Proof

This is clear, as before for the square. In fact, we have already met this in chapter 1, with details, and this is our come-back to the subject, long overdue.

■

Looking at what we have so far, it is pretty much clear that Theorem 4.31 and Theorem 4.33 are of the same nature. The joint extension of these theorems, along with the computation of the corresponding symmetry group, leads to the following statement:

Theorem

The Cayley graph of the group [math]\mathbb Z_2^N[/math] is the hypercube

[[math]] \square_N\subset\mathbb R^N [[/math]]

and the symmetry group of [math]\square_N[/math], called hyperoctahedral group, is given by

[[math]] H_N=\mathbb Z_2^N\rtimes S_N [[/math]]

with the permutations acting via [math]\sigma(e_1,\ldots,e_k)=(e_{\sigma(1)},\ldots,e_{\sigma(k)})[/math].

Show Proof

Regarding the Cayley graph assertion, this follows as for the square, or for the cube. As for the computation of [math]H_N[/math], this can be done as follows:

(1) Consider the standard cube in [math]\mathbb R^N[/math], centered at 0, and having as vertices the points having coordinates [math]\pm1[/math]. With this picture in hand, it is clear that the symmetries of the cube coincide with the symmetries of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math].

(2) In order to count now these symmetries, observe first that we have as examples the [math]N![/math] permutations of the [math]N[/math] coordinate axes of [math]\mathbb R^N[/math]. But each of these permutations [math]\sigma\in S_N[/math] can be further “decorated” by a sign vector [math]e\in\{\pm1\}^N[/math], consisting of the possible [math]\pm1[/math] flips which can be applied to each coordinate axis, at the arrival. Thus, we have:

[[math]] |H_N| =|S_N|\cdot|\mathbb Z_2^N| =N!\cdot2^N [[/math]]

(3) Now observe that at the level of the cardinalities, the above formula gives:

[[math]] |H_N|=|\mathbb Z_2^N\times S_N| [[/math]]

To be more precise, given an element [math]g\in H_N[/math], the element [math]\sigma\in S_N[/math] is the corresponding permutation of the [math]N[/math] coordinate axes, regarded as unoriented lines in [math]\mathbb R^N[/math], and [math]e\in\mathbb Z_2^N[/math] is the vector collecting the possible flips of these coordinate axes, at the arrival. Now observe that the product formula for two such pairs [math]g=(e,\sigma)[/math] is as follows, with the permutations [math]\sigma\in S_N[/math] acting on the elements [math]f\in\mathbb Z_2^N[/math] as in the statement:

[[math]] (e,\sigma)(f,\tau)=(ef^\sigma,\sigma\tau) [[/math]]

(4) Thus, we are precisely in the framework of Definition 4.27, and we conclude that we have a crossed product decomposition [math]H_N=\mathbb Z_2^N\rtimes S_N[/math], as in the statement.

■

Many more things can be said here, and more on all this in Part III of this book.

General references

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