טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentReiter Asael
SubjectRandomly Generating the Symmetric Group, by Word Maps
DepartmentDepartment of Mathematics
Supervisors Dr. Chen Meiri
Dr. Danny Neftin


Abstract

It is known, for the past half century, that two random permutations almost surely generate the symmetric group Sn or the alternating group An. However, little is known about the same question, when we replace random permutations with random substitutions in word maps. For example, what is the group generated by x and yxy, when x and y are independent random permutations ?


In this work, we consider the images of random substitutions in a general set of word maps. Using Stallings core graphs, and some ideas from graph theory and combinatorics, we explain how it can be analyzed. The main result of this paper is that the generated group, in this setup, is almost surely transitive. This is an improvement of previous results, that had only shown that this group does not have any fixed point .


Our method can be slightly generalized. Unfortunately, this generalization is not enough to show that the generated group is almost surely An or Sn, but we manage to show that it does not preserve any partition of the set {1,2,?,n}  into a small number of parts. Combining this result with existing results about the structure of a random permutation, we can show that in several special cases, the generated group is indeed (almost surely) An or Sn .