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

Date
2010
Authors
Purdy, Alison May
Journal Title
Journal ISSN
Volume Title
Publisher
Faculty of Graduate Studies and Research, University of Regina
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.

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.
Keywords
Erdős-Ko-Rado Theorem
Citation
Collections