Algebraic Graph Theory Seminar - Karen Meagher

Monday, June 27, 2022 11:30 am - 11:30 am EDT (GMT -04:00)

Title: A Brief Introduction to World of Erd\H{o}s-Ko-Rado Theorems

Speaker: Karen Meagher
Affiliation: University of Regina
Zoom: Please contact Sabrina Lato for Zoom link

Abstract:   The Erd\H{o}s-Ko-Rado (EKR) theorem is a famous result that is one of the cornerstones of extremal set theory. This theorem answers the question "What is the largest family of intersecting sets, of a fixed size, from a base set?"

This result has been the starting point for a whole field of study. For example, this question may be asked for any type of object for which there is some notion of intersection or difference. There natural versions of the EKR theorem for permutations, vector spaces, designs, partial geometries, integer sequences, domino tilings, partitions, matchings and many other objects. There are also many related questions about the largest sets with additional restrictions.

There are many vastly different proofs of these results, some are simple straight-forward counting arguments, others use graph theory and some require nuanced properties of related matrix algebra. I will show some of the different proof methods for EKR theorems, with a focus on the best method, which is of course, the algebraic method.