On Regularity Methods and Applications in Graph Theory

这个数学研究项目以图论领域为中心，图论是组合学的一个活跃领域，由于它与数学和理论计算机科学的其他领域的联系，近年来取得了巨大的进步。在现代组合学中开发的许多工具，如正则方法、概率方法和代数方法，在理解其他数学领域（如数论和信息论）的问题时也很有用。这个项目考虑了与图论相关的组合学中的几个基本问题。预计这些问题的进展将导致新的方法，不仅对数学，而且对计算机科学产生影响，具有重要的实际应用。本项目探讨的主题是组合学的核心问题之一。一个目标是通过理解几个重要应用中的边界来提高对正则性方法的能力和局限性的理解。另一个目标是确定使用概率方法的随机结构何时给出最优或接近最优边界。几个经典的主题包括西多连科猜想，拉姆齐理论和二部图的图兰数。研究者将使用并进一步开发多种技术来解决这些问题，包括正则方法，如Szemeredi的正则引理和弱正则引理，以及分析工具，如图极限和随机过程。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.