Methods in Extremal Combinatorics

点击翻译按钮获取中文摘要

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.