Login | Register

Designs with an Intersection Property inspired by the Erdos-Ko-Rado Problem.

Title:

Designs with an Intersection Property inspired by the Erdos-Ko-Rado Problem.

Loiselle, Mathieu (2015) Designs with an Intersection Property inspired by the Erdos-Ko-Rado Problem. Masters thesis, Concordia University.

[img]
Preview
Text (application/pdf)
Loiselle_MCompSc_S2016.pdf - Accepted Version
512kB

Abstract

Katona’s proof of the Erdos-Ko-Rado Theorem (EKR) relies on the existence of a family of v k-subsets of a set of size v with no subfamily of k+1 sets that are pairwise 1-intersecting. Herein, we consider a generalization of these families: collections of size λ {v \choose t}/{k \choose t} of k-subsets of a set of size v with no subcollection of λ+1 sets that are pairwise t-intersecting. Katona’s original family corresponds to the case t = 1 and λ = k. Replacing Katona’s family with such a collection in his proof constitutes a Katona-style proof of EKR for the parameters t, v, and k.
Any Steiner system is such a collection and any such collection is proven to be a t-design. Moreover, the Erdos-Ko-Rado theorem itself can be seen as the statement that for any t and k, and for a sufficiently large value of v, the set of all k-subsets of a set of size v is such a collection with λ ={v-t \choose k-t}. Proofs and analogs of the Erdos-Ko-Rado theorem have been topics of interest since its publication and the t-designs we identify have aspects of both. Each design proves a particular instance of EKR and satisfies a condition analogous to the conclusion of EKR. In honor of Katona’s proof, we have named these collections Katona sieves. The research questions addressed by this thesis are for what values of λ, given t, v, and k, does such a collection exist and which t-designs have this property.
We largely restricted our attention to 2-designs and developed programs for generating 2-(v,k,λ) designs, testing for the additional property that no subfamily of λ+1 subsets is 2-intersecting, that is, testing the condition for being a Katona sieve. For any choice of v, k, and λ, the number of blocks in the design, b, and the number of blocks containing a given element, r, are uniquely determined. Of the 142 case listed in the CRC Handbook for 2-designs with b ≤ 64 and r ≤ 21, existence or non-existence of a Katona sieve is established through theory for 92 cases. Of these the enumeration problem was also settled for by theory for 71 cases and settled by computation for 10 cases. Of the 50 cases for which the existence problem is not settled by theory, we resolve 17 more through computation, fully enumerating 14 of these cases. This leaves 33 cases with b ≤ 64 and r ≤ 21 for which existence is not determined and an additional 14 only partially enumerated.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science
Item Type:Thesis (Masters)
Authors:Loiselle, Mathieu
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:27 November 2015
Thesis Supervisor(s):Lam, Clement
ID Code:980711
Deposited By: MATHIEU LOISELLE
Deposited On:16 Jun 2016 14:43
Last Modified:18 Jan 2018 17:51
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top