Cayley Diagraphs. Hamiltonian paths.

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⁴ = ⟨r, f | r⁴ = f² = (rf)² = id⟩, ℤ x ℤ = ⟨a, b | ab = ba⟩, ℤ₄⊕ ℤ₂ = ⟨a, b | a⁴ = b² = 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:

1. Each element g ∈ G is a vertex of τ(G, S) or Cay(S:G).
2. Each element s ∈ S is assigned a color c_s.
3. ∀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:

1. 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.
2. If an element s of S is its own inverse (s = s^-1), then it is typically represented by an undirected edge.

Examples

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): ℤ₃⊕ℤ₂}) 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,

1. We begin at (0, 0) and move across the first row to the end by using the generator (0, 1).
2. Use the generator (1, 0) to move vertically to the vertex below.
3. Use the generator (0, 1) to move horizontally and cover the remaining points in the second row.
4. 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.
5. Move vertically to the second “k” block by using the generator (1, 0), and repeat the process explained above for the first block.
6. Keep and repeat until the last “k” block is covered.
7. 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² →···→ a^m-1, where |a| = m, and there is an obvious Hamiltonian path for this Cayley diagraph.

Let’s |S| > 1, S = {s₁, s₂, …, 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₁, s₂, …, s_n-1⟩

|T| < |S| and H is a finite Abelian group ⇒ [By the induction hypothesis] ∃(a₁, a₂,···, a_k) a Hamiltonian path in Cay(T:H)

We claim that (a₁, a₂,···, a_k, s, a₁, a₂,···, a_k, a₁, a₂,···, a_k, s, a₁, a₂,···, a_k, a₁, a₂,···, a_k, s, a₁, a₂,···, a_k, a₁, a₂,···, a_k) where a₁, a₂,···, 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₁, s₂, …, 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²,…, Hsⁿ where n = |G|/|H| - 1.

1. We start from the identity element of G.
2. We know by the induction hypothesis that the path given by a₁, a₂,···, a_k visits each element of H exactly one.
3. Next, we use the generator s to move us to some element of the coset Hs.
4. Starting from that element, the path given by a₁, a₂,···, a_k visits each element of the coset Hs exactly once.
5. Then, we repeat the previous process by using s to move us to the next coset Hs² and then the path a₁, a₂,···, a_k to visit each element of this new coset exactly once.
6. We repeat this algorithm and visit each coset, that is, Hs³, Hs⁴,…, Hsⁿ and each element of each coset exactly once. Take into consideration that each vertex of Cay(S:G) is in exactly one coset Hsⁱ (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 ∎

Bibliography

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