Extremal Questions for Hypergraphs

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

The PI will develop the theory of hypergraphs, or families of finite sets, focusing on the relationship between local and global properties. Questions about the local/global relationships in large structures impact several areas of mathematics (number theory, combinatorics, logic) as well as other fields like information theory, coding theory, theoretical computer science, and the social sciences. 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. 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 focus on two particular areas: Ramsey theory and Extremal problems for hypergraphs. Within Ramsey theory, he plans to work on fundamental problems in the area posed by Erdos, Hajnal, and Rado starting the 1950's about the tower growth rate of classical hypergraph Ramsey numbers. Several other related problems posed by Erdos-Gyarfas-Shelah, Erdos-Rogers, and Erdos-Hajnal will also be explored. His planned projects in extremal hypergraph theory include the following: solving an old conjecture of Kalai on the extremal number of hypergraph trees that generalizes the well-known Erdos-Sos conjecture for graphs; studying the relationship between problems in convex geometry and abstract extremal hypergraph problems; developing an approach towards improving the longstanding bound of Kostochka on the sunflower problem; improving the known supersaturation results for cycles in linear hypergraphs, which has applications to a problem in additive number theory studied by Bourgain and Katz-Tao; and studying a question posed in various forms by Razborov and Lovasz-Szegedy about whether a large class of problems in extremal combinatorics can be solved using methods stemming from the Cauchy-Schwarz inequality. 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.