Extremal Combinatorics: Themes and Challenging Problems

Princeton University, Princeton NJ

Investigators

Abstract

Combinatorics is a fundamental area of mathematics. This project mainly concerns the area of graph theory, an active area of combinatorics which has been booming in recent years because of its connection to other areas of mathematics and theoretical computer science. Many graph theory problems also have practical motivations. Most of the world can be represented as large networks consisting of nodes and the connections between certain pairs of them. For example, a social network such as Facebook has over 2 billion users as nodes and friendship relations as connections; a biological network like the brain has over 100 billion neurons as nodes and synapses as connections. Understanding those networks and designing fast algorithms on them provides much practical value, examples include understanding how news spreads in a social network, understanding brain functions or diseases and improving artificial neural networks for machine learning applications. This project considers several fundamental questions in extremal graph theory. The project also provides training opportunities for graduate and undergraduate students. There are multiple techniques the PI plans to use and further develop, including regularity methods such as Szemeredi's regularity lemma and weak regularity lemmas; analytic tools such as graph limits, random processes and entropy methods; and various other combinatorial tools. The first project is related to Szemeredi's regularity lemma, which is an extremely powerful tool in modern graph theory which spurred a dramatic change of how we view and study graphs. It is a major direction of research to study which applications of the regularity lemma have considerably better bounds. The PI will work on several classical questions where the goal is to improve our understanding of the power and limitation of the regularity method through understanding the bounds in various important applications. Another major project 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 related questions in graph limits. The goal is to better understand this general direction through studying several closely related and concrete problems and gain more insight on the connections between these topics. 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.