Algebraic Graph Theory and Erdos-Ko-Rado Theorems

代数图论和 Erdos-Ko-Rado 定理

• 批准号: RGPIN-2018-03952
• 负责人: Meagher, Karen
• 金额: $ 1.46万
• 依托单位: University of Regina
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=759061
• 关键词: Algebraic; Graph; Theory; Erdos; Ko

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.

该研究建议的重点是著名的Erdos-Ko-Rado（EKR）定理。该定理是一个非常活跃的研究领域的中心，是极端集理论的基石结果。它最初在1963年被证明，从那时起，结果进行了许多概括，扩展和应用。 EKR定理关注的是找到最大的子集集合，以使任何两个相交。在某些条件下，定理指出，最大的集合是通过摄取所有包含一个共同元素的集合来形成的。该定理的一部分吸引力是结果是如此自然，您想到的第一个集合实际上是最大的。使这一结果重点的另一个方面是，EKR定理的一个版本适用于集合以外的许多不同对象。例如，在有限字段，整数序列，排列，图中的独立集，多米诺骨牌瓷砖和许多其他对象的矢量空间的定理版本。实际上，对于任何相交概念的对象，都可以询问EKR定理版本是否包含。令人惊讶的是答案是肯定的。我的研究计划的一部分是试图理解为什么在很多情况下这种结果成立。首先进行此类询问的地方是查看EKR定理证明的关键组成部分。有许多不同的方法可以证明EKR定理用于集合 - 实际上，该定理与数学不同领域之间的联系是它是如此著名的结果。这些证据中的许多可以推广到其他对象的EKR定理的变化。我最喜欢的证明使用代数图理论；这种方法是有效的，因为它设法捕获了集合中任意两个对象的全球属性。也很容易看到如何将这种代数方法应用于不同对象。实际上，它提供了一种证明许多不同对象的EKR定理版本的方法。该方法对于具有某种形式的对称的对象特别有效。在我的研究计划中，我将考虑针对不同对象的EKR定理。我将把两个具有高度对称性的对象和没有对称性的对象视为一种更充分理解ekr定理的变化的一种方式。我相信，通过关注排列组的EKR定理可以找到达到此类结果的途径。我的计划是概括使用代数图理论方法的证据。代数方法有效的对称对象通常也具有在其上定义的高度结构化代数。在这些情况下，我计划调查EKR定理的其他概括，目的是更好地了解EKR和相关定理，以及代数结构。我的研究计划的整个目标是使用代数方法以更统一的EKR定理巩固这些结果。