Cayley Graphs of Symmetric Groups

From CanisiusmathWiki

link to page with a Mathematica program: Some topical pages here

Table of contents

1 Abstract

2 Generators of the Symmetric Group

[edit]

Abstract

A permutation is an arrangement of n objects such that order matters. The collection of all permutations of length n forms the symmetric group $S_n$ . Composition of permutations generates a subgroup of $S_n$ , which can be represented graphically using Cayley graphs. This research deals with cases when two permutations generate $S_n$ .

[edit]

Generators of the Symmetric Group $S_n$

Given two permutations, A and B, with $A=(a_1, a_2, ... , a_n) , B=(b_1, b_2, ... , b_n)$ , we can obtain a new permutation $C=(c_1, c_2, ... , c_n)$ such that $c_m=b_{a_m}$ .

With respect to the composition of two permutations, the identity element $e\inS_n$ is $(1,2,...,n$ . Because permutations form cycles, m turns through a cycle of length m returns the permutation to its original ordering. If the starting point is something other than the origin, the identity element, taking a permutation of order m through m turns returns the permutation to the starting point rather than the origin. We can say for any permutation of order m, $m^m=1$ .

[edit]

$S_1$ and $S_2$

In all cases, the identity element replicates its left or right multiplier under the composition of permutations. Thus, except for the case of $S_1$ , which only contains the identity element, it is useless to consider the identity element as a potential generator of $S_n$ .

$S_1$ contains exactly one element, $(1)$ . This is the identity element, and it always generates itself.

$S_2$ contains exactly two elements, $(1,2)$ and $(2,1)$ . $(2,1)$ is of order 2, so it generates both itself and the identity element. Because there are only two elements in $S_2$ , this means $(2,1)$ generates the entirety of $S_2$ , so we do not require a second generator for $S_2$ .

Because $S_1$ and $S_2$ require only one generator, we only are interested in $S_n$ such that $n\geq 3$ .

[edit]

$S_3$

$S_3$ is composed of three types of elements. The identity is $(0,1,2)$ , which is the type $(1+1+1)$ . The elements $(0,2,1)$ , $(1,0,2)$ , and $(2,1,0)$ are of type $(2+1)$ . The elements $(1,2,0)$ and $(2,0,1)$ are of type $(3)$ . An element's type describes the size of the blocks in its composition. Here, type $(1+1+1)$ has three blocks of length 1, type $(2+1)$ has one block of length 2 and one block of length 1, and type $(3)$ has one block of length 3.

In order to generate the $S_3$ , we require at least two elements. Elements of type $(3)$ generate three elements, and elements of type $(2+1)$ generate two elements. Therefore, we cannot generate $S_3$ using only one element. Thus, there are three cases to consider for potential generators of $S_3$ .

1. $x,y\in(2+1)$ 2. $x\in(2+1) , y\in(3)$ 3. $x,y\in(3)$

Case 1: 1. $x=(a b)(c) , y=(a b)(c)$ 2. $x=(a b)(c) , y=(a c)(b)$ 3. $x=(a b)(c) , y=(b c)(a)$

Suppose $x=(a b)(c) , y=(a b)(c)$ . This indicates that in both x and y, the first and second letters of the identity permutation are reordered. Because this transformation switches only two letters, it is of order 2, and there are $2!=2$ ways to arrange 2 letters. Because these letters of x and y must have a different arrangement from the letters in the identity element, according to the pigeonhole principle, the letters must be arranged the same way in x and y. Likewise, the notation $(c)$ indicates that one letter of the permutation remains constant between the three permutations.

In the case of $S_3$ , the two elements of type $(3)$ generate each other, so it is impossible for the two elements of type $(3)$ to generate $S_3$ . Using brute force, I found that an element of type $(2+1)$ and any other element except $(0,1,2)$ will generate $S_3$ .

[edit]

Observations

1. Using elements $(0,1,3,2)$ and $(0,2,3,1)$ , which are, respectively, types $(2+1+1)$ and $(3+1)$ , we generate a set containing 6 elements.

2. Using elements $(1,0,3,2)$ and $(3,0,1,2)$ , which are, respectively, types $(2+2)$ and $(3+1)$ , we generate a set containing 12 elements. The same happens with $[x=(1,0,3,2) , y=(0,2,3,1)] , [x=(2,3,0,1) , y=(2,0,3,1)]$ , and $[x=(3,2,1,) , y=(3,0,1,2)]$ .

3. Using elements $(0,2,3,1)$ and $(1,2,3,0)$ , which are, respectively, types $(3+1)$ and $(4)$ , we generate the entirety of $S_4$ .

4. Using elements $(2,1,0,3)$ and $(2,0,3,1)$ , which are, respectively, types $(2+1+1)$ and $(4)$ , we generate the entirety of $S_4$ .

5. Using elements $(2,3,0,1)$ and $(1,2,3,0)$ , which are, respectively, types $(2+2)$ and $(4)$ , we generate 4 elements. Using elements $(1,2,3,0)$ and $(3,0,1,2)$ , which are both type $(4)$ , we generate the same 4 elements. This is because both $(1,2,3,0)$ and $(3,0,1,2)$ can generate the 4 elements of the group without a second generator.

6. The elements of type $(2+2)$ are $(1,0,3,2)$ , $(2,3,0,1)$ , and $(3,2,1,0)$ . Any two of these will generate exactly four elements. These four elements are: the two elements themselves, the third element of type $(2+2)$ , and the identity element. Thus, the elements of type $(2+2)$ are isomorphic to the Klein Four Group.

7. Some $x\in(2+1+1) , y\in(4)$ generate $S_4$ , but others of this type only generate 8 elements.

8. It is not the case that $x\in(n) , y\in(n-1)$ always generate $S_n$ . However, this does not become apparent until $S_5$ . Given $x=(2,3,4,5,1) , y=(4,3,1,2,5)$ , x and y generate $S_5$ . However, given $x=(2,3,4,5,1) , y=(3,1,4,2,5)$ , x and y generate only 20 elements of $S_5$ .

[edit]

Conjectures

Note: Assume $x\neq{y} \hskip0.1in \forall {x,y}$ .

1. Given $x\in(2+1+1)$ and $y\in(2+1+1)$ , x and y generate at least 3 elements. x and y generate exactly 3 elements when the undisturbed letters in x are the block of length 2 in y and vice versa. If one of the undisturbed letters remains undisturbed between x and y, then x and y generate 6 elements.

2. Given $x\in(2+1+1)$ and $y\in(3+1)$ , x and y generate at least 6 elements. x and y will generate exactly 6 elements if and only if the undisturbed letter in y is one of the undisturbed letters in x. Otherwise, x and y will generate 12 or 24 elements.

3. Given $x\in(2+2)$ and $y\in(3+1)$ , x and y generate exactly 12 elements. Because $(2+2)$ and $(3+1)$ are sets of even size, we know that x and y cannot generate more than half of $S_4$ . From observation 2, we know that $x\in(2+2)$ and $y\in(3+1)$ can generate 12 elements. However, because there are no undisturbed letters common to x and y, I conjecture that it must be the case that x and y generate more than 6 elements. Because the Symmetric Group operates using powers of 2, I hypothesize that by disturbing an additional letter in x, the number of elements generated by x and y is doubled.

4. Given $x,y\in(3+1)$ such that the undisturbed element is not the same between x and y, x and y generate exactly 12 elements. Because $(3+1)$ is a group of even size, we know that x and y generate at most half of $S_4$ . Because x and y disturb all 4 letters of the permutation, I hypothesize that x and y generate 12 elements. Whenever x and y have a common undisturbed letter, it is impossible for x and y to generate more than 6 elements because there are $(n-1)!$ elements with any given undisturbed letter in $S_n$ .

5. Given $x\in(3+1)$ and $y\in(4)$ , x and y generate $S_4$ .

6. Given permutations $x,y\in S_n$ such that every letter is disturbed by x or y with exactly one letter disturbed by both x and y, x and y will generate $S_n$ if $x=(x_1\hskip0.05in x_2)(x_2\hskip0.05in x_3)...(x_{k-1}\hskip0.05in x_k) , y=(y_1\hskip0.05in y_2)(y_2\hskip0.05in y_3)...(y_{m-1}\hskip0.05in y_m)$ such that at least one of x and y contains an odd number of inversions.

The proof of this is inspired by the textbook example that $(1\hskip0.05in 2)(2\hskip0.05in 3)...(n-1\hskip0.05in n)$ generate $S_n$ .

[edit]

Conclusions

Note: Assume $x\neq{y} \hskip0.1in \forall {x,y}$ .

1. 1. If $x,y\in S_n$ share m undisturbed letters, they generate at most a set isomorphic to $S_{n-m}$ .

Proof: Omit the undisturbed letters and relabel the other letters. Note that the letters must be undisturbed between both generators and the identity element, not just between one generator and the identity element or between the two generators but not the identity element. If $k$ is an undisturbed letter, relabel each $k+i$ term ( $i>0$ ) to be $k+i-1$ . Repeat this for any additional undisturbed letters such that this algorithm is repeated $m$ times, once for each of the $m$ undisturbed letters. After this process is complete, each permutation will contain $n-m$ letters. Thus, after performing the algorithm, we have $x,y \in S_{n-m}$ . Because of this, x and y cannot generate more elements than are present in $S_{n-m}$ .

2. It is known that there are a total of $(a-1)+(b-1)+(c-1)+...+(\alpha -1)+(\beta -1)+(\gamma -1)+...$ inversions given $x\in(a+b+c+...) , y\in(\alpha +\beta +\gamma +...)$ with $x,y\in S_n$ . I conclude that if x and y have a combined total of $n-2$ or fewer inversions, they cannot generate $S_n$ .

Proof: Draw a graph with one vertex for each letter in a permutation in $S_n$ . Treat permutations as mappings, and draw an edge between two letters that are mapped into each other, leaving off the last edge in each cycle. Stop once you have drawn $n-2$ edges. In every case, there is a disconnected graph. If no path exists which connects two vertices, then it is impossible to generate a permutation in which these two vertices are reversed from their original order. Thus, it is impossible to generate the entirety of a symmetric group of order n because it is impossible to generate at least one of the elements contained in that group.

3. 6. Given $x\in(4)$ and $y\in(2+2)$ , x and y generate either 4 or 8 elements. x and y generate 4 elements if and only if y generates x. Otherwise, x and y generate 8 elements.