Forbidden Substructures in Graphs and Hypergraphs

University Of Montana, Missoula MT

Investigators

Abstract

A graph is a mathematical model used to study network-like structures. Everyday examples include social networks (individuals and friendships), transport networks (stops and routes), and chemical structures (atoms and bonds). Modeling such networks as graphs allows us to solve real-world problems by applying theorems and algorithms from the subject of graph theory. For instance, when a car’s GPS gives an optimal route to a destination, it solves the ‘shortest path problem’ on the corresponding graph (intersections and roads). This project focuses on extremal graph theory, which is the study of the optimal structure and behavior of graphs under specified constraints. Results in this field have direct applications in computer science and information theory and can characterize the theoretical limits of algorithms applied to networks. The activity in this project will engage undergraduate research groups and provide graduate mentoring. The PI will also lead mathematics outreach for K-12 students and the general public. This project has three main research goals. The first is to further extend the Turán function. In particular, the PI will examine the Ramsey-Turán problem in the generalized setting where we enumerate subgraphs, and continue to develop the theory of positive co-degree Turán density. The second is to make progress on the Tree Packing Conjecture, which concerns decompositions of the complete graph into trees, leveraging ideas from the recent resolution of the related Ringel Conjecture. The third is to explore the connections between graph theory and coarse geometry and understand the behavior of coarse graphs. Of particular interest is the structure of coarse graphs that do not contain asymptotic minors (a ‘coarse’ generalization of ordinary graph minors). Understanding these structures is expected to lead to coarse analogues of foundational theorems in graph minor theory. 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.