On Regularity Methods and Applications in Graph Theory

论图论中的正则方法及其应用

• 批准号: 1953958
• 负责人: Fan Wei
• 金额: $ 15万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1953958&HistoricalAwards=false
• 关键词: Regularity; Methods; Applications; Graph; Theory

This mathematics research project centers on the area of graph theory, an active area of combinatorics that has made great strides in recent years because of its connection to other areas of mathematics and theoretical computer science. Many tools developed in modern combinatorics, such as the regularity methods, the probabilistic method, and algebraic methods, turn out to be also useful in understanding questions in other areas of mathematics such as number theory and information theory. This project considers several fundamental questions in combinatorics related to graph theory. It is expected that progress on these questions will lead to new methods that will have impact not only in mathematics but also in computer science, with important practical applications.The topics explored in this project are among the central questions in combinatorics. One goal is to improve understanding of the power and limitation of the regularity method through understanding the bounds in several important applications. Another goal 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 Turan numbers of bipartite graphs. The investigator will use and further develop multiple techniques to tackle these problems, including regularity methods such as Szemeredi's regularity lemma and weak regularity lemmas, and analytic tools such as graph limits and random processes.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.

该数学研究项目集中在图理论领域，这是一个组合学的活跃领域，近年来由于它与其他数学和理论计算机科学领域的联系而取得了长足的进步。现代组合学中开发的许多工具，例如规则性方法，概率方法和代数方法，也可用于理解数学其他领域（例如数字理论和信息理论）的问题。该项目考虑了与图理论有关的几个基本问​​题。预计这些问题的进展将导致新方法不仅在数学中，而且在计算机科学以及重要的实践应用中都会影响。一个目标是通过理解几种重要应用中的界限来提高对规则方法的力量和限制的理解。另一个目标是确定使用概率方法的随机构造何时具有最佳或几乎最佳的边界。几个古典主题包括Sidorenko的猜想，Ramsey理论和两分图的Turan数字。调查人员将使用并进一步开发多种技术来解决这些问题，包括诸如Szemeredi的规律性引理和弱规则性引理等规律性方法，以及诸如图形限制和随机过程之类的分析工具。该奖项反映了NSF的法定任务，并被认为是值得的。通过基金会的智力优点和更广泛的影响评估标准通过评估来支持。