LEAPS MPS: The Erdos-Ko-Rado Property of Well-Covered Graphs

LEAPS MPS：良好覆盖图的 Erdos-Ko-Rado 性质

• 批准号: 2213394
• 负责人: Jessica De Silva
• 金额: $ 24.93万
• 依托单位: California State University-Stanislaus
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-01 至 2024-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2213394&HistoricalAwards=false
• 关键词: LEAPS; MPS; Erdos; Ko; Rado

Many types of relations and processes, including physical and social systems, can be modeled using a graph. Graph models of such systems tend to be very large, requiring mathematical techniques that can extract global information from the graph at the smaller, local level. Extremal graph theory can be thought of as the study of how global properties of a graph influence its local structure. The aim of this project is to investigate questions in extremal graph theory, particularly those that relate to a well-known extremal set theory result called the Erdos-Ko-Rado theorem. Undergraduate student researchers at the PI’s Hispanic-serving institution will work in pairs to take on parts of this project. These students will have the opportunity to learn how to leverage their individual strengths while conducting cutting-edge research. Additionally, a colloquium series will be established within this project to connect students and faculty in the PI’s department to high-impact role models in the mathematical sciences.The Erdos-Ko-Rado (EKR) theorem is a pivotal result in extremal set theory that gives an upper bound on the number of sets of a fixed size that are pairwise intersecting. Of particular interest is the straightforward construction of an intersecting family that attains this bound by collecting all sets of the specified size that contain some fixed element. In 2005, Holroyd, Spencer, and Talbot formulated an EKR property for graphs related to intersecting families of independent sets. This property has a corresponding construction, called an r-star, that takes all independent sets of size r containing a fixed vertex of the graph. A graph is called r-EKR if the maximum size of an intersecting family of size r independent sets is equal to the size of the largest r-star in the graph. This project aims to study the r-EKR property, and related concepts, for certain classes of graphs.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

许多类型的关系和过程，包括物理系统和社会系统，都可以用图来建模。这类系统的图形模型往往非常大，需要能够在较小的局部级别从图形中提取全局信息的数学技术。极值图论可以被认为是研究一个图的全局性质如何影响其局部结构的。这个项目的目的是研究极值图论中的问题，特别是那些与一个著名的极值集合论结果有关的问题，称为Erdos-Ko-Rado定理。PI的拉美裔服务机构的本科生研究人员将结对工作，承担这一项目的一部分。这些学生将有机会学习如何在进行尖端研究的同时利用自己的个人优势。此外，在这个项目中还将建立一个系列讨论会，将PI系的学生和教员与数学科学中的高影响力榜样联系起来。Erdos-Ko-Rado(EKr)定理是极值集合论中的一个关键结果，它给出了固定大小的两两相交的集合的数量的上限。特别令人感兴趣的是，通过收集包含某些固定元素的指定大小的所有集合来直接构造达到此界限的相交族。2005年，Holroyd、Spencer和Talbot为与独立集族相交的图建立了一个EKR性质。这个性质有一个相应的结构，称为r-星，它取包含图的一个固定顶点的大小为r的所有独立集。一个图称为r-EKr，如果一个大小为r个独立集的交族的最大尺寸等于图中最大的r-星的尺寸。这个项目旨在研究某些类别的图表的r-EKr财产和相关概念。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。