On Regularity Methods and Applications in Graph Theory

Princeton University, Princeton NJ

Investigators

Abstract

This mathematics research project centers on the area of graph theory, an active area of combinatorics that has made great strides in recent years because of its connection to other areas of mathematics and theoretical computer science. Many tools developed in modern combinatorics, such as the regularity methods, the probabilistic method, and algebraic methods, turn out to be also useful in understanding questions in other areas of mathematics such as number theory and information theory. This project considers several fundamental questions in combinatorics related to graph theory. It is expected that progress on these questions will lead to new methods that will have impact not only in mathematics but also in computer science, with important practical applications. The topics explored in this project are among the central questions in combinatorics. One goal is to improve understanding of the power and limitation of the regularity method through understanding the bounds in several important applications. Another goal is to determine when random constructions using the probabilistic method give optimal or nearly optimal bounds. Several classical topics include Sidorenko's conjecture, Ramsey theory, and Turan numbers of bipartite graphs. The investigator will use and further develop multiple techniques to tackle these problems, including regularity methods such as Szemeredi's regularity lemma and weak regularity lemmas, and analytic tools such as graph limits and random processes. 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.