Extremal problems for sparse hypergraphs and graphs

Miami University, Oxford OH

Investigators

Abstract

Extremal combinatorics is a fast developing subarea within modern mathematics that investigates extremal values of useful parameters of discrete networks/systems. Its study has far reaching applications in computer science, information theory, engineering, or even social science. The project focuses on the following central problem in extremal combinatorics: how large/dense can a discrete system be before certain substructures are set to emerge? Such a study is critical to our analysis of discrete networks. In the analysis of discrete networks, graphs and hypergraphs are two of the main mathematical models. In the past several decades, powerful tools have been developed in the study of graphs and hypergraphs, especially for those that are dense. However, in general, there is a lack of effective tools for sparse graphs and hypergraphs. The project aims at developing some useful tools for the study of extremal problems for sparse graphs and hypergraphs via a study of several specific problems. The first objective of this project is to adapt tools from classical extremely set theory for general sparse hypergraphs. The PI and collaborators have recently applied tools from classical extremal set theory such as the delta system method and shadow analysis to solve Turan type problems for some general sparse hypergraphs. The PI will exploit this connection and look to adapt and develop tools for a more widely applicable setting. A second objective is to investigate how the shadow structure of a sparse hypergraph affects its Turan and Ramsey properties. One particular problem in this direction is to study Turan and Ramsey problems for hypergraphs that are obtained from graphs through expanding edges into hyperedges via new vertices. Another problem of particular emphasis is the Turan problem for hyperforests on which the PI and collaborators and other groups have made substantial recent progress, generalizing several classic results. A third objective is to combine existing tools and to develop new tools for the Turan problem for sparse bipartite graphs. One particular plan is to explore the combination of the expansion method with supersaturation of subgraphs and dependent random choice on sparse bipartite graphs. The PI and collaborators have had some recent success in this direction and will continue such an investigation. There is also an important educational component to this project. The PI has been actively involving masters students in research projects and will continue such endeavors on this project.