Hypergraphs, Ramsey Theory and Extremal Combinatorics

超图、拉姆齐理论和极值组合

• 批准号: 1301698
• 负责人: Vojtech Rodl
• 金额: $ 28.51万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-06-01 至 2018-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1301698&HistoricalAwards=false
• 关键词: Hypergraphs; Ramsey; Theory; Extremal; Combinatorics

The proposed research concentrates mainly on problems in Ramsey theory and on extremal graph and hypergraph theory. Both of these areas belong to the mainstream of contemporary discrete mathematics and are often motivated by applications in other areas, such as theoretical computer science. In tackling these problems, a variety of combinatorial methods will be used, such as probabilistic methods and applications of regularity techniques. The PI also plans to develop new techniques leading to the construction of graphs with certain special properties. The Ramsey type problems suggested in the proposal include the investigation of the asymptotic behavior of hypergraph Ramsey numbers, of induced Ramsey numbers, of size-Ramsey numbers, as well of the Erdos-Rogers function. The PI also intends to study some problems in structural Ramsey theory. The extremal problems that the PI intends to investigate include Ramsey-Turán problems and the study of Hamilton cycles and matchings in hypergraphs, as well as extremal problems regarding random subsets of integers.This research will serve as a basis for the mentoring activities of the PI. Concepts and questions of combinatorial character appear naturally in other branches of mathematics and, more broadly speaking, in computer science and in the physical, biological, and social sciences, making combinatorial mathematics of interest not only within mathematics itself, but within the sciences as a whole.

建议的研究主要集中在拉姆齐理论和极值图和超图理论的问题。这两个领域都属于当代离散数学的主流，并且经常受到其他领域（如理论计算机科学）应用的启发。在解决这些问题时，将使用各种组合方法，如概率方法和正则性技术的应用。PI还计划开发新技术，以构建具有某些特殊性质的图。该提案中提出的Ramsey型问题包括超图Ramsey数、诱导Ramsey数、大小Ramsey数以及Erdos-Rogers函数的渐近行为的研究。PI还打算研究结构拉姆齐理论中的一些问题。PI打算研究的极值问题包括Ramsey-Turán问题和超图中的汉密尔顿圈和匹配的研究，以及整数随机子集的极值问题。这项研究将作为PI指导活动的基础。组合性质的概念和问题自然出现在数学的其他分支，更广泛地说，在计算机科学和物理，生物和社会科学中，使组合数学不仅在数学本身中，而且在整个科学中。