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. *****