Graph Theory and Additive Combinatorics

图论和加法组合学

• 批准号: 1764176
• 负责人: Yufei Zhao
• 金额: $ 18万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-07-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1764176&HistoricalAwards=false
• 关键词: Graph; Theory; Additive; Combinatorics

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.

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

项目成果

Cayley Graphs Without a Bounded Eigenbasis

没有有界本征基的凯莱图

• DOI: 10.1093/imrn/rnaa298
• 发表时间: 2020
• 期刊: International Mathematics Research Notices
• 影响因子: 1
• 作者: Sah, Ashwin;Sawhney, Mehtaab;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Triforce and corners

三角力和角点

• DOI: 10.1017/s0305004119000173
• 发表时间: 2020
• 期刊: Mathematical Proceedings of the Cambridge Philosophical Society
• 影响因子: 0.8
• 作者: FOX, JACOB;SAH, ASHWIN;SAWHNEY, MEHTAAB;STONER, DAVID;ZHAO, YUFEI
• 通讯作者: ZHAO, YUFEI

Induced arithmetic removal: complexity 1 patterns over finite fields

诱导算术去除：有限域上的复杂性 1 模式

• DOI: 10.1007/s11856-022-2290-x
• 发表时间: 2022
• 期刊: Israel Journal of Mathematics
• 影响因子: 1
• 作者: Fox, Jacob;Tidor, Jonathan;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Removal lemmas and approximate homomorphisms

移除引理和近似同态

• DOI: 10.1017/s0963548321000572
• 发表时间: 2022
• 期刊: Probability and Computing
• 作者: Fox, Jacob;Zhao, Yufei
• 通讯作者: Zhao, Yufei

Exponential improvements for superball packing upper bounds

• DOI: 10.1016/j.aim.2020.107056
• 发表时间: 2019-04
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: A. Sah;Mehtaab Sawhney;David Stoner;Yufei Zhao