## Maximum Intersecting Families of Permutations

##### Abstract

In extremal set theory, the Erd}os-Ko-Rado (EKR) theorem gives an upper bound
on the size of intersecting k-subsets of the set {1; : : : ;n}. Furthemore, it classi es
the maximum-sized families of intersecting k-subsets. It has been shown that similar
theorems can be proved for other mathematical objects with a suitable notion of
\intersection". Let G B Sym(n) be a permutation group with its permutation action
on the set {1; : : : ;n}. The intersection for the elements of G is de ned as follows: two
permutations ; > G are intersecting if (i) = (i) for some i > {1; : : : ;n}. A subset
S of G is, then, intersecting if any pair of its elements is intersecting. We say G has
the EKR property if the size of any intersecting subset of G is bounded above by the
size of a point stabilizer in G. If, in addition, the only maximum-sized intersecting
subsets are the cosets of the point-stabilizers in G, then G is said to have the strict
EKR property. It was rst shown by Cameron and Ku [10] that the group G = Sym(n)
has the strict EKR property. Then Godsil and Meagher presented an entirely di erent
proof of this fact using some algebraic properties of the symmetric group. A similar method was employed to prove that the projective general linear group PGL(2; q),
with its natural action on the projective line Pq, has the strict EKR property. The
main objective in this thesis is to formally introduce this method, which we call the
module method, and show that this provides a standard way to prove Erd}os-Ko-Rado
theorems for other permutation groups. We then, along with proving Erd}os-Ko-Rado
theorems for various groups, use this method to prove some permutation groups
have the strict EKR property. We will also show that this method can be useful in
characterizing the maximum independent sets of some Cayley graphs. To explain
the module method, we need some facts from representation theory of groups, in
particular, the symmetric group. We will provide the reader with a su cient level of
background from representation theory as well as graph theory and linear algebraic
facts about graphs.