KAIST Discrete Math Seminar

The Erdos-Ko-Rado Theorem is a classic result about intersecting families of sets. More recently, analogous “EKR-type” type theorems have been developed for other types of objects. For example, non-trivially intersecting vector spaces, and overlapping strings. In this seminar we will give a proof of the EKR Theorem for permutations in S_n due to Godsil and Meagher. Along the way we will see some useful tools from algebraic graph theory. Namely, a bound on the maximum size of an independent set in a graph, equitable partitions, and eigenpolytopes.