Extremal and Ramsey-Type Problems for Graphs and Hypergraphs

Emory University, Atlanta GA

Investigators

Abstract

Graphs and hypergraphs are mathematical structures that model relations among objects, such as the friendship relation in a society. The study of these structures has numerous applications in various branches of mathematics, computer science and engineering. Consequently, understanding these and other related mathematical structures is important. One of the techniques in the study of these structures, probabilistic reasoning, has been crucial in the development of modern algorithms and the design of robust, efficient, and economical communication networks. Another application of probabilistic reasoning in discrete mathematics is based on the fact that one can decompose deterministic objects into pieces that share many properties with randomly generated objects. This general approach, pioneered by E. Szemeredi, has been generalized and enriched in the last couple of decades, and is now one of the central methods in the investigation of large graphs and hypergraphs. The PI plans to work on Turan-, Dirac-, and Ramsey-type questions for graphs and hypergraphs. A considerable part of the research proposed by the PI will employ, among others, the methodology mentioned above. A prime example is the investigation of Turan densities. Most of the other problems also fall within the theory of hypergraphs and are focused on questions in Ramsey theory and extremal combinatorics. Several of the problems considered here can be traced back to classical research of Paul Erdos, whose work, as well as many problems, shaped these branches of discrete mathematics. 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.