Graph Theory and Additive Combinatorics

该奖项支持PI在构建数学工具以解决图论和加性组合问题以及更好地理解这两个学科之间的联系方面的研究。图论涉及分析抽象网络的数学技术，特别是与计算机科学应用相关的非常大的网络。加性组合学关注的是数字集合中的结构，比如质数。以前的基础工作，包括PI所做的一些工作，已经表明，来自其中一个领域的工具和见解可以帮助解决另一个领域的问题。PI将继续证明进一步建立这两个学科之间联系的结果。这个项目的第一个主题是关于szemeracimdi定理的扩展和变化。szemeracimdi定理是组合学的一个基础结果，它指出具有正密度的整数子集必须包含任意长的等差数列。围绕szemersamedi定理的发展导致了图论中重要而强大的工具，如szemersamedi的正则引理，以及加性组合学中的概念，如Gowers均匀范数和高阶傅立叶分析。这个项目的一个主要目标是扩展szemersamedi定理，包括理解多项式和多维推广、流行差异以及其他设置（如排列）中的变体。第二个主题涉及离散随机结构中的大偏差。PI将开发工具来理解随机图中子图计数的尾部分布，以及随机集中某些算术模式的计数。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This award supports the PI's research in building mathematical tools to solve problems in graph theory and additive combinatorics, and to better understand the connections between these two subjects. Graph theory concerns mathematical techniques for analyzing abstract networks, especially very large networks that are relevant for applications in computer science. Additive combinatorics concerns structures in sets of numbers, such as the prime numbers. Previous foundational work, including some done by the PI, has shown that tools and insights from one of these areas can be helpful in solving problems in the other. The PI will continue to prove results that further build the connections between these two subjects. The first topic of this project concerns extensions and variations of Szemerédi's theorem. Szemerédi's theorem is a cornerstone result in combinatorics, stating that subsets of integers with positive density must contain arbitrarily long arithmetic progressions. Developments around Szemerédi's theorem have led to important and powerful tools in graph theory such as Szemerédi's regularity lemma, as well as concepts in additive combinatorics such as Gowers uniformity norms and higher order Fourier analysis. A major goal of this project is to extend Szemerédi's theorem, including understanding polynomial and multidimensional generalizations, popular differences, and variants inside other settings such as permutations. The second topic concerns large deviations in discrete random structures. The PI will develop tools for understanding tail distributions of subgraph counts in random graphs as well as counts of certain arithmetic patterns in a random set.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.