Hypergraphs and Ramsey Theory

超图和拉姆齐理论

• 批准号: 2153576
• 负责人: Dhruv Mubayi
• 金额: $ 38万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-01 至 2026-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2153576&HistoricalAwards=false
• 关键词: Hypergraphs; Ramsey; Theory

The PI will develop the theory of families of finite sets, focusing on the relationship between local and global properties. Questions about the local/global relationships in large structures impact several areas of mathematics (number theory, combinatorics, logic) as well as other fields like information theory, coding theory, theoretical computer science, and the social sciences. The study of these objects has gained particular importance in recent years due to the many large real world networks that have emerged and are being studied. Developing new techniques to study these complex systems will be a major task for future researchers and the PI plans to contribute to this through his theoretical work. The PI plans to involve graduate students in this research.The PI will focus on two particular areas of combinatorics: Extremal hypergraph theory and Ramsey theory. In the first area, the main object to be explored is the "feasible region" of a hypergraph. This captures two of the most important themes in extremal combinatorics: shadow theorems exemplified by the Kruskal-Katona theorem, and extremal hypergraph problems exemplified by Turan's theorem and its various extensions to hypergraphs. The PI and his coauthors have developed the basic theory of feasible regions for both hypergraphs and induced graphs in a series of papers. Still, many foundational issues remain unresolved and settling these could be considered one of the main thrusts of this project. In the second area, the PI plans to work on fundamental problems in Ramsey theory. The main problems that will be explored here are the determination of the tower growth rates of diagonal and off-diagonal classical hypergraph Ramsey numbers, as well as of the closely related Erdos-Hajnal function. The PI will also try to obtain better bounds for off-diagonal graph Ramsey numbers using pseudorandom structures.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.

PI将发展有限集族理论，重点是局部和全局属性之间的关系。关于大型结构中局部/全局关系的问题影响数学的几个领域（数论，组合学，逻辑）以及其他领域，如信息论，编码理论，理论计算机科学和社会科学。近年来，由于出现了许多大型的真实的世界网络并正在进行研究，对这些对象的研究变得特别重要。开发研究这些复杂系统的新技术将是未来研究人员的主要任务，PI计划通过他的理论工作对此做出贡献。PI计划让研究生参与这项研究。PI将专注于组合学的两个特定领域：极值超图理论和拉姆齐理论。在第一个领域中，要探索的主要对象是超图的“可行域”。这抓住了极值组合学中两个最重要的主题：以克鲁斯卡尔-卡托纳定理为例的阴影定理，以及以图兰定理及其对超图的各种扩展为例的极值超图问题。PI和他的合著者在一系列论文中发展了超图和诱导图的可行域的基本理论。尽管如此，许多基本问题仍然没有得到解决，解决这些问题可以被认为是该项目的主要目标之一。 在第二个领域，PI计划研究拉姆齐理论中的基本问题。主要的问题，将在这里探讨的是确定的塔增长率的对角和非对角的经典超图Ramsey数，以及密切相关的埃尔多斯-Hajnal功能。PI还将尝试使用伪随机结构获得非对角图Ramsey数的更好边界。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

项目成果

Hypergraph Ramsey numbers of cliques versus stars

超图拉姆齐派系与明星的数量

• DOI: 10.1002/rsa.21155
• 发表时间: 2023
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Conlon, David;Fox, Jacob;He, Xiaoyu;Mubayi, Dhruv;Suk, Andrew;Verstraëte, Jacques
• 通讯作者: Verstraëte, Jacques