Extensions of the Erdős-Ko-Rado Theorem to Perfect Matchings
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
One of the important results in extremal set theory is the Erdős-Ko-Rado (EKR) theorem which gives a tight upper bound on the size of intersecting sets. The focus of this thesis is on extensions of the EKR theorem to perfect matchings and uniform set partitions. Two perfect matchings are said to be t-intersecting if they have at least t edges in common. In 2017, Godsil and Meagher algebraically proved the EKR theorem for intersecting perfect matchings on the complete graph with 2k vertices. In 2017, Lindzey presented an asymptotic refinement of the EKR theorem on perfect matchings. In this thesis, we extend their results to 2-intersecting and also to set-wise 2-intersecting perfect matchings. These results are not asymptotic. A perfect matching is in fact a special case of a uniform set partition. Another focus of this thesis is on partially 2-intersecting uniform set partitions. We find the largest set of 2-intersecting uniform set partitions, when the number of parts is sufficiently large. The result on uniform set partitions is part of a joint research project with Karen Meagher and Brett Stevens.