Extremal and Ramsey-Type Problems for Graphs and Hypergraphs

图和超图是对对象之间的关系进行建模的数学结构，例如社会中的友谊关系。对这些结构的研究在数学、计算机科学和工程学的各个分支中都有许多应用。因此，理解这些和其他相关的数学结构是重要的。研究这些结构的技术之一，概率推理，在现代算法的发展和鲁棒，高效和经济的通信网络的设计中至关重要。概率推理在离散数学中的另一个应用是基于这样一个事实，即人们可以将确定性对象分解为与随机生成的对象共享许多属性的片段。这种通用方法是由E. Szemeredi在过去的几十年中得到了推广和丰富，现在是研究大型图和超图的中心方法之一。PI计划研究图和超图的Turan-，Dirac-和Ramsey-型问题。PI提议的研究中有相当一部分将采用上述方法。一个主要的例子是图兰密度的研究。大多数其他问题也属于超图理论，并集中在拉姆齐理论和极值组合学的问题。这里考虑的几个问题可以追溯到经典研究的保罗·鄂尔多斯，他的工作，以及许多问题，塑造了离散数学的这些分支。这个奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

Graphs and hypergraphs are mathematical structures that model relations among objects, such as the friendship relation in a society. The study of these structures has numerous applications in various branches of mathematics, computer science and engineering. Consequently, understanding these and other related mathematical structures is important. One of the techniques in the study of these structures, probabilistic reasoning, has been crucial in the development of modern algorithms and the design of robust, efficient, and economical communication networks. Another application of probabilistic reasoning in discrete mathematics is based on the fact that one can decompose deterministic objects into pieces that share many properties with randomly generated objects. This general approach, pioneered by E. Szemeredi, has been generalized and enriched in the last couple of decades, and is now one of the central methods in the investigation of large graphs and hypergraphs.The PI plans to work on Turan-, Dirac-, and Ramsey-type questions for graphs and hypergraphs. A considerable part of the research proposed by the PI will employ, among others, the methodology mentioned above. A prime example is the investigation of Turan densities. Most of the other problems also fall within the theory of hypergraphs and are focused on questions in Ramsey theory and extremal combinatorics. Several of the problems considered here can be traced back to classical research of Paul Erdos, whose work, as well as many problems, shaped these branches of discrete mathematics.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.