Hypergraphs and Ramsey Theory

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

The PI will develop the theory of 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 plans to involve graduate students in this research. The PI will focus on two particular areas of combinatorics: Extremal hypergraph theory and Ramsey theory. In the first area, the main object to be explored is the "feasible region" of a hypergraph. This captures two of the most important themes in extremal combinatorics: shadow theorems exemplified by the Kruskal-Katona theorem, and extremal hypergraph problems exemplified by Turan's theorem and its various extensions to hypergraphs. The PI and his coauthors have developed the basic theory of feasible regions for both hypergraphs and induced graphs in a series of papers. Still, many foundational issues remain unresolved and settling these could be considered one of the main thrusts of this project. In the second area, the PI plans to work on fundamental problems in Ramsey theory. The main problems that will be explored here are the determination of the tower growth rates of diagonal and off-diagonal classical hypergraph Ramsey numbers, as well as of the closely related Erdos-Hajnal function. The PI will also try to obtain better bounds for off-diagonal graph Ramsey numbers using pseudorandom structures. 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.