Extremal and Ramsey-Type Problems for Graphs and Hypergraphs

图和超图的极值问题和 Ramsey 型问题

基本信息

批准号：
1764385
负责人：
Vojtech Rodl
金额：
$ 35万
依托单位：
Emory University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-05-01 至 2024-04-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1764385&HistoricalAwards=false
关键词：
Extremal Ramsey Type Problems Graphs

项目摘要

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.

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