Extremal Problems on Graphs and Hypergraphs and Ramsey Theory

The PI will develop the theory of networks and families of finite sets, focusing on how local constraints affect global structure. These types of questions impact several areas of mathematics as well as other fields like information theory, coding theory and theoretical computer science. The study of these objects has gained particular importance in recent years due to the many large real-world networks that have emerged and are being studied, and more recently in the development of AI models. Developing new techniques to study these complex systems will be a major task for future researchers and the PI plans to contribute to this through his theoretical work. The PI will also train Ph.D. students in combinatorics and it is expected that some of them will go on to careers in AI and quantum computing. Consequently, the broader impacts of this proposal will contribute to workforce development in pure mathematics and theoretical computer science, as well as in both AI and quantum computing that will translate from the academic setting to industry. The PI will focus on two particular areas of combinatorics: Extremal graph and hypergraph theory, and Ramsey theory. In the first area, one problem that the PI will study is the supersaturation phenomenon for pentagons in linear hypergraphs, whose resolution would have some consequences in number theory and discrete geometry. Another problem to be investigated is the inducibility problem for graphs. Finally, the PI will also try to prove some old and more recent conjectures in extremal hypergraph theory where the forbidden hypergraph is linear. In Ramsey theory, the PI will investigate classical problems in graph and hypergraph Ramsey theory, where he will attempt to both give new lower bounds (constructions) as well as to improve some longstanding upper bounds. 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. NSF Award ID: 2552740 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Dhruv Mubayi | Institution: University of Illinois at Chicago, CHICAGO, IL | Award Amount: $180,000 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2552740 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2552740.html