Advancing Ramsey theory and Extremal Combinatorics

About This Grant

This project will make advances on fundamental problems in Ramsey theory and extremal combinatorics, which study conditions guaranteeing the existence of patterns in discrete structures, through the further development of techniques from a variety of areas of mathematics, including from combinatorics, probability, analysis, and algebraic geometry. These methods and problems are not only of intrinsic interest but relate to important applications in computer science, including the development of faster algorithms for problems of real-world utility like matrix multiplication and understanding the properties of large networks. Students will be mentored as part of this research project. The first area in this project concerns Ramsey numbers of hypergraphs, including better understanding the role of the number of colors and how the structure of hypergraphs impacts the off-diagonal growth rate. The PI and his collaborators have previously made significant progress on these directions. The PI also plans to continue studying the Erdős-Hajnal conjecture and variants, which roughly shows that graphs with a forbidden substructure are well-structured (have large independent sets or cliques). Finally, the PI plans to continue collaborative work on Alon's conjecture on the existence of Ramsey Cayley graphs for all finite groups and related longstanding problems in additive combinatorics, information theory and random graph theory. 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.