SFU Discrete Math Seminar: Karen Meagher

The first half of this talk will be a gentle introduction to the Erdős–Ko–Rado (EKR) Theorem. This is a theorem that determines the size and structure of the largest collection of intersecting sets. It has become a cornerstone of extremal set theory and has been extended to many other objects. I will show how this result can be proven using techniques from algebraic graph theory.

In the second half of this talk I will give more details about extensions of the EKR theorem to permutations. Two permutations are intersecting if they both map some i to the same point (so σ and π are intersecting if and only if σ−1π has a fixed point). In 1977, Deza and Frankl proved that the size of a set of intersecting permutations is at most (n-1)!. It wasn't until 2003 that the structure of sets of intersecting permutations that meet this bound was determined.

For any group action, we can ask what is the size and structure of the largest set of intersecting permutations. I will show some recent results for different groups, with a focus on 2-transitive groups.