Associating Finite Groups with Cayley Color Graphs

We aim to introduce Cayley color graphs as powerful visualization tools for understanding groups geometrically. These graphs are constructed using a group and a generating set, and they provide insights into various group properties through the application of graph theoretical methods. We seek to establish a fundamental connection between groups and graphs by proving that finite groups are isomorphic to the group of color-preserving automorphisms of their corresponding Cayley color graphs. Exploiting this connection, we then delve into the investigation of specific properties upheld by the Cayley color graphs of Abelian groups.

1. Introduction

A Cayley color graph is an edge-colored directed graph that corresponds to a specific finite group and a chosen generating set (defined in Definition 2.1). Let $G$ be a finite group and $\Delta$ be a generating set of $G$. We denote $G$‘s Cayley color graph as $D_\Delta(G)$.

We define $D_\Delta(G)$ as follows:

1. The vertex set of $D_\Delta(G)$ is equal to $G$.
2. Each $a \in \Delta$ corresponds to an edge color $a$.
3. For distinct $g, h \in G$, $(g, h)$ is an edge if and only if for some $a \in \Delta$, $g^{-1}h = a$. This edge is colored $a$.

In this paper, we will prove that the group of color-preserving automorphisms (defined in Definition 2.5) of $D_\Delta(G)$ is isomorphic to $G$.

Main Theorem. Let $G$ be a finite group with generating set $\Delta$. The group of color-preserving automorphisms of $D_{\Delta}(G)$ is isomorphic to $G$.

Example 1.1 For example, we can consider the finite group $\mathbb{Z}_4 = \{0, 1, 2, 3\}$ with generating set $\Delta = \{2, 3\}$. The Cayley color graph $D_\Delta(\mathbb{Z}_4)$ is illustrated in Figure 1.

Figure 1. Cayley color graph of $\mathbb{Z}_4$ with generating set $\{2, 3\}$.

As illustrated in Figure 1, each pair of vertices associated by $2 \in \Delta$ is connected with a blue-dashed edge while each pair of vertices associated by $3 \in \Delta$ is connected with a red-solid edge. According to Theorem 1, the group of all color-preserving automorphisms of $D_\Delta(\mathbb{Z}_4)$ is isomorphic to $G$.

The idea of formulating a graphical representation of finite groups originated in an 1878 paper by Arthur Cayley [2]. Cayley set the foundations for graphically analyzing groups by defining a way to construct a graph from a finite group.

A few decades later in 1936, Dénes Kőnig posed a question that seeked to identify the cases in which a group is isomorphic to an automorphism group of a graph [5]. Two years later in 1938, Robert Frucht found a procedure to transform a Cayley color graph into an undirected graph by substituting each edge with a subgraph depending on the edge’s direction and color [3]. Effectively, Frucht encoded each edge’s direction and color with a simple undirected subgraph. Frucht then proved that the automorphic group of the resulting graph is isomorphic to the original finite group, hence answering Kőnig’s original question.

This paper is structured to prove the Main Theorem 1 and explore its applications. In doing so, we first cover the necessary background knowledge in Section 2. We define the necessary terminology to understand how to construct a Cayley color graph and some foundational lemmas surrounding color-preserving automorphisms. Then, we transition into proving the Main Theorem 1 in Section 3. In Section 4, we explore how the structure of Cayley color graphs reveal whether or not its underying group is Abelian. Finally, we explore potential future directions of Cayley color graphs in Section 5.

2. Background

This paper assumes familiarity with the fundamentals of group theory and isomorphisms as in [4, 3 and 6]. We will be extending these concepts to conform to graph theory, so we also assume knowledge of graphs and their basic properties as in [3, 1.1].

The structure of a constructed Cayley color graph is dependent on both the chosen finite group and a particular subset known as a generating set.

Definition 2.1. Let $G$ be a group and $\Delta \subseteq G$. $\Delta$ is a generating set if for each $g \in G$, we can write:

$$g = a_1a_2 \cdots a_n$$

where $a_i \in \Delta$. The $a_i$ are not necessarily distinct. Further, the elements in $\Delta$ are called generators.

We note that each finite group may potentially have multiple generating sets.

Example 2.2. Trivially, one possible generating set of $\mathbb{Z}_6$ is $\mathbb{Z}_6$ itself. Alternatively, we can consider $\Delta = \{2, 3\} \subset \mathbb{Z}_6$. We can show that each $g \in \mathbb{Z}_6$ can be expressed by elements in $\Delta$ under the group’s operation:

$$\begin{align*} 0 &= 2 + 2 + 2 + 2 \\ 1 &= 2 + 2 + 3 \\ 2 &= 2 \\ 3 &= 3 \\ 4 &= 2 + 2 \\ 5 &= 2 + 3 \end{align*}$$

Thus, we can conclude that $\Delta = \{2, 3\}$ is a generating set of $\mathbb{Z}_6$.

Similar to how we can create group automorphisms, we can also create isomorphisms from a graph to itself known as a graph automorphism.

Definition 2.3 [(3, 5.2)]. Let $G$ be a graph with vertex set $V_G$ and edge set $E_G$. A graph automorphism is a permutation $\sigma : V_G \rightarrow V_G$ such that $\forall u, v \in V_G$, $(u, v) \in E_G$ if and only if $(\sigma(u), \sigma(v)) \in E_G$.

Example 2.4. For example, we illustrate a graph automorphism in Figure 2.

Figure 2. Graph automorphism $\sigma$ permuting a graph.

Since graph automorphisms are permutations on a graph’s vertex set, we can express $\sigma$ in cycle notation (defined in [4, 5]):

$$\sigma = (18)(27)(35)(46).$$

We can observe that each pair of adjacent vertices in the original graph is adjacent in the permuted graph and each pair of nonadjacent vertices in the original graph is nonadjacent in the permuted graph.

When dealing with edge-colored graphs, we may also classify certain automorphisms as color-preserving. In edge-colored graphs, edges are designated a color as a way to differentiate edges from each other. With Cayley color graphs, it is important to preserve edge coloring in addition to adjacency and nonadjacency.

Definition 2.5. A color-preserving automorphism is a graph automorphism that additionally preserves edge color. More formally, let $G$ be a graph with edge set $E_G$. Let $\phi$ be a color-preserving automorphism. Then, $(u, v) \in E_G$ and $(\phi(u), \phi(v)) \in E_G$ have the same color.

Next, we can consider the color-preserving automorphisms of a Cayley color graph.

Lemma 2.6 ([3, 5.4]). Let $G$ be a finite group with a generating set $\Delta$ and let $\phi$ be a permutation on the vertex set of $D_\Delta(G)$. Then, $\phi$ is a color-preserving automorphism of $D_\Delta(G)$ if and only if

$$\phi(gh) = (\phi(g))h$$

for every $g \in G$ and $h \in \Delta$.

Lemma 2.7 ([3, 5]). Let $G$ be a finite group with generating set $\Delta$. Then, the set of all color-preserving automorphisms of $D_\Delta(G)$ forms a subgroup of $\text{Aut}(D_\Delta(G))$.

3. Main Theorem

After covering the essential background behind Cayley color graphs, we can now prove Theorem 1. We begin by proving that we can express the group of color-preserving automorphisms as the set of all permutations on $G$ by left multiplication. We then construct an isomorphism between the group of color-preserving automorphisms and the finite group.

Main Theorem. Let $G$ be a finite group with generating set $\Delta$. The group of color-preserving automorphisms of $D_{\Delta}(G)$ is isomorphic to $G$.

Proof. Firstly, let $G$ be a finite group of order $n$ such that:

$$G = \{g_1, \ldots, g_n\}$$

where $g_1$ denotes the identity of $G$. Furthermore, let $\Delta$ denote a generating set with respect to $G$ (as defined in Definition 2.1).

For each $g_i \in G$, we define the mapping $\phi_i : G \rightarrow G$ as follows:

$$g \mapsto g_ig.$$

We can prove that for each $g_i \in G$, the resulting $\phi_i$ is a permutation on $G$. To do so, we must prove that $\phi_i$ is both injective and surjective:

1. $\phi_i$ is injective: Let $g_j, g_k \in G$ be arbitrary elements such that $\phi_i(g_j) = \phi_i(g_k)$. It follows:

$$\begin{align*} &\implies g_ig_j = g_ig_k \\ &\implies (g_i^{-1})g_ig_j = (g_i^{-1})g_ig_k & \text{[group inverses]} \\ &\implies g_j = g_k. \end{align*}$$

Hence, for all $g_j, g_k \in G$, we have $\phi(g_j) = \phi(g_k) \implies g_j = g_k$. Thus, we can conclude that $\phi_i$ is injective. 2. $\phi_i$ is surjective: Let $g_j \in G$ be an arbitrary element. It follows using group associativity:

$$\begin{align*} \phi_i(g_i^{-1}g_j) &= g_i(g_i^{-1}g_j) = (g_ig_i^{-1})g_j = g_j. \end{align*}$$

Hence, for each $g_j \in G$, there exists some element in $G$ such that $\phi_i$ maps to $g_j$. Thus, $\phi_i$ is surjective.

Since $\phi_i$ is both injective and surjective, it can be viewed as a permutation on $G$. Additionally, since the vertex set of $D_\Delta(G)$ is equal to $G$ by construction, we can also view $\phi_i$ as a permutation on $G$‘s Cayley color graph.

We can prove that $\phi_i$ satisfies the property outlined in Lemma 2.6. Let $g \in G$ and $h \in \Delta$. It follows using group associativity:

$$\begin{align*} \phi_i(gh) &= g_i(gh) = (g_ig)h = (\phi_i(g))h. \end{align*}$$

Thus, $\phi_i$ is a color-preserving automorphism of $D_\Delta(G)$.

Next, we can prove that if $\phi$ is a color-preserving automorphism of $D_\Delta(G)$, then $\phi = \phi_i$ for some $i \in \{1, \ldots, n\}$. Suppose $\phi(g_1) = g_i$ and $g_s = h_1\cdots h_t \in G$ be arbitrary where $h_i \in \Delta$ (not necessarily distinct). We know we can express $g_s$ in this way because $\Delta$ is a generating set. It follows:

$$\begin{align*} \phi(g_s) &= \phi(g_1h_1\cdots h_t) \\ &= \phi(g_1h_1\cdots h_{t-1})h_t & \text{[Lemma 2.6]} \\ &= \phi(g_1h_1\cdots h_{t-2})h_{t-1}h_t & \text{[Lemma 2.6]} \\ &= \cdots \\ &= \phi(g_1)h_1\cdots h_t \\ &= g_ig_s. \end{align*}$$

Hence, if $\phi$ is a color-preserving automorphism of $D_\Delta(G)$, then $\phi$ is a permutation by left multiplication on $G$.

From these results, we express the set of all color-preserving automorphisms (we denote as $A$):

$$A = \{\phi_i \mid i \in \{1, \ldots, n\}\}.$$

In other words, the set of all color-preserving automorphisms of $D_\Delta(G)$ is equivalent to the set of all permutations on $G$ by left multiplication. By Lemma 2.7, we know $A$ is a group.

Next, we can establish an isomorphism between $G$ and $A$, the group of color-preserving automorphisms of $D_\Delta(G)$. Let $\psi : G \rightarrow A$ be a mapping defined as follows:

$$\psi(g_i) = \phi_i.$$

We proceed by proving that $\psi$ is an isomorphism:

1. $\psi$ is injective: Let $g_j, g_k \in G$ be arbitrary elements such that $\psi(g_j) = \psi(g_k)$. It follows:

$$\begin{align*} &\implies \phi_j = \phi_k \\ &\implies \phi_j(g_1) = \phi_k(g_1) & \text{[$g_1 \in G$ is identity]} \\ &\implies g_jg_1 = g_kg_1 \\ &\implies g_j = g_k. \end{align*}$$

Hence, for all $g_j, g_k \in G$, we have $\psi(g_j) = \psi(g_k) \implies g_j = g_k$. Thus, $\psi$ is injective. 2. $\psi$ is surjective: By construction of $A$ and definition of $\psi$, we note that $\psi$ is vacuously surjective. In particular, $\phi_i \in A$ is equivalent to $\psi(g_i)$ where $g_i \in G$. 3. $\psi$ is operation-preserving: Let $g_i, g_j \in G$ be arbitrary. We seek to prove $\psi(g_ig_j)$ is equal to $\psi(g_i)\psi(g_j)$. Suppose $g_ig_j = g_k \in G$. It follows:

$$\begin{align*} \psi(g_ig_j) &= \psi(g_k) = \phi_k &\psi(g_i)\psi(g_j) = \phi_i\phi_j. \end{align*}$$

Then, we can prove $\phi_k = \phi_i\phi_j$. Let $g \in G$ be arbitrary. It follows using group associativity:

$$\begin{align*} \phi_k(g) &= g_kg = (g_ig_j)g = g_i(g_jg) = \phi_i(g_jg) = \phi_i(\phi_j(g)). \end{align*}$$

Since for all $g \in G$ we have $\phi_k(g) = \phi_i(\phi_j(g))$, it follows that $\phi_k = \phi_i \phi_j$. Thus we have $\psi(g_ig_j) = \phi_k = \phi_i\phi_j = \psi(g_i)\psi(g_j)$, which means $\psi$ is operation-preserving.

Therefore, since $\psi$ is injective, surjective, and operation-preserving, we can conclude that $G$ is isomorphic to the group of color-preserving automorphisms of $D_\Delta(G)$.

To illustrate our Main Theorem, we now turn our attention to constructing a Cayley color graph from a finite group and identifying the color-preserving automorphisms in the following Example 3.1.

Example 3.1. We consider the group $\mathbb{Z}_6$ with generating set $\Delta = \{2, 3\}$. We associate each element of $\Delta$ with an edge color as follows:

• $2$: blue and dashed.
• $3$: red and solid. The Cayley color graph $D_\Delta(\mathbb{Z}_6)$ is illustrated in Figure 3.

Figure 3. Cayley color graph of $\mathbb{Z}_6$ with generating set $\{2, 3\}$.

The group of color-preserving automorphisms of $D_\Delta(\mathbb{Z}_6)$ would be $A = \{\phi_0, \phi_1, \phi_2, \phi_3, \phi_4, \phi_5\}$ where $\phi_g(x) = gx$ for $g, x \in \mathbb{Z}_6$. By Theorem 1, we know $A$ is isomorphic to $\mathbb{Z}_6$.

4. Cayley Color Graphs of Abelian Groups

Now that we have established an isomorphic connection between finite groups and the color-preserving automorphisms of their Cayley color graph, we can observe what these geometric representations reveal about groups. Specifically, we can look into the structure of Cayley color graphs of Abelian groups.

Since each element of a group can be written as a product of generators, it is trivial to show that if the generators commute then the group is Abelian. Thus, this motivates Lemma 4.1.

Lemma 4.1. Let $G$ be a group and $\Delta$ a generating set of $G$. If the elements in $\Delta$ pairwise commute, then $G$ is an Abelian group.

If the elements in $\Delta$ pairwise commute, it holds that for for all $a, b \in \Delta$, $ab = ba$. This implies that $aba^{-1}b^{-1} = e$ where $e$ is the identity. We can think of the edges in a Cayley color graph as applying a generator onto some element. Thus, if the underlying group of a Cayley color graph is Abelian, it holds that for two distinct colors $a_1$ and $a_2$, the path $a_1, a_2, a_1^{-1}, a_2^{-1}$ (where the inverse of a color is interpreted as following the edge in its reverse direction) should start and end at the same vertex [1, 5.2.1]. We can use an original example to illustrate this concept more clearly.

Original Example. We consider the symmetric group $S_3 = \{e, (12), (23), (13), (123), (132)\}$ where $e$ is the identity and the rest of the elements are written in cycle notation as in [4, 5]. Since every permutation in $S_3$ can be written as a product of $2$-cycles ([4, 5.4]), we know $\Delta = \{(12), (23), (13)\}$ is a generating set. We assign each generator in $\Delta$ with the following edge colors:

• $(12)$: blue and dashed.
• $(23)$: white and dotted.
• $(13)$: red and solid.

The resulting Cayley color graph $D_\Delta(S_3)$ is illustrated in Figure 4.

Figure 4. Cayley color graph of $S_3$ with generating set $\{(12), (23), (13)\}$.

From Figure 4 we observe that if we pick two colors, $a_1$ and $a_2$, and follow the path $a_1$, $a_2$, $a_1^{-1}$, $a_2^{-1}$, the starting vertex is distinct from the ending vertex. For example, we pick two colors $a_1$ and $a_2$ represented by the generators $(12)$ and $(23)$ respectively. Starting from vertex $e$ (chosen arbitrarily) results in the graph traversal illustrated in Figure 5.

Figure 5. Non-Abelian path traversal of a Cayley color graph.

Figure 5 highlights that applying $(12)$, $(23)$, $(12)^{-1}$, then $(23)^{-1}$ does not return us back to the same element, which means there exists generators that do not pairwise commute. Consequently, we can conclude that $S_3$ is non-Abelian.

5. Future Directions

Cayley color graphs allow us to view groups from a different perspective; providing us the ability to distinguish group properties with graph theoretical methods. Section 4 covered how the structure of Cayley color graphs can reveal whether or not its underlying group is Abelian, but we can also consider other group properties which motivates the following question.

Question 5.1. What other group properties do Cayley color graphs reveal and in what graph theoretical ways can we determine them? In particular, how can we characterize cyclic groups, dihedral groups, and symmetric groups by their Cayley color graphs?

Furthermore, Frucht’s theorem utilizes Cayley color graphs to prove that every group is isomorphic to an automorphism group of simple connected graphs in the finite case. However, this raises the question whether the same can be said in the infinite case.

Question 5.2. Is every infinite group isomorphic to an automorphism group of a simple connected graph?

References

[1] N. C. Carter. Visual group theory. Classroom resource materials. Mathematical Association of America, Washington, D.C., 2009.

[2] P. Cayley. Desiderata and suggestions: No. 2. the theory of groups: Graphical representation. American Journal of Mathematics, 1(2):174–176, 1878.

[3] G. Chartrand, L. Lesniak, and P. Zhang. Graphs & digraphs. Chapman and Hall/CRC, Boca Raton, FL, 5th ed edition, 2011.

[4] J. A. Gallian. Contemporary abstract algebra. Brooks/Cole, Cengage Learning, Belmont, CA, 7th ed edition, 2010.

[5] N. A. Nemirovskaya. Frucht theorem for inverse semigroups. Mathematical Notes, 61(2):201–205, Feb 1997.