JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

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., D4 = ⟨r, f | r4 = f2 = (rf)2 = id⟩, ℤ x ℤ = ⟨a, b | ab = ba⟩, ℤ4⊕ ℤ2 = ⟨a, b | a4 = b2 = 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 cs.
  3. ∀g ∈ G and s ∈ S, there is a directed edge of color cs 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).

Image 

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

![Image](/maths/images/CayleyColor3.jpeg ./maths/images/CayleyColor2.jpeg ./maths/images/CayleyColor.jpeg)

Image 

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.

Image 

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.

Image 

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 → a2 →···→ am-1, where |a| = m, and there is an obvious Hamiltonian path for this Cayley diagraph.

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

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

We claim that (a1, a2,···, ak, s, a1, a2,···, ak, a1, a2,···, ak, s, a1, a2,···, ak, a1, a2,···, ak, s, a1, a2,···, ak, a1, a2,···, ak) where a1, a2,···, ak 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 = sn, H = ⟨s1, s2, …, sn-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, Hs2,…, Hsn 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 a1, a2,···, ak 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 a1, a2,···, ak 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 Hs2 and then the path a1, a2,···, ak to visit each element of this new coset exactly once.
  6. We repeat this algorithm and visit each coset, that is, Hs3, Hs4,…, Hsn and each element of each coset exactly once. Take into consideration that each vertex of Cay(S:G) is in exactly one coset Hsi (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

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.
  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.
Bitcoin donation

JustToThePoint Copyright © 2011 - 2024 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun. Social Issues, Join us.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.