Collaborative Research: Extremal and Ramsey Problems for Graphs and Hypergraphs

协作研究：图和超图的极值问题和 Ramsey 问题

• 批准号: 2300347
• 负责人: Vojtech Rodl
• 金额: $ 18万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-15 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2300347&HistoricalAwards=false
• 关键词: Collaborative; Research; Extremal; Ramsey; Problems

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.

图和超图是对对象（例如大型网络）之间关系进行建模的数学结构，出现在许多应用中。这些结构的研究在数学、计算机科学和工程的各个分支中都有广泛的应用。因此，理解这些和其他相关的数学结构很重要。研究这些结构的技术之一是概率推理，它对于现代算法的开发和鲁棒高效的通信网络的设计至关重要。 PI 计划研究属于极值图和超图理论的经典问题。作为该项目的一部分，他们将培训本科生和研究生。该项目的相当一部分将采用概率推理、显式构造和正则性方法的应用。 PI 考虑的几个问题可以追溯到 Paul Erdos 的工作，他塑造了离散数学的这些领域。特别是，PI 将致力于图兰、拉姆齐和狄拉克类型的图和超图问题。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。