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

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.