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. A goal is to extend classical theorems in the area and to discover new phenomena using modern approaches, which include the semirandom or nibble method and hypergraph regularity. The PI and his collaborators have recently used these tools to improve and extend several results in combinatorics that have been around for decades. The plan is to continue these projects. Several questions that were unapproachable for many years have suddenly come within reach due to some ground-breaking recent developments and the PI plans to continue exploiting these new techniques to shed light on old problems. The specific questions to be attacked concern the chromatic number of locally sparse hypergraphs, the structure of typical hypergraphs that contains no copy of some fixed configuration, and the enumeration of copies of one hypergraph in another. The extremal theory of hypergraphs impacts several areas of Mathematics and also has consequences in other fields like information theory, coding theory, and theoretical computer science. The study of random structures and randomized algorithms has gained importance in recent years due to the proliferation of large networks like the internet and various other social networks. Developing new techniques to study these complex systems will be a major task for future researchers. Part of this project seeks to develop randomized algorithms that break a large complicated system into smaller, well understood pieces.