Hypergraphs and Ramsey Theory

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

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.