Given that $G = \langle a, b\rangle$ and that $a$ is an involution, when is it the case that there exists $c, d$ such that $G =
\langle c, d\rangle$ and $cd$ is an involution?
At present, I am reviewing the following paper by I. Pak and R. Radoičić (2009), to include their main result in my undergraduate dissertation (which is a survey on the Hamiltonicity of Cayley graphs and digraphs). This result is stated as follows:
Theorem 1 Every finite group $G$ of size $|G| \geq 3$ has a generating set $S$ of size $|S| \leq \log_2 |G|$, such that the corresponding Cayley graph $\Gamma(G, S)$ contains a Hamiltonian cycle.
The proof relies on a further theorem given in the paper, which I shall also state. Firstly, note that $r(G)$ and $m(G)$ denote that number of Abelian and non-Abelian composition factors of $G$.
Theorem 2 Let $G$ be a finite group, and let $r(G)$ and $m(G)$ be as above. Then there exists a generating set $S$, $\langle S \rangle = G$, with $|S| \leq r(G) + 2m(G)$, such that the corresponding Cayley graph $\Gamma(G, S)$ contains a Hamiltonian cycle.
While I do understand the way with which Theorem 1 follows from Theorem 2, the proof for Theorem 2 is not clear to me. Firstly, it is worth noting that the proof relies on consequences of the Classification of Finite Simple Groups; namely that "every non-Abelian finite simple group can be generated by two elements, one of which is an involution".
No reference is given in the paper to a proof of the aforementioned remark. I have however found the following paper by C. S. H. King (2016), in which the author proves that, indeed, every non-Abelian finite simple group is generated by an involution and an element of prime order. Of course, given the survey nature of the dissertation (and that it is at undergraduate level), this result will be simply stated. However, the aim is to clarify for non-expert readers the proofs given by Pak and Radoičić in [1], and I think stating this reference [2] will help do so.
The second result that comes into play in the proof of Theorem 2 is one given by R. A. Rankin (1966), which I shall state in full below ('Lemma 3' refers to the numbering in [1] and not in [3]).
Lemma 3 Let $G$ be a finite group, generated by two elements $\alpha$ and $\beta$, such that $(\alpha\beta)^2 = 1$. Then the Cayley graph $\Gamma = \Gamma(G, \{\alpha, \beta\})$ contains a Hamiltonian cycle.
In other words, note that the product of the generators above is an involution. In the proof for Theorem 2, the authors invoke the use of Lemma 3 as follows:
It is a well known consequence from the classification of finite simple groups, that every non-Abelian finite simple group can be generated by two elements, one of which is an involution. Therefore Lemma 3 is applicable, and for every non-Abelian finite simple group produces a generating set $S$, with $|S| = 2$, such that the corresponding Cayley graph contains a Hamiltonian cycle.
Finally, I can state my question in full: Lemma 3 requires that the product of the generators to be an involution, however we are only given that one of the generators is an involution; is the product necessarily an involution then? How exactly is Lemma 3 invoked?
Many thanks for your time and for reading this far! 🙂
Best Answer
If $a$ and $b$ are elements of $G$ such that $G=\langle a,b\rangle$, and $c=ab$, then $$G=\langle a,b\rangle=\langle a,c\rangle=\langle b,c\rangle.$$ Thus one can choose any two of $a$, $b$ and $ab$ to be a generating set.