On the generating graphs of the symmetric and alternating groups

Erdem, Fuat
Dixon showed that the probability that a random pair of elements in the symmetric group $S_n$ generates $S_n$ or the alternating group $A_n$ tends to $1$ as $n to infty$. (A generalization of this result was given by Babai and Hayes.) The generating graph $Gamma(G)$ of a finite group $G$ is defined to be the simple graph on the set of non-identity elements of $G$ with the property that two elements are connected by and edge if and only if they generate $G$. The purpose of this thesis is to study the graphs $Gamma(S_n)$ and $Gamma(A_n)$. We prove that the graphs $Gamma(S_n)$ and $Gamma(A_n)$ contain Hamiltonian cycles provided that $n geq 107$. This improves a recent result of Breuer, Guralnick, Lucchini, Mar'oti and Nagy. Our result can be viewed as another step towards the conjecture of Breuer, Guralnick, Lucchini, Mar'oti and Nagy stating that for an arbitary finite group $G$ of order at least $4$ the generating graph $Gamma(G)$ contains a Hamiltonian cycle if and only if $G/N$ is cyclic for every non-trivial normal subgroup $N$ of $G$. (This is a stronger form of an older conjecture of Breuer, Guralnick and Kantor.) Our results may have applications to dimensions of fixed point spaces of elements of a finite group $G$ acting on a finite dimensional vector space $V$ with $C_{V}(G) = 0$.