05C50 Online Seminar: Karen Meagher

My research is centred around the famous Erdos-Ko-Rado (EKR) Theorem. I was first introduced to this theorem through an application in computer science, and later learned about its roots in pure mathematics. This is a research area that has grown so much recently that researchers have coined the term "Erdos-Ko-Rado Combinatorics" to describe the field. My talk will be a general introduction to this field, highlighting the different types of problems considered and their connections to different areas of math.

The original EKR Theorem is a problem in extremal set theory; it determines the largest collections of k-subsets from an n-set, with the property that any two of the subsets have non-empty intersection. The collection of all k-subsets that contain a fixed point is clearly an example of such a family (it is called a canonical intersecting family) and the EKR theorem states that it is the largest possible. One reason that the this theorem is so important is that it is a very natural and satisfying result! Further, there are many vastly different proofs of the result, and in recent year many extensions and generalizations have been considered.

One active direction is to show that a theorem analogous to the EKR holds for different objects. So consider any type of object with some notion of intersection, and ask what is the largest collection of objects so that any two from the collection have non-trivial intersection. A natural version of the EKR theorem is known to hold for set partitions, permutations, integer sequences, trees in a graph and many different geometries, just to name a few examples. A common proof method is to define a graph with the property that intersecting sets are exactly the cocliques (also called independent sets) in the graph. Then the problem becomes how to determine the largest cocliques in this graph. With this perspective, tools from linear algebra and algebraic graph theory can be applied and are surprisingly effective. Further, the adjacency matrices of these graphs often belong to a very structured matrix algebra and there can be patterns in the eigenvalues of these association scheme that can be used to find good, and often tight, bounds on the size of the cocliques.

Another direction in EKR combinatorics is to characterize all the largest intersecting sets. Typically, this is a much harder problem, but new and effective methods based on algebraic graph theory have been recently developed. This method considers a collection of Boolean functions defined on a subspace and leads to the study of related sets called Cameron-Liebler sets.

The focus of research has been on objects for which a version of the EKR theorem holds, but some recent work had looked for natural examples where the theorem does not hold. This work has focused on permutation groups, and trying to measure how far the group is to having the EKR theorem hold. There are also some examples where the EKR theorem is conjectured to hold, but the current methods are not effective.