CAREER: Graph Structural Theorems, Asymptotic Dimension, and Beyond

点击翻译按钮获取中文摘要

This project aims to develop structural theorems for graphs and apply them to questions in mathematics and computer science inspired by notions related to geometry. Graphs are combinatorial objects that have been extensively studied in mathematics and used for modeling systems in engineering, statistics, biology, economics, and many other disciplines. Graphs can be used to represent spaces or networks and to encode distance between points in spaces or machines in networks. Asymptotic dimension is a notion that concerns large-scale behaviors of such spaces or networks studied in metric geometry, geometric group theory, and distributed computing. The PI and his collaborators recently used tools from structural graph theory, a central research area in combinatorics, to establish results about asymptotic dimension, showing possibilities for attacking open questions in different areas in mathematics. This project aims to further explore this direction by developing novel structural theorems about graphs motivated by their potential applications to computer science and metric geometry, including but not limited to questions about asymptotic dimension. This project contains an education component, including student mentoring, research opportunities for graduate students and advanced undergraduate students, and course development, with outreach activities designed for K-12 students and the public.The main objective of this project is to develop novel graph structural theorems and apply them to solve open questions in combinatorics, theoretical computer science, and other areas in mathematics. The first direction is to study metric spaces supported by minor-closed families of graphs. Embedding problems and related applications in computer science for such metrics have attracted wide attention. One goal of this project is to develop new structural theorems for minor-closed families to attack those problems. The second direction is to study graph classes with polynomial expansion. Such graph classes have been extensively studied in computer science and geometric graph theory due to its tight connection to separator theory. A goal of this project is to develop decomposition theorems for such classes without involving separator theory to pave a novel way for studying those classes. A potential application is to determine the sparsity hierarchy for graph classes with finite asymptotic dimension. The third direction addresses the emerging induced graph minor theory, which combines graph minor theory and induced subgraph theory, two major directions in structural graph theory. An objective of this project is to study this area by extending the existing graph minor theory for sparse graphs to theory for dense graphs via notions inspired from asymptotic dimension and metric geometry.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.