• Login
    View Item 
    •   oURspace Home
    • Faculty of Graduate Studies and Research
    • Theses and Dissertations
    • Doctoral Theses and Dissertations
    • View Item
    •   oURspace Home
    • Faculty of Graduate Studies and Research
    • Theses and Dissertations
    • Doctoral Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Maximum Intersecting Families of Permutations

    Thumbnail
    View/Open
    Ahmadi_Bahman_200270398_PhD_MATH_Fall2013.pdf (842.6Kb)
    Date
    2013-07
    Author
    Ahmadi, Bahman
    Metadata
    Show full item record
    URI
    http://hdl.handle.net/10294/3835
    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.
    Collections
    • Doctoral Theses and Dissertations

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina

     

     

    Browse

    All of oURspaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    About

    About oURspacePoliciesLicensesContacts

    Statistics

    View Usage Statistics

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina