Algebraic Graph Theory and Erdos-Ko-Rado Theorems

本研究计划的重点是著名的Erdos-Ko-Rado （EKR）定理。这个定理是一个非常活跃的研究领域的中心，是极值集合论的一个基石结果。它最初是在1963年被证明的，从那时起，这个结果得到了许多推广、扩展和应用。EKR定理关注的是找到最大的子集集合，使任意两个子集相交。在某些条件下，定理指出，最大集合是由包含一个公共元素的所有集合组成的。这个定理吸引人的部分原因是它的结果很自然，你能想到的第一个集合实际上是最大的。使这个结果成为众多研究焦点的另一个方面是，EKR定理的一个版本适用于许多不同的对象，而不是集合。例如，对于有限域上的向量空间、整数序列、置换、图中的独立集、多米诺骨牌平铺和许多其他对象，存在不同版本的定理。事实上，对于任何有交集概念的物体，我们都可以问EKR定理的一个版本是否成立。令人惊讶的是，答案往往是肯定的。我的研究计划的一部分是试图理解为什么这个结果在如此多的情况下成立。要进行这样的研究，首先要看一下EKR定理证明的关键组成部分。有许多不同的方法来证明集合的EKR定理——事实上，这个定理与不同数学领域之间的联系是它是一个如此著名的结果的另一个原因。这些证明中的许多可以推广到其他对象的EKR定理的变化。我最喜欢用代数图论证明；这种方法是有效的，因为它设法捕获集合中相交的任何两个对象的全局属性。也很容易看出如何将这种代数方法应用于不同的对象。事实上，它给出了一种方法来证明许多不同对象的EKR定理的一个版本；这种方法对于具有某种对称形式的对象特别有效。在我的研究计划中，我将考虑不同对象的EKR定理。我将考虑高度对称的物体和不对称的物体，以更充分地理解为什么EKR定理的变体成立。我相信，通过关注置换群的EKR定理，可以找到获得这些结果的途径。我的计划是推广使用代数图论方法的证明。通常在代数方法有效的对称对象上也定义了高度结构化的代数。在这些情况下，我计划研究EKR定理的其他推广，目标是更好地理解EKR和相关定理，以及代数结构。我的研究计划的首要目标是利用代数方法将这些结果整合到更统一的EKR定理中。

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.