Collaborative Research: Extremal and Ramsey Problems for Graphs and Hypergraphs

点击翻译按钮获取中文摘要

Graphs and hypergraphs are mathematical structures that model relations among objects (for example, large networks) and appear in many applications. 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 is probabilistic reasoning, which has been crucial in the development of modern algorithms and the design of robust and efficient communication networks. The PIs plan to work on classical problems that belong to extremal graph and hypergraph theory. They will train undergraduate and graduate students as part of this project. A considerable part of the project will employ probabilistic reasoning, explicit constructions, and applications of the regularity method. Several problems considered by the PIs can be traced back to the work of Paul Erdos that has shaped these areas of discrete mathematics. In particular the PIs will work on Turan, Ramsey, and Dirac-type problems for graphs and hypergraphs.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.