Extremal and Probabilistic Questions on Hypergraphs

University Of Illinois At Chicago, Chicago IL

Investigators

Abstract

The PI will develop the theory of hypergraphs, or families of sets, focusing on extremal and probabilistic questions. Three directions of study are proposed: quasirandomness, extremal Turan-type problems, and ramsey theory. In each of these areas, the PI will extend classical results in graph theory that have been around for decades to hypergraphs. For example, extending the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs to hypergraphs has received considerable attention since the early 1990's and the PI has made further progress recently; he plans to explore the sparse case in this project. The PI (together with coauthors) has recently extended the Erdos-Gallai theorem about paths and cycles in graphs to hypergraphs; further extensions of the new method that was developed will be explored for other forbidden structures. Finally, there have been relatively few results in hypergraph Ramsey theory since some basic bounds of Erdos and others from the 1950's and the PI will use modern approaches to tackle some outstanding problems in these areas. The extremal and probabilistic theory of hypergraphs impacts several areas of Mathematics (number theory, combinatorics, logic) as well as other fields like information theory, coding theory, and theoretical computer science. The study of random structures and randomized algorithms 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. The theory of quasirandom hypergraphs may form a theoretical foundation for studying large scale behavior of more complicated networks where groups of more than two nodes are connected to each other. One theme common to most problems that will be investigated in this project is to understand the quantitative relationship between the local and global behavior of a large system.