Extremal Combinatorics: Themes and Challenging Problems

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

• 批准号: 2246641
• 负责人: Fan Wei
• 金额: $ 21万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2023-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2246641&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将通过了解各种重要应用中的界限来提高我们对规则性方法的力量和限制的目标，以提高我们对规律方法的力量和限制的目标。另一个主要项目是确定使用概率方法的随机构造何时具有最佳或几乎最佳的界限。几个古典主题包括Sidorenko的猜想，Ramsey理论以及相关的问题。目的是通过研究几个密切相关和具体的问题来更好地理解这一总体方向，并对这些主题之间的联系有更多的见解。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛的评估来支持的。影响审查标准。