• 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.

    Variations on a Theorem of Erdös, Ko and Rado

    Thumbnail
    View/Open
    PURDY_Alison_184238837_PhD_MATH_Spring2014.pdf (629.7Kb)
    Date
    2014-09
    Author
    Purdy, Alison May
    Metadata
    Show full item record
    URI
    http://hdl.handle.net/10294/5807
    Abstract
    The Erdös-Ko-Rado theorem, a theorem which gives the size and structure of the largest pairwise intersecting collection of k-subsets from a base set of size n, has inspired many variations on the theme of the maximum size and structure of intersecting families. Some results for intersecting set systems add additional conditions or vary the intersection requirement. For instance, Hajnal and Rothschild allow up to s mutually disjoint sets. Hilton and Milner consider the largest families that do not have an element common to all of the k-subsets. Another variation is to consider objects other than subsets. For each object, a suitable de nition of intersection is required. In some instances, theorems with di erent de nitions of intersection have appeared for the same objects. In this thesis, we deal with two such objects: multisets and permutations. We de ne a k-multiset as a collection of k integers (not necessarily distinct) from a nite base set of cardinality m and say that two k-multisets are intersecting if they have an element in common. Our results include a theorem giving the size and structure of the largest intersecting families of multisets for all values of m and k. The proof of our theorem uses a graph theoretic approach. This approach is applied to give additional results including the largest family in which there is no common element in all of the multisets and the largest family in which up to s multisets are allowed to be pairwise not intersecting. For permutations, we consider two di erent de nitions of intersection that have been used in intersection theorems: t-intersection and t-cycle-intersection. We show that a previous result giving an exact lower bound on n relative to t above which the largest xed t-intersecting family of permutations is the pointwise stabilizer of t points can be used to give a similar result for all t-cycle-intersecting families. For t-cycleintersecting permutations, we prove several results that may be useful in proving the structure of the t-cycle-intersecting families which attain the maximum size for all values of n and t. For t-intersecting families, we give the size of the largest family with up to s permutations that are not pairwise intersecting and prove a number of results concerning unions of t-intersecting families where the cardinality of the union is as large as possible.
    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