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.