12b. Orientation, colors

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 now various versions of the Cayley graph construction [math]G\to X_G[/math], which are all technically useful, obtained by adding orientation, or colors, or both. Let us start with a straightforward oriented version of Definition 12.1, 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[/math], is its oriented Cayley graph, constructed as follows:

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

Observe that the oriented Cayley graph is indeed a graph, because our assumption [math]1\notin S[/math] excludes the self-edges, [math]g\not\!\!-\,g[/math]. Observe also that in the case [math]S=S^{-1}[/math] each edge [math]g\to h[/math] has as companion edge [math]h\to g[/math], so in this case, up to replacing the pairs of edges [math]g\leftrightarrow h[/math] by usual edges [math]g-h[/math], we obtain the previous, unoriented Cayley graph.

As in the case of unoriented Cayley graphs, our graph depends a lot on the chosen writing [math]G= \lt S \gt [/math], and the point is to look for generating sets [math]S[/math] which are minimal, in order to perform our Cayley graph construction, and get non-trivial graphs.

In view of this, what we basically have to do, in order to get started with some theory, is to review the material from the previous section, by dropping the assumption [math]S=S^{-1}[/math] there, which in practice means to remove around [math]1/2[/math] of the generators.

Getting started now, as a first result, in relation with Proposition 12.2, we have:

Proposition

We have the following examples of oriented Cayley graphs, each time with respect to the standard, minimal generating set:

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

Show Proof

This is something elementary, with the convention that the generating set is [math]S=\{1\}[/math] for the cyclic group [math]\mathbb Z_N[/math], written additively, and with the generating sets for products being obtained by taking the union of the generating sets for components:

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

[[math]] \xymatrix@R=16pt@C=16pt{ &\bullet\ar[r]&\bullet\ar[dr]\\ \bullet\ar[ur]&&&\bullet\ar[d]\\ \bullet\ar[u]&&&\bullet\ar[dl]\\ &\bullet\ar[ul]&\bullet\ar[l]} [[/math]]

As an observation here, that will be of importance later, in the particular case [math]N=2[/math] what we get is the graph [math]\bullet\longleftrightarrow\bullet[/math], which is the same as the usual segment, [math]\bullet-\!\!\!-\,\bullet[/math].

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

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

But this leads to the oriented prism graph [math]P(C_3^o)[/math], which is as follows, with the convention that the usual segments [math]\bullet-\!\!\!-\,\bullet[/math] stand for double edges [math]\bullet\longleftrightarrow\bullet[/math]:

[[math]] \xymatrix@R=15pt@C=15pt{ &&&&\bullet\ar[ddr]\\ &\bullet\ar[ddr]\ar@{-}[urrr]\\ &&&\bullet\ar[uur]&&\bullet\ar[ll]\\ \bullet\ar@{-}[urrr]\ar[uur]&&\bullet\ar@{-}[urrr]\ar[ll] } [[/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, written additively, there is no true orientation, due to the reason explained in (1), and we are led to the old hypercube graph [math]\square_N[/math], 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]]

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

■

As before in the unoriented case, we can generalize these computations, as follows:

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 oriented Cayley graphs, we have the formula

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

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

Show Proof

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

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

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

■

At the level of symmetry groups now, of these Cayley graphs, things get more interesting, in the present oriented graph setting. Let us recall indeed that in the unoriented setting, the basic computations of type [math]G\to X_G\to G(X_G)[/math] were 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]]

When adding orientation, according to Proposition 12.9, these computations become:

[[math]] \mathbb Z_N\to C_N^o\to\mathbb Z_N [[/math]]

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

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

Thus, we are getting closer to a formula of type [math]G=G(X_G)[/math]. In order to discuss this, let us start with a straightforward analogue of Proposition 12.6, as follows:

Proposition

Given a finite group, [math]G= \lt S \gt [/math] with [math]1\notin S[/math], we have an action of this group on its associated oriented 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, 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\to hs[/math] with [math]s\in S[/math], a group element [math]g\in G[/math] will transform it into [math]gh\to ghs[/math], which is an edge too.

(3) Thus, the first assertion holds indeed. As for the second assertion, this holds too, the counterexample coming from the computation [math]\mathbb Z_2^N\to\square_N\to H_N[/math], discussed above.

■

Summarizing, as already said, we are certainly getting closer to a formula of type [math]G=G(X_G)[/math], but we are still not there, with some counterexamples still persisting. We will come back to this question in a moment, with a solution using colors.

Before leaving the subject, let us record the following result, due to Sabidussi:

Theorem

An oriented graph [math]X[/math] is the oriented Cayley graph of a given group [math]G[/math] precisely when it admits a simply transitive action of [math]G[/math].

Show Proof

This is something elementary, which is clear in one sense, from the proof of Proposition 12.11, and which in the other sense can be established as follows:

-- Given a graph [math]X[/math] as in the statement, pick an arbitrary vertex, and label it 1.

-- Then, label each vertex [math]v\in X[/math] by the unique [math]g\in G[/math] mapping [math]1\to v[/math].

-- Finally, define [math]S\subset G[/math] as being the set of labels [math]i[/math], such that [math]1\to i[/math].

Indeed, with these operations performed, it follows from definitions that what we get is a generating set for our group, [math]G= \lt S \gt [/math], satisfying the condition [math]1\notin S[/math], and the Cayley graph of [math]G= \lt S \gt [/math] follows to be the original graph [math]X[/math] itself, as desired.

■

Moving ahead, let us attempt now to further modify our Cayley graph formalism, as to have [math]G=G(X_G)[/math]. As a first observation, this is certainly possible, due to:

Theorem

Any finite group [math]G[/math] appears as [math]G=G(X_G)[/math], with [math]X_G[/math] being the complete oriented graph having [math]G[/math] as set of vertices, and with the edges being colored by

[[math]] d_{hk}=h^{-1}k [[/math]]

according to the usual colored graph conventions, with color set [math]C=G[/math].

Show Proof

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

We have [math]d_{gh,gk}=d_{hk}[/math], which gives an action [math]G\curvearrowright X_G[/math], and so an inclusion [math]G\subset G(X_G)[/math]. Conversely now, pick an arbitrary permutation [math]\sigma\in S_G[/math]. We have then:

[[math]] \begin{eqnarray*} \sigma\in G(X_G) &\implies&d_{\sigma(h)\sigma(k)}=d_{hk}\\ &\implies&\sigma(h)^{-1}\sigma(k)=h^{-1}k\\ &\implies&\sigma(1)^{-1}\sigma(k)=k\\ &\implies&\sigma(k)=\sigma(1)k\\ &\implies&\sigma\in G \end{eqnarray*} [[/math]]

Thus, the inclusion [math]G\subset G(X_G)[/math] is an equality, as desired.

■

Summarizing, we must add colors to our Cayley graph formalism, as follows:

Definition

Associated to any finite group [math]G= \lt S \gt [/math], with the generating set [math]S[/math] satisfying [math]1\notin S[/math], is its oriented colored Cayley graph, constructed as follows:

The vertices are the group elements [math]g\in G[/math].
Edges [math]g\to h[/math] are drawn when [math]h=gs[/math], with [math]s\in S[/math].
Such an edge [math]g\to h[/math] is colored by the element [math]s=g^{-1}h\in S[/math].

As before, this oriented colored Cayley graph is indeed a graph, because our assumption [math]1\notin S[/math] excludes the self-edges, [math]g\not\!\!-\,g[/math]. Observe also that in the case [math]S=S^{-1}[/math] each edge [math]g\to h[/math] has as companion edge [math]h\to g[/math], so in this case, up to replacing the pairs of edges [math]g\leftrightarrow h[/math] by usual edges [math]g=h[/math], we obtain an unoriented colored graph.

At the level of examples, the graph in Theorem 12.13 appears as in Definition 12.14, with generating set [math]S=G-\{1\}[/math]. Also, in relation with Proposition 12.2 and Proposition 12.9, and with the associated symmetry groups too, we have the following result:

Proposition

We have the following oriented colored Cayley graphs, each time with respect to the standard, minimal generating set:

For [math]\mathbb Z_N[/math] we obtain [math]C_N^o[/math], having symmetry group [math]\mathbb Z_N[/math].
For [math]\mathbb Z_2\times\mathbb Z_3[/math] we obtain the bicolored [math]P(C_3^o)[/math], with symmetry group [math]\mathbb Z_2\times\mathbb Z_3[/math].
For [math]\mathbb Z_2^N[/math] we obtain the [math]N[/math]-colored cube [math]\square_N[/math], having symmetry group [math]\mathbb Z_2^N[/math].

Show Proof

This basically comes from our previous computations, as follows:

(1) For the group [math]\mathbb Z_N= \lt 1 \gt [/math], written as usual additively, the number of colors is [math]|\{1\}|=1[/math], and so no colors, and the graph is the usual oriented cycle [math]C_N^o[/math], namely:

[[math]] \xymatrix@R=16pt@C=16pt{ &\bullet\ar[r]&\bullet\ar[dr]\\ \bullet\ar[ur]&&&\bullet\ar[d]\\ \bullet\ar[u]&&&\bullet\ar[dl]\\ &\bullet\ar[ul]&\bullet\ar[l]} [[/math]]

But, as we know well from the above, the symmetry group of this graph is [math]\mathbb Z_N[/math].

(2) For the group [math]\mathbb Z_2\times\mathbb Z_3= \lt (1,0),(0,1) \gt [/math], again written additively, we have 2 colors, and we obtain the bicolored version of the oriented prism [math]P(C_3^o)[/math], which is as follows:

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

But the symmetry group of this bicolored oriented prism is [math]\mathbb Z_2\times\mathbb Z_3[/math], as claimed.

(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, written as usual additively, here there is no true orientation, due to [math]1=-1[/math], but we have however [math]N[/math] colors, those of the generators. We are led in this way to the [math]N[/math]-colored version of the old hypercube graph [math]\square_N[/math], 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]]

But the symmetry group of this latter graph is [math]\mathbb Z_2^N[/math], as claimed.

■

All this is quite interesting, so let us generalize now the above results. In what regards the product operations, the result here, which is very standard, is as follows:

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 oriented colored Cayley graphs, we have the formula

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

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

Show Proof

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

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

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

■

As for the generalization of our symmetry group computations, this is as follows:

Theorem

Given a group [math]G= \lt S \gt [/math] with [math]1\notin S[/math], we have the formula

[[math]] G=G(X_G) [[/math]]

with [math]X_G[/math] being the corresponding oriented colored Cayley graph.

Show Proof

We use the same method as for Theorem 12.13, which corresponds to the case [math]S=G-\{1\}[/math]. The adjacency matrix of the graph [math]X_G[/math] in the statement is given by:

[[math]] d_{hk} =\begin{cases} h^{-1}k&{\rm if}\ h^{-1}k\in S\\ 0&{\rm otherwise} \end{cases} [[/math]]

Thus we have an action [math]G\curvearrowright X_G[/math], and so on inclusion [math]G\subset G(X_G)[/math]. Conversely now, pick an arbitrary permutation [math]\sigma\in S_G[/math]. We know that [math]\sigma[/math] must preserve all the color components of [math]d[/math], which are the following matrices, depending on a color [math]c\in S[/math]:

[[math]] d_{hk}^c =\begin{cases} 1&{\rm if}\ h^{-1}k=c\\ 0&{\rm otherwise} \end{cases} [[/math]]

In other words, we have the following equivalences:

[[math]] \begin{eqnarray*} \sigma\in G(X) &\iff&d^c_{\sigma(h)\sigma(k)}=d_{hk},\forall c\in S\\ &\iff&\sigma(h)^{-1}\sigma(k)=h^{-1}k,\forall h^{-1}k\in S \end{eqnarray*} [[/math]]

Now observe that with [math]h=1[/math] we obtain from this that we have:

[[math]] \begin{eqnarray*} k\in S &\implies&\sigma(1)^{-1}\sigma(k)=k\\ &\implies&\sigma(k)=\sigma(1)k \end{eqnarray*} [[/math]]

Next, by taking [math]h\in S[/math], we obtain from the above formula that we have:

[[math]] \begin{eqnarray*} k\in hS &\implies&\sigma(h)^{-1}\sigma(k)=h^{-1}k\\ &\implies&\sigma(k)=\sigma(h)h^{-1}k\\ &\implies&\sigma(k)=(\sigma(1)h)h^{-1}k\\ &\implies&\sigma(k)=\sigma(1)k \end{eqnarray*} [[/math]]

Thus with [math]g=\sigma(1)[/math] we have the following formula, for any [math]k\in S[/math]:

[[math]] \sigma(k)=gk [[/math]]

But the same method shows that this formula holds as well for any [math]k\in S^2[/math], then for any [math]k\in S^3[/math], any [math]k\in S^4[/math], and so on. Thus the above formula [math]\sigma(k)=gk[/math] holds for any [math]k\in G[/math], and so the inclusion [math]G\subset G(X_G)[/math] is an equality, as desired.

■

The above results are not the end of the story, but rather the beginning of it. Indeed, at a more advanced level, we have the following classical result, due to Frucht:

Theorem (Frucht)

Any finite group [math]G[/math] appears as the symmetry group

[[math]] G=G(X) [[/math]]

of a certain uncolored, unoriented graph [math]X[/math].

Show Proof

This is something quite tricky, the idea being as follows:

(1) We can start with the graph in Definition 12.8, namely the associated oriented Cayley graph [math]X_G[/math], with the convention that the edges [math]g\to h[/math] exist when:

[[math]] g^{-1}h\in S [[/math]]

(2) The point now is that we can make a suitable unoriented graph out of this graph, by replacing each edge with a copy of the following graph, with the height being in a chosen bijection with the corresponding element [math]g^{-1}h\in S[/math]:

[[math]] \xymatrix@R=20pt@C=30pt{ &&\circ\\ &\circ&\circ\ar@{-}[u]\\ \\ \circ_g\ar@{-}[r]&\circ\ar@{.}[uu]\ar@{-}[r]&\circ\ar@{.}[uu]\ar@{-}[r]&\circ_h} [[/math]]

(3) With these replacements made, and under suitable assumptions on the generating set [math]S[/math], namely the usual [math]1\notin S[/math] assumption, plus the fact that [math]S\cap S^{-1}[/math] must consist only of involutions, one can prove that [math]G[/math] appears indeed of the symmetry group of this graph [math]X[/math]. We will leave checking the details here as an instructive exercise.

■

General references

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