Extremal Problems on Graphs and Hypergraphs

Miami University, Oxford OH

Investigators

Abstract

Fast technological developments have necessitated our efforts to understand large complex networks, such as the internet. Questions studied in this project are of the general theme: what kind of local substructures are forced to emerge when a network/system is dense enough? Finding solutions to these problems will allow us to perform tasks on large networks more efficiently and will yield applications in areas such as computer science, coding theory, and information theory. The specific problems studied fall into the realm of extremal combinatorics: a study of discrete mathematical objects under various local constraints. In recent decades, extremal combinatorics has witnessed significant developments thanks to both practical problems arising from applications and an infusion of ideas and tools from various other branches of mathematics such as probability, algebra, geometry and analysis. For dense systems, a well-developed method called the regularity method allows one to partition a system into well-behaved uniform pieces. However, for sparser systems, no such universally applicable tools exist. This project aims at developing more universal tools for sparse systems through the study of supersaturation of substructures and through finding effective applications of the sparse regularity method. The problems pursued in the project are suitable for graduate students and early career mathematicians whom the PI will actively engage. The project focuses on Turan type extremal problems, in which we want to determine how dense a system can be when certain sub-configurations are forbidden. These problems are central to the development of extremal combinatorics. For graphs, the problem is well-solved when the forbidden subgraph is non-bipartite (i.e. not 2-colorable). When the forbidden subgraph is bipartite, the problem becomes more intractable due to the host graph being sparse. Much effort in developing this important field is driven by several general conjectures of Erdos and Simonovits, particularly the two so-called Turan exponents conjectures. In a recent breakthrough, Bukh and Conlon solved one of the two conjectures, while the one for single bipartite graphs is wide-open. The PI and his collaborators made initial progress on this second conjecture through the so-called supersaturation approach. The idea is to use supersaturation of certain subgraphs together with local constraints of the host graph to build the forbidden subgraph once the host graph is too dense. This method has the potential of being developed into a general tool to tackle Turan type extremal problems in the sparse setting. The PI looks to fully develop this method and make further progress on the Turan exponent conjecture. Another aim of the project is to find effective ways to apply the sparse regularity method for deterministic Turan type problems in the sparse setting. A third set of problems the PI will pursue are extremal problems on cycles in graphs and hypergraphs. 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.