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定理使用代数方法。