Graph Theory and 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.