Do one thing every day that scares you, Eleanor Roosevelt.

A presentation is one method of specifying a group. It comprises a set of generators S (elements that we want to generate the group) and a set of relations or equations R among those generators, we then say G has presentation ⟨S | R⟩, e.g., D^{4} = ⟨r, f | r^{4} = f^{2} = (rf)^{2} = id⟩, ℤ x ℤ = ⟨a, b | ab = ba⟩, ℤ_{4}⊕ ℤ_{2} = ⟨a, b | a^{4} = b^{2} = e and ab = ba⟩

A graph, G, is a pair (V, E) where V is a set and E is a set of 2-element subsets of V . The set V is almost always finite and its elements are called vertices.

Definition. Let G be a group and S be a generating set of G. The Cayley graph, written as τ(G, S) or Cay(S:G), is an edge-colored (it assigns a color to each edge) directed graph (a graph that is made up of a set of vertices connected by directed edges called arcs) constructed as follows:

- Each element g ∈ G is a vertex of τ(G, S) or Cay(S:G).
- Each element s ∈ S is assigned a color c
_{s}. - ∀g ∈ G and s ∈ S, there is a directed edge of color c
_{s}from the vertex corresponding to g to the one corresponding to gs.

It provides a way to visualizing a group. They clearly communicate the group’s structure and complexity (or lack thereof).

Facts:

- There are several ways to draw the Cayley graph, also know as a Cayley color graph, Cayley diagram, or color group of a group given by a particular generating set.
- If an element s of S is its own inverse (s = s
^{-1}), then it is typically represented by an undirected edge.

A Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once without returning to the starting point. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once.

There can be more than one Hamiltonian path in a single graph but the graph must be connected to have the possibility of the existence of a Hamiltonian path.

- Example. Cay({(1, 0), (0, 1): ℤ
_{3}⊕ℤ_{2}}) Figure 01.

We want to research the existence of Hamiltonian circuits in Cay({(1, 0), (0, 1): ℤ_{m}⊕ℤ_{n}}) where m, n > 1 and gcd(m, n) = 1 (Figure 100).

If there is a Hamiltonian circuit and (a, b) is a vertex from which the circuit exists horizontally, then, it immediately follows, the circuit must exist (a -1, b +1) horizontally, too because otherwise the circuit would pass through (a, b + 1) twice (Figure 11). Then, repeating this argument, the circuit exists horizontally from each of the vertices (a, b), (a-1, b +1)(a -2, b +2),….that is, the coset (a, b) + ⟨(-1, 1)⟩. Futhermore, gcd(m, n) = 1 ⇒ ⟨(-1, 1)⟩ = ℤ_{m}⊕ℤ_{n} (that is, (-1, 1) generates the entire group). However, this is a contradiction because there cannot be a Hamiltonian circuit consisting entirely and exclusively of horizontal moves.

Theorem. Cay({(1, 0), (0, 1): ℤ_{m}⊕ℤ_{n}}) does not have a Hamiltonian circuitwhen m, n > 1 and gcd(m, n) = 1.

Theorem. Cay({(1, 0), (0, 1): ℤ_{m}⊕ℤ_{n}}) has a Hamiltonian circuit when n divides m.

Proof.

n divides m ⇒ ∃k ∈ ℤ: m = kn, then we may think of ℤ_{m}⊕ℤ_{n} as k blocks of size n x n (Figure 100). The Hamiltonian circuit is given as follows,

- We begin at (0, 0) and move across the first row to the end by using the generator (0, 1).
- Use the generator (1, 0) to move vertically to the vertex below.
- Use the generator (0, 1) to move horizontally and cover the remaining points in the second row.
- Iterate this process up until the point (n-1, 0), that is, the lower left-hand corner of the first block, is reached by the Hamiltonian circuit.
- Move vertically to the second “k” block by using the generator (1, 0), and repeat the process explained above for the first block.
- Keep and repeat until the last “k” block is covered.
- Complete the circuit by moving back vertically to square one by using (0, 1), so we may reach the first, starting vertex (0, 0).

Let k ∈ ℤ, k * (a, b, c, ···) denotes the concatenation of k copies of the sequence (a, b, c, ···). Thus, this proof can be expressed as m * [(n - 1) * (0, 1), (1, 0)]

Theorem. Let G be a finite Abelian group and S any non-empty generating set for G. Then, the Cayley diagraph of G, Cay(S:G), has a Hamiltonian path.

Proof.

Let’s induct on the order of the generating set for G, |S|.

Base case. |S|=1, that is, S = ⟨a⟩, then the digraph is just a circle labeled with e → a → a^{2} →···→ a^{m-1}, where |a| = m, and there is an obvious Hamiltonian path for this Cayley diagraph.

Let’s |S| > 1, S = {s_{1}, s_{2}, …, s_{n-1}, s_{n}} and pick some arbitrary element s. Without losing any generality, let’s take the last element, s_{n} = s ∈ S, and define T = S - {s}, H = ⟨s_{1}, s_{2}, …, s_{n-1}⟩

|T| < |S| and H is a finite Abelian group ⇒ [By the induction hypothesis] ∃(a_{1}, a_{2},···, a_{k}) a Hamiltonian path in Cay(T:H)

We claim that (a_{1}, a_{2},···, a_{k}, s, a_{1}, a_{2},···, a_{k}, a_{1}, a_{2},···, a_{k}, s, a_{1}, a_{2},···, a_{k}, a_{1}, a_{2},···, a_{k}, s, a_{1}, a_{2},···, a_{k}, a_{1}, a_{2},···, a_{k}) where a_{1}, a_{2},···, a_{k} occurs |G|/|H| times and s appears |G|/|H| -1 times is indeed a Hamiltonian path.

By assumption S generates G, T = S - {s}, s = s_{n}, H = ⟨s_{1}, s_{2}, …, s_{n-1}⟩ ⇒[If group G is Abelian and H ≤ G, the quotient group G/H is a group] the coset Hs generates the factor group G/H. Thus, the cosets of H are H, Hs, Hs^{2},…, Hs^{n} where n = |G|/|H| - 1.

- We start from the identity element of G.
- We know by the induction hypothesis that the path given by a
_{1}, a_{2},···, a_{k}visits each element of H exactly one. - Next, we use the generator s to move us to some element of the coset Hs.
- Starting from that element, the path given by a
_{1}, a_{2},···, a_{k}visits each element of the coset Hs exactly once. - Then, we repeat the previous process by using s to move us to the next coset Hs
^{2}and then the path a_{1}, a_{2},···, a_{k}to visit each element of this new coset exactly once. - We repeat this algorithm and visit each coset, that is, Hs
^{3}, Hs^{4},…, Hs^{n}and each element of each coset exactly once. Take into consideration that each vertex of Cay(S:G) is in exactly one coset Hs^{i}(it is a well-know fact that the set of cosets form a partition in G) ⇒ we visit each vertex of Cay(S:G) exactly once and we have a Hamiltonian path ∎

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.

- NPTEL-NOC IITM, Introduction to Galois Theory.
- Algebra, Second Edition, by Michael Artin.
- LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
- Field and Galois Theory, by Patrick Morandi. Springer.
- Michael Penn (Abstract Algebra), and MathMajor.
- Contemporary Abstract Algebra, Joseph, A. Gallian.
- Andrew Misseldine: College Algebra and Abstract Algebra.