Extremal and Ramsey-Type Problems for Graphs and Hypergraphs

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

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.