Hypergraphs and Ramsey Theory

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

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.