The Erdős-Ko-Rado Theorem for intersecting families of permutations.

DSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Meagher, Karen
dc.contributor.author Purdy, Alison May
dc.date.accessioned 2012-08-13T19:56:49Z
dc.date.available 2012-08-13T19:56:49Z
dc.date.issued 2010
dc.identifier.uri http://hdl.handle.net/10294/3509
dc.description A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master's of Science, University of Regina. vi, 103 l. en_US
dc.description.abstract The Erdős-Ko-Rado Theorem is a fundamental result in extremal set theory. It describes the size and structure of the largest collection of subsets of size k from a set of size n having the property that any two subsets have at least t elements in common. Following the publication of the original theorem in 1961, many different proofs and extensions have appeared, culminating in the publication of the Complete Erdős-Ko-Rado Theorem by Ahlswede and Khachatrian in 1997. A number of similar results for families of permutations have appeared. These include proofs of the size and structure of the largest family of permutations having the property that any two permutations in the family agree on at least one element of the underlying set. In this thesis we apply techniques used in the proof of the Complete Erdős-Ko-Rado Theorem for set systems to prove a result for certain families of t-intersecting permutations. Specifically, we give the size and structure of a fixed t-intersecting family of permutations provided that n ≥2t + 1 and show that this lower bound on n is optimal. en_US
dc.language.iso en en_US
dc.publisher Faculty of Graduate Studies and Research, University of Regina en_US
dc.subject Erdős-Ko-Rado Theorem en_US
dc.subject.lcsh Permutations
dc.subject.lcsh Set theory
dc.subject.lcsh Extremal problems (Mathematics)
dc.title The Erdős-Ko-Rado Theorem for intersecting families of permutations. en_US
dc.type Thesis en
dc.description.authorstatus Student en
dc.description.peerreview yes en
thesis.degree.name Master of Science (MSc) en_US
thesis.degree.level Master's en
thesis.degree.discipline Mathematics en_US
thesis.degree.grantor University of Regina en
thesis.degree.department Department of Mathematics and Statistics en_US
dc.contributor.committeemember Fallat, Shaun
dc.contributor.externalexaminer Zilles, Sandra
dc.identifier.tcnumber TC-SRU-3509
dc.identifier.thesisurl http://ourspace.uregina.ca/bitstream/handle/10294/3509/Alison_Purdy_MSC_Math_2010.pdf


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search oURspace


Browse

My Account

About