Sequence of elements representing a Hamiltonian cycle and the generating element of a subgroup

Let $$S$$ be a subset of a finite group $$G$$. The Cayley graph $$Cay(G,S)$$ can be defined as the graph whose vertices are the elements of $$G$$, with an edge joining $$g$$ and $$gs$$, for every $$g \in G$$ and $$s \in S$$.

For $$s_1,s_2,\cdots,s_n \in S \cup S^{-1}$$, $$(s_1,s_2, \cdots, s_n)$$ is used to denote a walk in $$Cay(G,S)$$ that visits (in order) the vertices, $$e, s_1, s_1 s_2, \cdots, s_1 s_2 s_3 \cdots s_n$$.

Lemma: Suppose,

1. $$S$$ is a generating set of $$G$$,

2. $$H$$ is a cyclic subgroup of $$G$$, with index $$|G:H|=n$$,

3. $$s_1,s_2,\cdots,s_n$$ is a sequence of $$n$$ elements of $$S \cup S^{-1}$$ such that,

i) the elements $$e, s_1, s_1 s_2, \cdots, s_1 s_2 s_3 \cdots s_n$$ are all in different right cosets of $$H$$,

ii) the product $$s_1 s_2 \cdots s_n$$ is a generator of $$H$$.

Then, $$(s_1, s_2, \cdots , s_n)^{|H|}$$ is a Hamiltonian cycle in $$Cay(G,S)$$.

In this lemma, what is the importance of having $$s_1 s_2 \cdots s_n$$ as a generator of $$H$$?

I have seen other lemmas and theorems too where similar condition that such a product should be a generating element of some subgroup is mentioned. But I'm unable to see why?

Also, suppose a case where $$S=\{u,t\}$$. Then a Hamiltonian cycle in a Cayley graph with respect to $$S$$ will be expressed in terms of $$u,t$$. Then, if the Hamiltonian cycle is $$(u,t,t^{-1},t, \cdots, t)^{|H|}$$, I thought probably the above definition of notations mean to take $$s_1=s, s_2=t, s_3=t^{-1}, s_4=t, \cdots, s_n=t$$ since they have not mentioned that $$s_1, s_2, s_3, \cdots, s_n$$ are distinct elements. Am I right?.

Can some one help me with the above questions.

Thanks a lot in advance.

1 Answer

In the walk $$(s_1, s_2, \dots , s_n)^{|H|}$$, we visit $$H$$ every $$n$$ elements, so after $$n|H|$$ steps, the elements of $$H$$ we see are exactly $$(s_1 s_2 \cdots s_n)^k$$ for $$0 \le k \le |H|-1$$. If $$s_1 s_2 \cdots s_n$$ does not generate $$H$$, then we won't get a Hamiltonian cycle, because we won't visit all the different elements of $$H$$.

And yes, it's fine for some of the elements $$s_1, s_2, \dots, s_n$$ to coincide in the definition of $$(s_1, s_2, \dots, s_n)$$.

• Thank you very much @MishaLavrov it is clear to me now. Commented Mar 22, 2021 at 3:37