CAREER: Graph Structural Theorems, Asymptotic Dimension, and Beyond

职业：图结构定理、渐近维数及其他

• 批准号: 2144042
• 负责人: Chun-Hung Liu
• 金额: $ 40万
• 依托单位: Texas A&M University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-07-01 至 2027-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2144042&HistoricalAwards=false
• 关键词: CAREER; Graph; Structural; Theorems; Asymptotic

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.

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

项目成果

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth

正确的无冲突列表着色、奇数次要、细分和分层树宽

• DOI: 10.1016/j.disc.2023.113668
• 发表时间: 2024
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Liu, Chun-Hung

Phase transition of degeneracy in minor-closed families

• DOI: 10.1016/j.aam.2023.102489
• 发表时间: 2019-12
• 期刊: Adv. Appl. Math.
• 作者: Chun-Hung Liu;F. Wei

Defective Coloring is Perfect for Minors

有缺陷的色彩非常适合未成年人

• DOI: 10.1007/s00493-024-00081-8
• 发表时间: 2024
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Liu, Chun-Hung

Clustered coloring of graphs with bounded layered treewidth and bounded degree

具有有界分层树宽和有界度的图的聚类着色

• DOI: 10.1016/j.ejc.2023.103730
• 发表时间: 2023
• 期刊: European Journal of Combinatorics
• 影响因子: 1
• 作者: Liu, Chun-Hung;Wood, David R.
• 通讯作者: Wood, David R.