CAREER: Graph Structural Theorems, Asymptotic Dimension, and Beyond

该项目旨在发展图的结构定理，并将其应用于与几何相关的概念启发的数学和计算机科学问题。图是组合对象，在数学中被广泛研究，并用于工程、统计学、生物学、经济学和许多其他学科的系统建模。图可以用来表示空间或网络，并对空间中点之间或网络中机器之间的距离进行编码。渐近维数是一个概念，涉及在度量几何、几何群论和分布式计算中研究的空间或网络的大规模行为。PI和他的合作者最近使用了结构图论（组合学的一个核心研究领域）的工具，建立了关于渐近维的结果，展示了在数学不同领域解决开放问题的可能性。本项目旨在进一步探索这一方向，通过发展新的图的结构定理来激发它们在计算机科学和度量几何中的潜在应用，包括但不限于关于渐近维数的问题。该项目包含教育部分，包括学生指导，研究生和本科生的研究机会，课程开发，为K-12学生和公众设计的外展活动。该项目的主要目标是发展新的图结构定理，并将它们应用于解决组合学、理论计算机科学和其他数学领域的开放问题。第一个方向是研究由图的次闭族支持的度量空间。这些指标的嵌入问题及其在计算机科学中的相关应用已经引起了广泛的关注。该项目的一个目标是为未成年封闭家庭开发新的结构定理来解决这些问题。第二个方向是研究具有多项式展开的图类。由于这种图类与分隔理论的紧密联系，在计算机科学和几何图论中得到了广泛的研究。该项目的目标是在不涉及分隔理论的情况下为这些类开发分解定理，为研究这些类铺平新的道路。一个潜在的应用是确定具有有限渐近维的图类的稀疏性层次结构。第三个方向是新兴的诱导图小理论，它结合了图小理论和诱导子图理论这两个结构图论的主要方向。本项目的目标是通过从渐近维数和度量几何中获得灵感，将现有的稀疏图的图小理论扩展到密集图的理论，从而研究这一领域。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.