Algebraic Graph Theory and Erdos-Ko-Rado Theorems

点击翻译按钮获取中文摘要

***The focus of this research proposal is the famous Erdos-Ko-Rado (EKR) theorem. This theorem is at the centre of a very active field of research and is a cornerstone result in extremal set theory. It was originally proven in 1963, and since then there have been many generalizations, extensions and applications of the result. The EKR theorem is concerned with finding the largest collection of subsets so that any two intersect. With some conditions, the theorem states that the largest collection is formed by taking all sets that contain a common element. Part of the appeal of this theorem is that the result is so natural, the first collection that you would think of is actually the largest possible. ******Another aspect that makes this result the focus of so much research is that a version of the EKR theorem holds for many different objects other than sets. For example, there are versions of the theorem for vector spaces over a finite field, integer sequences, permutations, independent sets in a graph, domino tilings, and many other objects. In fact, for any object for which there is some notion of intersection, one can ask if a version of the EKR theorem holds. It is surprising how often the answer is yes. Part of my research program is to try to understand why this result holds in so many cases.******The place to start with such an inquiry is to look at the key components of the proofs of the EKR theorem. There are many different ways to prove the EKR theorem for sets---in fact the connections between this theorem and different areas of math is another reason it is such a famous result. Many of these proofs can be generalized for the variations of the EKR theorem for other objects. My favourite proof uses algebraic graph theory; this approach is effective since it manages to capture the global property of any two objects in the collection intersecting. It is also easy to see how to apply this algebraic approach to different objects. In fact, it gives a method to prove a version of the EKR theorem for many different objects; this method is particularly effective for objects that have some form of symmetry. ******In my research program I will consider EKR theorems for different objects. I will consider both objects with a high degree of symmetry and objects without symmetry as a way to more fully understand why variations of the EKR theorem hold. I believe the route to such results will be found by focusing on EKR theorems for permutation groups. My plan is to generalize proofs that use an algebraic graph theory approach. Often the symmetric objects for which the algebraic method is effective also have highly structured algebras defined on them. In these cases there are other generalizations of the EKR theorems which I plan on investigating, the goal being to understand both the EKR and related theorems better, and also the algebraic structure. The over-arching goal of my research program is to consolidate these results in a more unified EKR theorem using algebraic approaches. *****