Extremal Combinatorics: Themes and Challenging Problems

极值组合学：主题和挑战性问题

• 批准号: 2401414
• 负责人: Fan Wei
• 金额: $ 21万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-10-15 至 2028-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2401414&HistoricalAwards=false
• 关键词: Extremal; Combinatorics; Themes; Challenging; Problems

Combinatorics is a fundamental area of mathematics. This project mainly concerns the area of graph theory, an active area of combinatorics which has been booming in recent years because of its connection to other areas of mathematics and theoretical computer science. Many graph theory problems also have practical motivations. Most of the world can be represented as large networks consisting of nodes and the connections between certain pairs of them. For example, a social network such as Facebook has over 2 billion users as nodes and friendship relations as connections; a biological network like the brain has over 100 billion neurons as nodes and synapses as connections. Understanding those networks and designing fast algorithms on them provides much practical value, examples include understanding how news spreads in a social network, understanding brain functions or diseases and improving artificial neural networks for machine learning applications. This project considers several fundamental questions in extremal graph theory. The project also provides training opportunities for graduate and undergraduate students.There are multiple techniques the PI plans to use and further develop, including regularity methods such as Szemeredi's regularity lemma and weak regularity lemmas; analytic tools such as graph limits, random processes and entropy methods; and various other combinatorial tools. The first project is related to Szemeredi's regularity lemma, which is an extremely powerful tool in modern graph theory which spurred a dramatic change of how we view and study graphs. It is a major direction of research to study which applications of the regularity lemma have considerably better bounds. The PI will work on several classical questions where the goal is to improve our understanding of the power and limitation of the regularity method through understanding the bounds in various important applications. Another major project is to determine when random constructions using the probabilistic method give optimal or nearly optimal bounds. Several classical topics include Sidorenko's conjecture, Ramsey theory, and related questions in graph limits. The goal is to better understand this general direction through studying several closely related and concrete problems and gain more insight on the connections between these topics.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.

组合学是数学的基础领域。该项目主要涉及图论领域，这是组合数学的一个活跃领域，近年来由于其与数学和理论计算机科学其他领域的联系而蓬勃发展。许多图论问题也有实际动机。世界上的大部分区域都可以表示为由节点以及某些节点之间的连接组成的大型网络。例如，Facebook这样的社交网络有超过20亿用户作为节点，好友关系作为连接；像大脑这样的生物网络有超过 1000 亿个神经元作为节点，突触作为连接。了解这些网络并在其上设计快速算法提供了很多实用价值，例如了解新闻如何在社交网络中传播、了解大脑功能或疾病以及改进机器学习应用的人工神经网络。该项目考虑极值图论中的几个基本问​​题。该项目还为研究生和本科生提供培训机会。PI 计划使用和进一步开发多种技术，包括正则性方法，如 Szemeredi 正则性引理和弱正则性引理；分析工具，例如图极限、随机过程和熵方法；以及各种其他组合工具。第一个项目与 Szemeredi 的正则引理有关，它是现代图论中极其强大的工具，它极大地改变了我们看待和研究图的方式。研究正则引理的哪些应用具有更好的界限是一个主要的研究方向。 PI 将致力于解决几个经典问题，其目标是通过了解各种重要应用的界限来提高我们对正则性方法的威力和局限性的理解。另一个主要项目是确定使用概率方法的随机构造何时给出最佳或接近最佳边界。几个经典主题包括西多连科猜想、拉姆齐理论以及图极限中的相关问题。目标是通过研究几个密切相关的具体问题来更好地理解这一总体方向，并更深入地了解这些主题之间的联系。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的评估进行评估，认为值得支持。影响审查标准。