TJHSST Senior Research Project Investigation of Minimal Conjugate Generators for the Symmet.pdfVIP

TJHSST Senior Research Project Investigation of Minimal Conjugate Generators for the Symmetric Group and their Cayley Graphs 2007-2008 Jacob Steinhardt September 7, 2007 Abstract We investigate subsets of the symmetric group with structure similar to that of a graph. The “trees” of these subsets then lead to minimal highly symmetric generating sets of the symmetric group. We show that there exist generating sets among these with edge-transitive Cayley graphs and investigate them in relation to the Lovasz conjecture. Keywords: Cayley graph, Lovasz conjecture, Hamiltonian cycle, conjugate generators, sym- metric group, quasi-hamiltonicity. 1 Introduction - Purpose and Scope Note that a graph can be defined as a collection of vertices and edges. Two vertices are adjacent if there exists an edge connecting them, and two vertices v1 and v2 are connected if there exists a sequence of adjacent vertices containing v and v . On the other hand, consider the following 1 2 definition: Given a collection of vertices V and a collection of edges E , we can let each element of E act on V as a transposition swapping the two vertices on which E is incident. If we then let multiplication in E extend through the definitions of a group action, E generates a subgroup of the symmetric group acting on V (we denote this subgroup as E ). Then we say that v1 and v2 are adjacent if (v v ) ∈ E , and that v and v are connected if (v v ) ∈ E . Additionally, connected 1 2 1