Methods in Extremal Combinatorics

PI将研究组合学中的基本问题。以前对这些问题的研究已经导致了广泛的应用和强大的方法的发展，这些方法已经在数学和计算机科学的许多分支中使用。例如，开发了概率方法来估计拉姆齐数，并对理论计算机科学产生了巨大的影响，例如随机算法的设计。另一个例子是，正则性方法引出了著名的素数等差数列格林-陶定理。预计对这些问题的进一步研究将带来新的方法和应用。PI将专注于使用和进一步发展解决极值组合问题的方法。这些技术的例子有正则性方法、多项式方法、相关随机选择和嵌入技术。该项目的第一个重点领域涉及Szemeredi的正则方法。在这个领域内，这个项目的主要目标之一是获得三角形去除引理及其变体的新边界。这个项目的第二个重点是估算拉姆齐数。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The PI will study fundamental problems in combinatorics. Previous work on these problems has led to a wide range of applications and the development of powerful methods which have been used in many branches of mathematics and computer science. For example, probabilistic methods were developed to estimate Ramsey numbers and have had a tremendous influence on theoretical computer science, such as in the design of randomized algorithms. As another example, the regularity method led to the celebrated Green-Tao theorem on arithmetic progressions in primes. It is expected that further work on these problems will lead to new methods and applications.The PI will focus on using and further developing methods to solve problems in extremal combinatorics. Examples of these techniques are the regularity method, the polynomial method, dependent random choice, and embedding techniques. The first area of focus in this project concerns Szemeredi's regularity method. Within this area, one of the main goals of this project is to obtain new bounds on the triangle removal lemma and its variants. The second area of focus in this project is estimating Ramsey numbers.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.